也就两个部分：
Node:
1 package models.BST; 2 3 public class BSTNode<E extends Comparable<E>> { 4 E data; 5 BSTNode<E> leftChild, rightChild; 6 7 public BSTNode() { 8 } 9 10 public BSTNode(E data, BSTNode<E> leftChild, BSTNode<E> rightChild) { 11 this.data = data; 12 this.leftChild = leftChild; 13 this.rightChild = rightChild; 14 } 15 16 public BSTNode(E data) { 17 this.data = data; 18 this.leftChild = null; 19 this.rightChild = null; 20 } 21 22 public String toString() { 23 return "This BSTNode is [" + data + "]"; 24 } 25 26 public E getLeftmostData() { 27 if (leftChild == null) return data; 28 else return leftChild.getLeftmostData(); 29 } 30 31 public E getRightmostData() { 32 if (rightChild == null) return data; 33 else return rightChild.getRightmostData(); 34 } 35 36 public String inorderPrint() { 37 String res = ""; 38 if (leftChild != null) res += leftChild.inorderPrint() + " "; 39 res += data + " "; 40 if (rightChild != null) res += rightChild.inorderPrint() + " "; 41 return res.substring(0, res.length() - 1); 42 } 43 44 public String preorderPrint() { 45 String res = data + " "; 46 if (leftChild != null) res += leftChild.preorderPrint() + " "; 47 if (rightChild != null) res += rightChild.preorderPrint() + " "; 48 return res.substring(0, res.length() - 1); 49 } 50 51 public String postorderPrint() { 52 String res = ""; 53 if (leftChild != null) res += leftChild.preorderPrint() + " "; 54 if (rightChild != null) res += rightChild.preorderPrint() + " "; 55 res += data + " "; 56 return res.substring(0, res.length() - 1); 57 } 58 59 public boolean isLeaf() { 60 return leftChild == null && rightChild == null; 61 } 62 63 public BSTNode<E> removeLeftmost() { 64 if (leftChild == null) return rightChild; 65 else { 66 leftChild = leftChild.removeLeftmost(); 67 return this; 68 } 69 } 70 71 public BSTNode<E> removeRightmost() { 72 if (rightChild == null) return leftChild; 73 else { 74 rightChild = rightChild.removeLeftmost(); 75 return this; 76 } 77 } 78 79 public int Size(BSTNode<E> root) { 80 if (root == null) return 0; 81 else return 1 + Size(root.leftChild) + Size(root.rightChild); 82 } 83 }
BST:
1 package models.BST; 2 3 public class BST<E extends Comparable<E>> { 4 BSTNode<E> root; 5 6 public BST() { 7 root = null; 8 } 9 10 public boolean isEmpty() { 11 return root == null; 12 } 13 14 public void insert(E data) { 15 root = insert(root, data); 16 } 17 18 public BSTNode<E> insert(BSTNode<E> node, E data) { 19 if (node == null) { 20 node = new BSTNode<E>(data); 21 return node; 22 } 23 if (data.compareTo(node.data) < 0) node.leftChild = insert(node.leftChild, data); 24 else node.rightChild = insert(node.rightChild, data); 25 return node; 26 } 27 28 public int countNodes() { 29 return countNodes(root); 30 } 31 32 private int countNodes(BSTNode<E> root) { 33 return root.Size(root); } 34 35 public boolean search(E data) { 36 return search(root, data); 37 } 38 39 private boolean search(BSTNode<E> node, E data) { 40 if (node == null) return false; 41 if (node.data.compareTo(data) == 0) return true; 42 return node.data.compareTo(data) > 0 ? search(node.leftChild, data) : search(node.rightChild, data); 43 } 44 45 public BSTNode<E> delete(E data) { 46 return delete(root, data); 47 } 48 49 private BSTNode<E> delete(BSTNode<E> node, E data) { 50 if (node == null) return null; 51 if (data.compareTo(node.data) < 0) node.leftChild = delete(node.leftChild, data); 52 else if (data.compareTo(node.data) > 0) node.rightChild = delete(node.rightChild, data); 53 else { 54 if (node.leftChild == null) return node.rightChild; 55 else if (node.rightChild == null) return node.leftChild; 56 node.data = node.rightChild.getLeftmostData(); 57 node.rightChild = delete(node.rightChild, node.data); 58 } 59 return node; 60 } 61 62 public String inorder() { 63 return "Inorder DFS of this BST is: [" + root.inorderPrint() + "]"; 64 } 65 66 public String preorder() { 67 return "Preorder DFS of this BST is: [" + root.preorderPrint() + "]"; 68 } 69 70 public String postorder() { 71 return "Postorder DFS of this BST is: [" + root.postorderPrint() + "]"; 72 } 73 74 }