001package algs32; 002import algs13.Queue; 003import stdlib.*; 004 005/* *********************************************************************** 006 * A simple BST with int keys and no values 007 * 008 * Complete each function below. 009 * Write each function as a separate recursive definition (do not use more than one helper per function). 010 * Depth of root==0. 011 * Height of leaf==0. 012 * Size of empty tree==0. 013 * Height of empty tree=-1. 014 *************************************************************************/ 015public class MyIntSET2 { 016 private Node root; 017 private static class Node { 018 public final int key; 019 public Node left, right; 020 public int H; 021 public Node(int key) { this.key = key; } 022 } 023 024 // The field "H" indicates the height of each node. 025 // You must then modify "put" to update the height of each node. 026 // "removeHeight" should also update the field "H". 027 028 // the number of nodes in the tree, at exactly height k 029 // include node n if height(n) == k 030 public int sizeAtHeight(int k) { return 0; } 031 032 // the number of nodes in the tree, above height k (not including k) 033 // include node n if height(n) > k 034 public int sizeAboveHeight(int k) { return 0; } 035 036 // the number of nodes in the tree, below height k (not including k) 037 // include node n if height(n) < k 038 public int sizeBelowHeight(int k) { return 0; } 039 040 // remove all subtrees of height k from the original tree 041 public void removeHeight(int k) {} 042 043 /* *************************************************************************** 044 * Some methods to create and display trees 045 *****************************************************************************/ 046 047 // Modify "put" to update the field "H". 048 public void put(int key) { root = put(root, key); } 049 private Node put(Node n, int key) { 050 if (n == null) return new Node(key); 051 if (key < n.key) n.left = put(n.left, key); 052 else if (key > n.key) n.right = put(n.right, key); 053 return n; 054 } 055 // Do not modify "copy" 056 public MyIntSET2 copy () { 057 MyIntSET2 that = new MyIntSET2 (); 058 for (int key : levelOrder()) 059 that.put (key); 060 return that; 061 } 062 // Do not modify "levelOrder" 063 public Iterable<Integer> levelOrder() { 064 Queue<Integer> keys = new Queue<>(); 065 Queue<Node> queue = new Queue<>(); 066 queue.enqueue(root); 067 while (!queue.isEmpty()) { 068 Node n = queue.dequeue(); 069 if (n == null) continue; 070 keys.enqueue(n.key); 071 queue.enqueue(n.left); 072 queue.enqueue(n.right); 073 } 074 return keys; 075 } 076 // Do not modify "toString" 077 public String toString() { 078 StringBuilder sb = new StringBuilder(); 079 for (int key: levelOrder()) 080 sb.append (key + " "); 081 return sb.toString (); 082 } 083 // You may modify "toGraphviz" if you wish 084 public void toGraphviz(String filename) { 085 GraphvizBuilder gb = new GraphvizBuilder (); 086 toGraphviz (gb, null, root); 087 gb.toFileUndirected (filename, "ordering=\"out\""); 088 } 089 private static void toGraphviz (GraphvizBuilder gb, Node parent, Node n) { 090 if (n == null) { gb.addNullEdge (parent); return; } 091 gb.addLabeledNode (n, Integer.toString (n.key)); 092 if (parent != null) gb.addEdge (parent, n); 093 toGraphviz (gb, n, n.left); 094 toGraphviz (gb, n, n.right); 095 } 096 097 /* *************************************************************************** 098 * Test client 099 * You can modify any of these methods, if you wish 100 *****************************************************************************/ 101 // create a tree from a string 102 public static MyIntSET2 fromString (String ints) { 103 MyIntSET2 set = new MyIntSET2 (); 104 for (String s : ints.split (" ")) 105 try { set.put (Integer.parseInt (s)); } catch (NumberFormatException e) {} 106 return set; 107 } 108 private static int exampleCount = 0; 109 public static void show(MyIntSET2 set, String filename) { 110 exampleCount++; 111 set.toGraphviz ("x" + exampleCount + "-" + filename + ".png"); 112 } 113 public static void test(String s) { 114 MyIntSET2 set = MyIntSET2.fromString(s); 115 StdOut.println ("###############################################################"); 116 StdOut.format ("tree: %s\n", set); show(set, "original"); 117 118 //StdOut.format ("size() = %d\n", set.size()); 119 //StdOut.format ("height() = %d\n", set.height()); 120 //StdOut.format ("sizeOdd() = %d\n", set.sizeOdd()); 121 //StdOut.format ("sizeAtDepth(2) = %d\n", set.sizeAtDepth(2)); 122 //StdOut.format ("sizeAboveDepth(2) = %d\n", set.sizeAboveDepth(2)); 123 //StdOut.format ("sizeBelowDepth(2) = %d\n", set.sizeBelowDepth(2)); 124 //StdOut.format ("isPerfectlyBalancedS() = %b\n", set.isPerfectlyBalancedS()); 125 //StdOut.format ("isPerfectlyBalancedH() = %b\n", set.isPerfectlyBalancedH()); 126 //StdOut.format ("isOddBalanced() = %b\n", set.isOddBalanced()); 127 //StdOut.format ("isSemiBalanced() = %b\n", set.isSemiBalanced()); 128 StdOut.format ("sizeAtHeight(2) = %d\n", set.sizeAtHeight(2)); 129 StdOut.format ("sizeAboveHeight(2) = %d\n", set.sizeAboveHeight(2)); 130 StdOut.format ("sizeBelowHeight(2) = %d\n", set.sizeBelowHeight(2)); 131 132 //set = MyIntSET2.fromString(s); set.removeOddSubtrees(); StdOut.format ("removeOddSubtrees() %s\n", set); show(set, "removeOddSubtrees"); 133 //set = MyIntSET2.fromString(s); set.removeBelowDepth(2); StdOut.format ("removeBelowDepth(2) %s\n", set); show(set, "removeBelowDepth2"); 134 //set = MyIntSET2.fromString(s); set.removeLeaves(); StdOut.format ("removeLeaves() %s\n", set); show(set, "removeLeaves"); 135 //set = MyIntSET2.fromString(s); set.removeSingles(); StdOut.format ("removeSingles() %s\n", set); show(set, "removeSingles"); 136 //set = MyIntSET2.fromString(s); set.addZeroToSingles(); StdOut.format ("addZeroToSingles() %s\n", set); show(set, "addZeroToSingles"); 137 set = MyIntSET2.fromString(s); set.removeHeight(2); StdOut.format ("removeHeight(2) %s\n", set); show(set, "removeHeight2"); 138 } 139 public static void main(String[] args) { 140 test ("90 30 100 10 80 20 40 60 50 70"); 141 //test ("40 20 60 10 30 50 70"); 142 //test (""); 143 //test ("1"); 144 //test ("41 21 61 11 31"); 145 //test ("41 21 61 11 31 51 71 111"); 146 //test ("101 41 21 61 11 31 51 71 111"); 147 //test ("101 41 21 61 11 31 51 71 141 121 161 111 131 151 171 "); 148 //test ("101 40 20 61 11 31 51 71 140 120 161 111 131 151 171 "); 149 //test ("90 30 100 10 81 20 40 60 50 70 62 63 64"); 150 //test ("40 20 61 10 30 50 70"); 151 //test ("41 21 61 11 30 51 70"); 152 //test (""); 153 //test ("1"); 154 //test ("90 30 100 10 80 20 40 60 5 85 35 95 105 2 6 110 103 104 102 93 97 96 82 86 12 21 45 62 106 111 92 94 98 34 36"); 155 156 } 157}