Java：我如何實現一個通用的二叉搜索樹？

Question

到現在爲止，我一直在寫一個節點類作爲

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

和二叉搜索樹爲

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

現在我想支持BinarySearchTree有任何類型的字符串一樣，人們的插入節點

我怎樣才能使它通用持有任何類型？

Answer 1

使用泛型：

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

你有兩個選擇：

1）您可以進入仿製藥/模板。

2）讓你的樹參加Object而不是int，並讓用戶負責施放。

Answer 3

Regaring第二個問題，你應該使用模板：

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

關於第一：

http://en.wikipedia.org/wiki/Binary_search_algorithm http://en.wikipedia.org/wiki/Tree_rotation（插入）

也許這是更快的閱讀：

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

好好學習！

Answer 4

就使每個Node和BinarySearchTree類通用的：

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

和：

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

注意Comparable擴展約束，你可能會需要執行節點排序樹。感謝zaske的建議。

Answer 5

請不要您的代碼不能編譯。
你有幾個挑戰在這裏 -
A.定義節點作爲通用 -

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

B.你的搜索類也應該是通用的，並且簽名應該是

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

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

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

這是爲了強制您僅提供實現Comparable的類型，因此您將能夠在樹中執行搜索。

Answer 6

我發現了一個SnapTreeMap，它實現了a concurrent AVL tree系統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); 
     } 
    } 

}