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}