BST.java
|
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 |
import java.util.ArrayList; class BST { private class BSTNode { int value; BSTNode left; BSTNode right; public BSTNode(int 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 root; private BSTNode insert(BSTNode curr, int value){ if (curr == null) return new BSTNode(value); if (value > curr.value) curr.right = insert(curr.right, value); else if (value < curr.value) curr.left = insert(curr.left, value); return curr; } public void insert(int value){ root = insert(root, value); } public void printTree(){ System.out.println(root.toString()); } // Testing public static void main(String[] args){ BST 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); bst.printTree(); } } |