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}