1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
public class BST<E extends Comparable<E>>{ @SuppressWarnings("ClassCanBeStatic") private class BSTNode<U extends Comparable<U>>{ BSTNode<U> left, right; U value; public BSTNode(U value){ this.value = value; } // Adapted from Todd Davies answer to printing a BST on Stack Overflow. // https://stackoverflow.com/questions/4965335/how-to-print-binary-tree-diagram private StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) { if(right!=null) { right.toString(new StringBuilder().append(prefix).append(isTail ? "│ " : " "), false, sb); } sb.append(prefix).append(isTail ? "└── " : "┌── ").append(value).append("\n"); if(left!=null) { left.toString(new StringBuilder().append(prefix).append(isTail ? " " : "│ "), true, sb); } return sb; } @Override public String toString() { return this.toString(new StringBuilder(), true, new StringBuilder()).toString(); } } private BSTNode<E> root; private BSTNode<E> search(BSTNode<E> curr, E value){ if (curr == null || curr.value.equals(value)) return curr; if (value.compareTo(curr.value) > 0) return search(curr.right, value); return search(curr.left, value); } public boolean contains(E value){ return search(root, value) != null; } private void printInOrder(BSTNode<E> curr){ if (curr != null){ // Print left subtree printInOrder(curr.left); // Print curr System.out.print(curr.value + " "); // Print right subtree printInOrder(curr.right); } } public void printInOrder(){ printInOrder(root); System.out.println(); } /* // Look-ahead version of insert. private void insert(BSTNode<E> curr, E value){ // In look-ahead, the only way curr can be null is if it's the root. if (curr == null) root = new BSTNode<E>(value); else if (value.compareTo(curr.value) > 0){ if (curr.right == null) curr.right = new BSTNode<E>(value); else insert(curr.right, value); } else if (value.compareTo(curr.value) < 0) if (curr.left == null) curr.left = new BSTNode<E>(value); else insert(curr.left, value); } */ private BSTNode<E> insert(BSTNode<E> curr, E value){ if (curr == null) return new BSTNode<E>(value); if (value.compareTo(curr.value) > 0) curr.right = insert(curr.right, value); else if (value.compareTo(curr.value) < 0) curr.left = insert(curr.left, value); return curr; } public void insert(E value){ root = insert(root, value); // For lookahead version: //insert(root, value); } @Override public String toString(){ return root.toString(); } // Test code. public static void main(String[] args){ BST<Integer> bst = new BST<>(); bst.insert(8); bst.insert(3); bst.insert(1); bst.insert(6); bst.insert(4); bst.insert(7); bst.insert(10); bst.insert(14); bst.insert(13); System.out.println(bst); System.out.println("9? " + bst.contains(9)); System.out.println("7? " + bst.contains(7)); bst.printInOrder(); } } |