Java: come implementare un albero di ricerca binaria generico?

Question

Fino ad ora, ho scritto una classe Node come

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; 
     } 
    } 

e Binary Search albero come

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 
    } 
} 

Ora vorrei sostenere BinarySearchTree avere nodo di inserimento di qualsiasi tipo come stringhe, le persone

Come posso renderlo generico per contenere qualsiasi tipo?

Answer 1

Utilizzare farmaci generici:

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

Si hanno due opzioni:

1) si può entrare in farmaci generici/templates.

2) Avere l'albero in un tipo Object anziché int e l'utente è responsabile della trasmissione.

Answer 3

regaring seconda domanda si dovrebbe usare Template:

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

Per quanto riguarda in primo luogo:

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

Forse è più veloce leggere:

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

Buono studio!

Answer 4

Basta fare ciascuno dei Node e BinarySearchTree classi generiche:

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; 
    } 
} 

e:

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 il vincolo estensione Comparable che sarà necessario in seguito di far rispettare il nodo ordinamento nell'albero. Grazie a zaske per il suggerimento.

Answer 5

Si prega di non compilare il codice.
Hai alcune sfide qui -
A. Definire Nodo come generico -

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

B. classe La ricerca dovrebbe anche essere generico, e la firma dovrebbe essere

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

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

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

Questo è necessario al fine di imporre all'utente di fornire solo i tipi che implementano Comparable in modo da poter eseguire la ricerca nell'albero.

Answer 6

Ho trovato una SnapTreeMap che implementa il sistema here.

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); 
     } 
    } 

}