001package algs32;
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        // prefix with parenthesis
041        public String toString () {
042                StringBuilder sb = new StringBuilder ();
043                toString (sb, root);
044                return sb.toString ();
045        }
046        private static void toString (StringBuilder sb, BNode n) {
047                if (n == null) {
048                        sb.append ("X ");                       
049                } else if (n.left == null && n.right == null) {
050                        sb.append (n.item);
051                        sb.append (" ");
052                } else {
053                        sb.append ("( ");
054                        sb.append (n.item);
055                        sb.append (" ");
056                        toString (sb, n.left);                  
057                        toString (sb, n.right);                 
058                        sb.append (") ");
059                }
060        }
061        public void toGraphviz (String filename) {
062                GraphvizBuilder gb = new GraphvizBuilder ();
063                toGraphviz (gb, null, root);
064                gb.toFileUndirected (filename, "ordering=\"out\"");
065        }
066        private void toGraphviz (GraphvizBuilder gb, BNode parent, BNode n) {
067                if (n == null) {
068                        gb.addNullEdge (parent);
069                        return;
070                }
071                gb.addLabeledNode (n, Double.toString (n.item));
072                if (parent != null) gb.addEdge (parent, n);
073                toGraphviz (gb, n, n.left);
074                toGraphviz (gb, n, n.right);
075        }
076
077        public static XBTree randomTree (double chanceOfNull, int maxDepth) {
078                XBTree result = new XBTree ();
079                result.root = randomTreeHelper (chanceOfNull, maxDepth, 0);
080                return result;
081        }
082        private static BNode randomTreeHelper (double chanceOfNull, int maxDepth, int depth) {
083                if (depth > maxDepth || StdRandom.uniform () < chanceOfNull * depth) 
084                        return null;
085                BNode left = randomTreeHelper (chanceOfNull, maxDepth, depth+1);
086                BNode right = randomTreeHelper (chanceOfNull, maxDepth, depth+1);
087                double val = StdRandom.uniform (10);
088                return new BNode (val, left, right);
089        }
090        
091        // Parses the following kinds of tree "T"
092        // T ::= "X" -- empty
093        // T ::= num -- a node with no children
094        // T ::= ( num T T ) -- a node with children
095        // For example: ( 0 ( 01 12 X ) 02 )
096        public static XBTree from (String in) {
097                Scanner sc = new Scanner (in);
098                XBTree result = new XBTree ();
099                result.root = ofHelper (sc);
100                return result;
101        }
102        private static BNode ofHelper (Scanner sc) {
103                BNode result = null;
104                if (sc.hasNext ("X")) {                 
105                        sc.next (); // gobble "X"
106                }
107                if (sc.hasNextDouble ()) {
108                        double val = sc.nextDouble ();
109                        result = new BNode (val, null, null);
110                } else if (sc.hasNext ("\\(")) {
111                        sc.next (); // gobble "("
112                        double val = sc.nextDouble ();
113                        result = new BNode (val, null, null);
114                        result.left = ofHelper (sc);
115                        result.right = ofHelper (sc);
116                        sc.next ("\\)"); //gobble ")"
117                } 
118                return result;
119        }
120        private static int count = 0;
121        private static void testHeightOfShortestFive (XBTree tree, int expected) {
122                int actual = tree.heightOfShortestFive ();
123                if (!DEBUG && expected != actual) {
124                        //if (!DEBUG && ((expected >= 0 && expected != actual) || (expected < 0 && actual > 0))) {
125                        count++;
126                        tree.toGraphviz ("error" + count + ".png");
127                        StdOut.format ("error%d.heightOfShortestFive: expected=%d, actual=%d\n", count, expected, actual);
128                }
129        }
130        private static void testDepthOfShallowestFive (XBTree tree, int expected) {
131                int actual = tree.depthOfShallowestFive ();
132                if (!DEBUG && expected != actual) {
133                        count++;
134                        tree.toGraphviz ("error" + count + ".png");
135                        StdOut.format ("error%d.depthOfShallowestFive: expected=%d, actual=%d\n", count, expected, actual);
136                }
137        }
138        
139        public static boolean DEBUG = false;
140        public static XBTree demoTree () {
141                String sl = "( 0 ( 0 X ( 0 ( 0 X ( 0 X X ) ) X ) ) ( 0 X ( 0 X X ) ) )";
142                String sr = "( 0 ( 0 ( 0 ( 0 X X ) ( 0 X X ) ) ( 0 X ( 0 ( 0 X X ) X ) ) ) ( 0 ( 0 X X ) X ) )";
143                String s = "( 0 " + sl + " " + sr + " )";
144                return XBTree.from (s);
145        }
146        public static void main (String[] args) {
147                if (DEBUG) Trace.run (); 
148                
149                XBTree t0 = demoTree();                 
150                testDepthOfShallowestFive(t0, -1);
151                t0.root.right.left.right.left.left.item = 5.0;
152                testDepthOfShallowestFive(t0, 5);
153                t0.root.left.left.left.left.left.item = 5.0;
154                testDepthOfShallowestFive(t0, 5);
155                t0.root.left.left.left.left.item = 5.0;
156                testDepthOfShallowestFive(t0, 4);
157                t0.root.right.left.right.item = 5.0;
158                testDepthOfShallowestFive(t0, 3);
159                t0.root.right.right.item = 5.0;
160                testDepthOfShallowestFive(t0, 2);
161                t0.root.left.item = 5.0;
162                testDepthOfShallowestFive(t0, 1);
163                t0.root.item = 5.0;
164                testDepthOfShallowestFive(t0, 0);
165
166                XBTree t1 = demoTree();                 
167                testHeightOfShortestFive(t1, -7);
168                t1.root.item = 5.0;
169                testHeightOfShortestFive(t1, 5);
170                t1.root.left.item = 5.0;
171                testHeightOfShortestFive(t1, 4);
172                t1.root.right.item = 5.0;
173                testHeightOfShortestFive(t1, 4);                
174                t1.root.right.left.item = 5.0;
175                testHeightOfShortestFive(t1, 3);
176                t1.root.left.left.left.item = 5.0;
177                testHeightOfShortestFive(t1, 2);
178                t1.root.left.left.left.left.item = 5.0;
179                testHeightOfShortestFive(t1, 1);
180                t1.root.right.left.right.left.left.item = 5.0;
181                testHeightOfShortestFive(t1, 0);
182                StdOut.println ("Finished tests");
183                
184//              YBTree t2 = demoTree();                 
185//              t2.toGraphviz ("t2.png");               
186//              StdOut.format ("t2: %s\n", t2);
187//              StdOut.format ("%d = t2.depth()\n", t2.depth ());
188//              StdOut.format ("%d = t2.height()\n", t2.height ());
189//              StdOut.format ("%d = t2.depthOfShallowestFive()\n", t2.depthOfShallowestFive ());
190//              StdOut.format ("%d = t2.heightOfShortestFive()\n", t2.heightOfShortestFive ());
191//              
192//              YBTree t3 = randomTree (0.10, 6);
193//              t3.toGraphviz ("t3.png");
194//              StdOut.format ("t3: %s\n", tree0);                      
195//              StdOut.format ("%d = t3.depth()\n", t3.depth ());
196//              StdOut.format ("%d = t3.height()\n", t3.height ());
197//              StdOut.format ("%d = t3.depthOfShallowestFive()\n", t3.depthOfShallowestFive ());
198//              StdOut.format ("%d = t3.heightOfShortestFive()\n", t3.heightOfShortestFive ());
199        }
200}