Java: ¿Cómo implemento un árbol genérico de búsqueda binaria?

Question

Hasta ahora, he estado escribiendo una clase de nodo como

class Node { 
     private value; 
     private Node left; 
     private Node right; 

     public int getValue() { 
      return value; 
     } 

     public void setValue(int value) { 
      this.value = value; 
     } 

     public Node getLeft() { 
      return left; 
     } 

     public void setLeft(Node left) { 
      this.left = left; 
     } 

     public Node getRight() { 
      return right; 
     } 

     public void setRight(Node right) { 
      this.right = right; 
     } 
    } 

y búsqueda binaria árbol como

public class BinarySearchTree { 
    private Node root; 

    public BinarySearchTree(int value) { 
     root = new Node(value); 
    } 

    public void insert(int value) { 
     Node node = new Node(value); 
     // insert logic goes here to search and insert 
    } 
} 

Ahora me gustaría apoyar BinarySearchTree tener nodo de inserción de cualquier tipo, como cuerdas, las personas

¿Cómo puedo hacer que sea genérico para contener cualquier tipo?

Answer 1

Use genéricos:

class Node<T extends Comparable<T>> { 
     private T value; 
     ... 
} 

public class BinarySearchTree<T extends Comparable<T>> { 
    private Node<T> root; 

    public BinarySearchTree(T value) { 
     root = new Node<T>(value); 
    } 

    public void insert(T value) { 
     Node<T> node = new Node<T>(value); 
     // insert logic goes here to search and insert 
    } 
} 

Answer 2

tiene dos opciones:

1) Usted puede conseguir en genéricos/templates.

2) Tenga su árbol en un tipo Object en lugar de int y haga que el usuario sea responsable de la fundición.

Answer 3

regaring segunda pregunta que debe utilizar la plantilla:

http://www.oracle.com/technetwork/articles/javase/generics-136597.html

En cuanto a la primera:

http://en.wikipedia.org/wiki/Binary_search_algorithm http://en.wikipedia.org/wiki/Tree_rotation (inserto)

Tal vez es más rápido leer:

http://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml

¡Buen estudio!

Answer 4

Simplemente haga cada uno de los Node y BinarySearchTree clases genéricas:

class Node<T extends Comparable<T>> { 
    private T value; 
    private Node<T> left; 
    private Node<T> right; 

    public Node(T value) { 
     this.value = value; 
    } 

    public T getValue() { 
     return value; 
    } 

    public void setValue(T value) { 
     this.value = value; 
    } 

    public Node<T> getLeft() { 
     return left; 
    } 

    public void setLeft(Node<T> left) { 
     this.left = left; 
    } 

    public Node<T> getRight() { 
     return right; 
    } 

    public void setRight(Node<T> right) { 
     this.right = right; 
    } 
} 

y:

class BinarySearchTree<T extends Comparable<T>> { 
    private Node<T> root; 

    public BinarySearchTree(T value) { 
     root = new Node<T>(value); 
    } 

    public void insert(T value) { 
     Node<T> node = new Node<T>(value); 
     // insert logic goes here to search and insert 
    } 
} 

Nota del Comparable extensión restricción de que necesitará más adelante para hacer cumplir pedidos nodo en el árbol. Gracias a zaske por la sugerencia.

Answer 5

Por favor, no se compila su código.
Usted tiene unos retos aquí -
A. Definir como nodo genérico -

public class Node<T> { 
    private T value; 
    //... here goes the rest of your code 
} 

B. clase Su búsqueda también debe ser genérico, y la firma debe ser

public class BinarySearchTree <T extends Comparable<T>> { 

    public BinarySearchTree(T value) { 
     //Do your logic here 
    } 

    public void insert(T value) { 
     //Do your logic here 
    } 
} 

Este es necesario para obligarlo a proporcionar solo tipos que implementen Comparable para que pueda realizar la búsqueda en el árbol.

Answer 6

Encontré un SnapTreeMap que implementa el sistema a concurrent AVL treehere.

Answer 7

Please find the BST using Generics, U can find more information on below link 

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/code/BST.java

public class BinarySearchTree< T extends Comparable<T>> { 
    Node root; 
    class Node { 
     T data; 
     Node left; 
     Node right; 

     public Node(T data) { 
      this.data = data; 
     } 
    } 

    public boolean isEmpty() { 
     return root == null; 
    } 

    public void insert(T value) { 
     if(isEmpty()) 
      root = new Node(value); 
     else 
      insert(root, value); 
    } 

    private void insert(Node node, T value) { 

     if(value.compareTo(node.data) < 0) { 
      if(node.left == null) 
       node.left = new Node(value); 
      else 
       insert(node.left, value); 
     } 
     else { 
      if(node.right == null) 
       node.right = new Node(value); 
      else 
       insert(node.right, value); 
     } 
    } 

}