001package algs13;
002
003import java.util.Scanner;
004import stdlib.*;
005
006// A Playground for binary trees
007
008public class XBTree {
009        static class BNode {
010                public BNode (double item, BNode left, BNode right) {
011                        this.item = item;
012                        this.left = left;
013                        this.right = right;
014                }
015                public double item;
016                public BNode left;
017                public BNode right;
018        }
019        BNode root;
020
021        // height/depth of empty tree is -1
022        // height/depth of singleton tree is 0
023        public int height () {
024                //TODO
025                return StdRandom.uniform (100);
026        }
027        public int depth () {
028                //TODO
029                return StdRandom.uniform (100);
030        }       
031        public int depthOfShallowestFive () {
032                //TODO
033                return StdRandom.uniform (100);
034        }
035        public int heightOfShortestFive () {
036                //TODO
037                return StdRandom.uniform (100);
038        }
039
040
041        // prefix with parenthesis
042        public String toString () {
043                StringBuilder sb = new StringBuilder ();
044                toString (sb, root);
045                return sb.toString ();
046        }
047        private static void toString (StringBuilder sb, BNode n) {
048                if (n == null) {
049                        sb.append ("X ");                       
050                } else if (n.left == null && n.right == null) {
051                        sb.append (n.item);
052                        sb.append (" ");
053                } else {
054                        sb.append ("( ");
055                        sb.append (n.item);
056                        sb.append (" ");
057                        toString (sb, n.left);                  
058                        toString (sb, n.right);                 
059                        sb.append (") ");
060                }
061        }
062        public void toGraphviz (String filename) {
063                GraphvizBuilder gb = new GraphvizBuilder ();
064                toGraphviz (gb, null, root);
065                gb.toFileUndirected (filename, "ordering=\"out\"");
066        }
067        private static void toGraphviz (GraphvizBuilder gb, BNode parent, BNode n) {
068                if (n == null) {
069                        gb.addNullEdge (parent);
070                        return;
071                }
072                gb.addLabeledNode (n, Double.toString (n.item));
073                if (parent != null) gb.addEdge (parent, n);
074                toGraphviz (gb, n, n.left);
075                toGraphviz (gb, n, n.right);
076        }
077
078        public static XBTree randomTree (double chanceOfNull, int maxDepth) {
079                XBTree result = new XBTree ();
080                result.root = randomTreeHelper (chanceOfNull, maxDepth, 0);
081                return result;
082        }
083        private static BNode randomTreeHelper (double chanceOfNull, int maxDepth, int depth) {
084                if (depth > maxDepth || StdRandom.uniform () < chanceOfNull * depth) 
085                        return null;
086                BNode left = randomTreeHelper (chanceOfNull, maxDepth, depth+1);
087                BNode right = randomTreeHelper (chanceOfNull, maxDepth, depth+1);
088                double val = StdRandom.uniform (10);
089                return new BNode (val, left, right);
090        }
091
092        // Parses the following kinds of tree "T"
093        // T ::= "X" -- empty
094        // T ::= num -- a node with no children
095        // T ::= ( num T T ) -- a node with children
096        // For example: ( 0 ( 01 12 X ) 02 )
097        public static XBTree from (String in) {
098                Scanner sc = new Scanner (in);
099                XBTree result = new XBTree ();
100                result.root = ofHelper (sc);
101                return result;
102        }
103        private static BNode ofHelper (Scanner sc) {
104                BNode result = null;
105                if (sc.hasNext ("X")) {                 
106                        sc.next (); // gobble "X"
107                }
108                if (sc.hasNextDouble ()) {
109                        double val = sc.nextDouble ();
110                        result = new BNode (val, null, null);
111                } else if (sc.hasNext ("\\(")) {
112                        sc.next (); // gobble "("
113                        double val = sc.nextDouble ();
114                        result = new BNode (val, null, null);
115                        result.left = ofHelper (sc);
116                        result.right = ofHelper (sc);
117                        sc.next ("\\)"); //gobble ")"
118                } 
119                return result;
120        }
121        private static int count = 0;
122        private static void testHeightOfShortestFive (XBTree tree, int expected) {
123                int actual = tree.heightOfShortestFive ();
124                if (!DEBUG && expected != actual) {
125                        //if (!DEBUG && ((expected >= 0 && expected != actual) || (expected < 0 && actual > 0))) {
126                        count++;
127                        tree.toGraphviz ("error" + count + ".png");
128                        StdOut.format ("error%d.heightOfShortestFive: expected=%d, actual=%d\n", count, expected, actual);
129                }
130        }
131        private static void testDepthOfShallowestFive (XBTree tree, int expected) {
132                int actual = tree.depthOfShallowestFive ();
133                if (!DEBUG && expected != actual) {
134                        count++;
135                        tree.toGraphviz ("error" + count + ".png");
136                        StdOut.format ("error%d.depthOfShallowestFive: expected=%d, actual=%d\n", count, expected, actual);
137                }
138        }
139
140        public static boolean DEBUG = false;
141        public static XBTree demoTree () {
142                String sl = "( 0 ( 0 X ( 0 ( 0 X ( 0 X X ) ) X ) ) ( 0 X ( 0 X X ) ) )";
143                String sr = "( 0 ( 0 ( 0 ( 0 X X ) ( 0 X X ) ) ( 0 X ( 0 ( 0 X X ) X ) ) ) ( 0 ( 0 X X ) X ) )";
144                String s = "( 0 " + sl + " " + sr + " )";
145                return XBTree.from (s);
146        }
147        public static void main (String[] args) {
148                if (DEBUG) {
149                        Trace.drawStepsOfMethod("main");
150                        Trace.drawStepsOfMethod("depth");
151                        Trace.drawStepsOfMethod("height");
152                        Trace.drawStepsOfMethod("depthOfShallowestFive");
153                        Trace.drawStepsOfMethod("heightOfShortestFive");
154                        Trace.run (); 
155                        XBTree t0 = demoTree();
156                        t0.root.right.right.item = 5.0;
157                        testDepthOfShallowestFive(t0, 2);
158                        return;
159                }
160                {
161                        XBTree t0 = demoTree();                 
162                        testDepthOfShallowestFive(t0, -1);
163                        t0.root.right.left.right.left.left.item = 5.0;
164                        testDepthOfShallowestFive(t0, 5);
165                        t0.root.left.left.left.left.left.item = 5.0;
166                        testDepthOfShallowestFive(t0, 5);
167                        t0.root.left.left.left.left.item = 5.0;
168                        testDepthOfShallowestFive(t0, 4);
169                        t0.root.right.left.right.item = 5.0;
170                        testDepthOfShallowestFive(t0, 3);
171                        t0.root.right.right.item = 5.0;
172                        testDepthOfShallowestFive(t0, 2);
173                        t0.root.left.item = 5.0;
174                        testDepthOfShallowestFive(t0, 1);
175                        t0.root.item = 5.0;
176                        testDepthOfShallowestFive(t0, 0);
177                }
178                {
179                        XBTree t1 = demoTree();                 
180                        testHeightOfShortestFive(t1, -7);
181                        t1.root.item = 5.0;
182                        testHeightOfShortestFive(t1, 5);
183                        t1.root.left.item = 5.0;
184                        testHeightOfShortestFive(t1, 4);
185                        t1.root.right.item = 5.0;
186                        testHeightOfShortestFive(t1, 4);                
187                        t1.root.right.left.item = 5.0;
188                        testHeightOfShortestFive(t1, 3);
189                        t1.root.left.left.left.item = 5.0;
190                        testHeightOfShortestFive(t1, 2);
191                        t1.root.left.left.left.left.item = 5.0;
192                        testHeightOfShortestFive(t1, 1);
193                        t1.root.right.left.right.left.left.item = 5.0;
194                        testHeightOfShortestFive(t1, 0);
195                }
196                {
197                        XBTree t2 = demoTree();                 
198                        t2.root.left.left.left.left.item = 5.0;
199                        t2.root.right.right.item = 5.0;
200                        t2.toGraphviz ("t2.png");               
201                        StdOut.format ("t2: %s\n", t2);
202                        StdOut.format ("%d = t2.depth()\n", t2.depth ());
203                        StdOut.format ("%d = t2.height()\n", t2.height ());
204                        StdOut.format ("%d = t2.depthOfShallowestFive()\n", t2.depthOfShallowestFive ());
205                        StdOut.format ("%d = t2.heightOfShortestFive()\n", t2.heightOfShortestFive ());
206                }
207
208                int NUM_RANDOM = 10;
209                for (int i=0; i<NUM_RANDOM; i++) {
210                        XBTree t3 = randomTree (0.11, StdRandom.uniform(3, 9));
211                        t3.toGraphviz ("t3" + i + ".png");
212                        StdOut.format ("t3: %s\n", t3);                 
213                        StdOut.format ("%d = t3.depth()\n", t3.depth ());
214                        StdOut.format ("%d = t3.height()\n", t3.height ());
215                        StdOut.format ("%d = t3.depthOfShallowestFive()\n", t3.depthOfShallowestFive ());
216                        StdOut.format ("%d = t3.heightOfShortestFive()\n", t3.heightOfShortestFive ());
217                }
218                StdOut.println ("Finished tests");
219        }
220}