package algs32; import algs13.Queue; import stdlib.*; /* *********************************************************************** * A simple BST with int keys and no values * * Complete each function below. * Write each function as a separate recursive definition (do not use more than one helper per function). * Depth of root==0. * Height of leaf==0. * Size of empty tree==0. * Height of empty tree=-1. *************************************************************************/ public class MyIntSET2 { private Node root; private static class Node { public final int key; public Node left, right; public int H; public Node(int key) { this.key = key; } } // The field "H" indicates the height of each node. // You must then modify "put" to update the height of each node. // "removeHeight" should also update the field "H". // the number of nodes in the tree, at exactly height k // include node n if height(n) == k public int sizeAtHeight(int k) { return 0; } // the number of nodes in the tree, above height k (not including k) // include node n if height(n) > k public int sizeAboveHeight(int k) { return 0; } // the number of nodes in the tree, below height k (not including k) // include node n if height(n) < k public int sizeBelowHeight(int k) { return 0; } // remove all subtrees of height k from the original tree public void removeHeight(int k) {} /* *************************************************************************** * Some methods to create and display trees *****************************************************************************/ // Modify "put" to update the field "H". public void put(int key) { root = put(root, key); } private Node put(Node n, int key) { if (n == null) return new Node(key); if (key < n.key) n.left = put(n.left, key); else if (key > n.key) n.right = put(n.right, key); return n; } // Do not modify "copy" public MyIntSET2 copy () { MyIntSET2 that = new MyIntSET2 (); for (int key : levelOrder()) that.put (key); return that; } // Do not modify "levelOrder" public Iterable levelOrder() { Queue keys = new Queue<>(); Queue queue = new Queue<>(); queue.enqueue(root); while (!queue.isEmpty()) { Node n = queue.dequeue(); if (n == null) continue; keys.enqueue(n.key); queue.enqueue(n.left); queue.enqueue(n.right); } return keys; } // Do not modify "toString" public String toString() { StringBuilder sb = new StringBuilder(); for (int key: levelOrder()) sb.append (key + " "); return sb.toString (); } // You may modify "toGraphviz" if you wish public void toGraphviz(String filename) { GraphvizBuilder gb = new GraphvizBuilder (); toGraphviz (gb, null, root); gb.toFileUndirected (filename, "ordering=\"out\""); } private static void toGraphviz (GraphvizBuilder gb, Node parent, Node n) { if (n == null) { gb.addNullEdge (parent); return; } gb.addLabeledNode (n, Integer.toString (n.key)); if (parent != null) gb.addEdge (parent, n); toGraphviz (gb, n, n.left); toGraphviz (gb, n, n.right); } /* *************************************************************************** * Test client * You can modify any of these methods, if you wish *****************************************************************************/ // create a tree from a string public static MyIntSET2 fromString (String ints) { MyIntSET2 set = new MyIntSET2 (); for (String s : ints.split (" ")) try { set.put (Integer.parseInt (s)); } catch (NumberFormatException e) {} return set; } private static int exampleCount = 0; public static void show(MyIntSET2 set, String filename) { exampleCount++; set.toGraphviz ("x" + exampleCount + "-" + filename + ".png"); } public static void test(String s) { MyIntSET2 set = MyIntSET2.fromString(s); StdOut.println ("###############################################################"); StdOut.format ("tree: %s\n", set); show(set, "original"); //StdOut.format ("size() = %d\n", set.size()); //StdOut.format ("height() = %d\n", set.height()); //StdOut.format ("sizeOdd() = %d\n", set.sizeOdd()); //StdOut.format ("sizeAtDepth(2) = %d\n", set.sizeAtDepth(2)); //StdOut.format ("sizeAboveDepth(2) = %d\n", set.sizeAboveDepth(2)); //StdOut.format ("sizeBelowDepth(2) = %d\n", set.sizeBelowDepth(2)); //StdOut.format ("isPerfectlyBalancedS() = %b\n", set.isPerfectlyBalancedS()); //StdOut.format ("isPerfectlyBalancedH() = %b\n", set.isPerfectlyBalancedH()); //StdOut.format ("isOddBalanced() = %b\n", set.isOddBalanced()); //StdOut.format ("isSemiBalanced() = %b\n", set.isSemiBalanced()); StdOut.format ("sizeAtHeight(2) = %d\n", set.sizeAtHeight(2)); StdOut.format ("sizeAboveHeight(2) = %d\n", set.sizeAboveHeight(2)); StdOut.format ("sizeBelowHeight(2) = %d\n", set.sizeBelowHeight(2)); //set = MyIntSET2.fromString(s); set.removeOddSubtrees(); StdOut.format ("removeOddSubtrees() %s\n", set); show(set, "removeOddSubtrees"); //set = MyIntSET2.fromString(s); set.removeBelowDepth(2); StdOut.format ("removeBelowDepth(2) %s\n", set); show(set, "removeBelowDepth2"); //set = MyIntSET2.fromString(s); set.removeLeaves(); StdOut.format ("removeLeaves() %s\n", set); show(set, "removeLeaves"); //set = MyIntSET2.fromString(s); set.removeSingles(); StdOut.format ("removeSingles() %s\n", set); show(set, "removeSingles"); //set = MyIntSET2.fromString(s); set.addZeroToSingles(); StdOut.format ("addZeroToSingles() %s\n", set); show(set, "addZeroToSingles"); set = MyIntSET2.fromString(s); set.removeHeight(2); StdOut.format ("removeHeight(2) %s\n", set); show(set, "removeHeight2"); } public static void main(String[] args) { test ("90 30 100 10 80 20 40 60 50 70"); //test ("40 20 60 10 30 50 70"); //test (""); //test ("1"); //test ("41 21 61 11 31"); //test ("41 21 61 11 31 51 71 111"); //test ("101 41 21 61 11 31 51 71 111"); //test ("101 41 21 61 11 31 51 71 141 121 161 111 131 151 171 "); //test ("101 40 20 61 11 31 51 71 140 120 161 111 131 151 171 "); //test ("90 30 100 10 81 20 40 60 50 70 62 63 64"); //test ("40 20 61 10 30 50 70"); //test ("41 21 61 11 30 51 70"); //test (""); //test ("1"); //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"); } }