Java: Làm thế nào để thực hiện một cây tìm kiếm nhị phân chung?

Question

Cho đến bây giờ, tôi đã viết một lớp Node như

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

và Binary Search Tree như

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

Bây giờ tôi muốn hỗ trợ BinarySearchTree có chèn nút của bất kỳ loại như dây đàn, người

Làm cách nào để tôi có thể giữ nguyên kiểu này?

Answer 1

Sử dụng Generics:

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

Bạn có hai lựa chọn:

1) Bạn có thể nhận được vào generics/mẫu.

2) Hãy để cây của bạn lấy một loại Object thay vì int và yêu cầu người dùng chịu trách nhiệm truyền.

Answer 3

Regaring câu hỏi thứ hai bạn nên sử dụng mẫu:

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

Về đầu:

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

Có thể đọc nhanh hơn:

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

Nghiên cứu tốt!

Answer 4

Chỉ cần chắc mỗi Node và BinarySearchTree lớp generic:

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

và:

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

Lưu ý Comparable hạn chế mà bạn sẽ cần sau này để thực thi các nút đặt hàng trong cây. Nhờ zaske cho đề nghị.

Answer 5

Vui lòng không mã của bạn không biên dịch.
Bạn có một vài thách thức ở đây -
A. Xác định Node như Generic -

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

B. lớp Tìm kiếm của bạn cũng nên được chung chung, và chữ ký nên

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

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

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

này là bắt buộc để thực thi bạn chỉ cung cấp các loại thực hiện Comparable để bạn có thể thực hiện tìm kiếm trong cây.

Answer 6

Tôi đã tìm thấy Bản đồ SnapTree triển khai a concurrent AVL tree hệ thống 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); 
     } 
    } 

}