Java：如何实现通用二进制搜索树？
到现在为止，我一直在编写一个Node类
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有任何类型的插入节点，如字符串，人
如何将其设为通用以保持任何类型？
使用generics：
class Node> { private T value; ... } public class BinarySearchTree > { private Node root; public BinarySearchTree(T value) { root = new Node (value); } public void insert(T value) { Node node = new Node (value); // insert logic goes here to search and insert } }
只需使每个Node和BinarySearchTree类都通用：
class Node> { private T value; private Node left; private Node right; public Node(T value) { this.value = value; } public T getValue() { return value; } public void setValue(T 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; } }
和：
class BinarySearchTree> { private Node root; public BinarySearchTree(T value) { root = new Node (value); } public void insert(T value) { Node node = new Node (value); // insert logic goes here to search and insert } }
请注意稍后您需要在树中强制执行节点排序的Comparable扩展约束。 感谢zaske提出的建议。
请不要你的代码不编译。
你在这里面临一些挑战 –
A.将节点定义为通用 –
public class Node { private T value; //... here goes the rest of your code }
B.您的搜索类也应该是通用的，签名应该是
public class BinarySearchTree > { public BinarySearchTree(T value) { //Do your logic here } public void insert(T value) { //Do your logic here } }
这是必需的，以便强制您仅提供实现Comparable的类型，以便您可以在树中执行搜索。
你有两个选择：
1）你可以进入generics/模板。
2）让你的树采用Object而不是int类型并让用户负责转换。
我找到了一个SnapTreeMap，它在这里实现了一个并发的AVL树系统。
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> { 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); } } }
public class TNode> { T data; public TNode left; public TNode right; public TNode(T data){ this.data = data; } } import java.util.ArrayList; import java.util.List; public class BinaryTree > { private TNode root; public TNode getRoot() { return this.root; } public void add(T data) { TNode newNode = new TNode (data); if (root == null) { root = newNode; } else { TNode tempNode = root; TNode prev = null; while (tempNode != null) { prev = tempNode; if (data.compareTo(tempNode.data) > 0) { tempNode = tempNode.right; } else { tempNode = tempNode.left; } } if (data.compareTo(prev.data) < 0) { prev.left = newNode; } else { prev.right = newNode; } } } public void traverseInOrder(TNode root, List storageList) { if (root != null) { traverseInOrder(root.left, storageList); storageList.add(root.data); traverseInOrder(root.right, storageList); } } public void traversePreOrder(TNode root, List storageList) { if (root != null) { storageList.add(root.data); traversePreOrder(root.left, storageList); traversePreOrder(root.right, storageList); } } public void traversePostOrder(TNode root, List storageList) { if (root != null) { traversePostOrder(root.left, storageList); traversePostOrder(root.right, storageList); storageList.add(root.data); } } public void printList(List list) { for (T item : list) { System.out.println(item); } } public static void main(String args[]) { BinaryTree bTree = new BinaryTree<>(); bTree.add(50); bTree.add(30); bTree.add(60); bTree.add(25); bTree.add(40); bTree.add(35); bTree.add(70); bTree.add(65); System.out.println("#### Inorder Traversal ####"); List inOrderList = new ArrayList<>(); bTree.traverseInOrder(bTree.getRoot(), inOrderList); bTree.printList(inOrderList); System.out.println("#### Pre Traversal ####"); List preOrderList = new ArrayList<>(); bTree.traversePreOrder(bTree.getRoot(), preOrderList); bTree.printList(preOrderList); System.out.println("#### Post Traversal ####"); List postOrderList = new ArrayList<>(); bTree.traversePostOrder(bTree.getRoot(), postOrderList); bTree.printList(postOrderList); }