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}