001package algs32; 002import algs13.Queue; 003import stdlib.*; 004 005/* *********************************************************************** 006 * A simple BST with int keys 007 * 008 * Recall that: 009 * Depth of root==0. 010 * Height of leaf==0. 011 * Size of empty tree==0. 012 * Height of empty tree=-1. 013 * 014 * TODO: complete the functions in this file. 015 * 016 * Restrictions: 017 * - DO NOT change the Node class. 018 * - DO NOT change the first line of any function: name, parameters, types. 019 * - you may add new functions, but don't delete anything 020 * - functions must be recursive, except printLeftI 021 * - no loops, except in printLeftI (you cannot use "while" "for" etc...) 022 * - no fields (variables declared outside of a function) 023 * - each function must have exactly one recursive helper function, which you add 024 * - each function must be independent --- do not call any function other than the helper 025 * (But you may use Math.max) 026 * 027 * See the method testAll for examples that explain the expected behavior 028 *************************************************************************/ 029public class MyIntSET { 030 private Node root; 031 private static class Node { 032 public final int key; 033 public Node left, right; 034 public Node(int key) { this.key = key; } 035 } 036 037 // Print only the elements going down the left side of the tree 038 // in the BST with level order traversal "41 21 61 11 31", this should print "41 21 11" 039 public void printLeftI () { 040 // TODO 041 } 042 043 // the number of nodes in the tree 044 // in the BST with level order traversal "41 21 61 11 31", the size is 5 045 public int size() { 046 // TODO 047 return 0; 048 } 049 050 // Recall the definitions of height and depth. 051 // in the BST with level order traversal "41 21 61 11 31", 052 // node 41 has depth 0, height 2 053 // node 21 has depth 1, height 1 054 // node 61 has depth 1, height 0 055 // node 11 has depth 2, height 0 056 // node 31 has depth 2, height 0 057 // height of the whole tree is the height of the root 058 059 // the height of the tree 060 public int height() { 061 // TODO 062 return 0; 063 } 064 065 // the number of nodes with odd keys 066 public int sizeOdd() { 067 // TODO 068 return 0; 069 } 070 071 // The next three functions compute the size of the tree at depth k. 072 // It should be the case that for any given k, 073 // 074 // sizeAbove(k) + sizeAt(k) + sizeBelow(k) = size() 075 // 076 // The words "above" and "below" assume that the root is at the "top". 077 // 078 // Suppose we have with size N and height H (so max depth also H). 079 // For such a tree, we expect 080 // 081 // sizeAboveDepth (-1) = 0 082 // sizeAtDepth (-1) = 0 083 // sizeBelowDepth (-1) = N 084 // 085 // sizeAboveDepth (0) = 0 086 // sizeAtDepth (0) = 1 087 // sizeBelowDepth (0) = N-1 088 // 089 // sizeAboveDepth (H+1) = N 090 // sizeAtDepth (H+1) = 0 091 // sizeBelowDepth (H+1) = 0 092 // 093 // the number of nodes in the tree, at exactly depth k 094 // include node n if depth(n) == k 095 public int sizeAtDepth(int k) { 096 // TODO 097 return 0; 098 } 099 100 // the number of nodes in the tree, "above" depth k (not including k) 101 // include node n if depth(n) < k 102 public int sizeAboveDepth(int k) { 103 // TODO 104 return 0; 105 } 106 107 // the number of nodes in the tree, "below" depth k (not including k) 108 // include node n if depth(n) > k 109 public int sizeBelowDepth(int k) { 110 // TODO 111 return 0; 112 } 113 114 // tree is perfect if for every node, size of left == size of right 115 // hint: in the helper, return -1 if the tree is not perfect, otherwise return the size 116 public boolean isPerfectlyBalancedS() { 117 // TODO 118 return false; 119 } 120 121 // tree is perfect if for every node, height of left == height of right 122 // hint: in the helper, return -2 if the tree is not perfect, otherwise return the height 123 public boolean isPerfectlyBalancedH() { 124 // TODO 125 return false; 126 } 127 128 // tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right 129 // A node is odd if it has an odd key 130 // hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size 131 public boolean isOddBalanced() { 132 // TODO 133 return false; 134 } 135 136 // tree is semi-perfect if every node is semi-perfect 137 // A node with 0 children is semi-perfect. 138 // A node with 1 child is NOT semi-perfect. 139 // A node with 2 children is semi-perfect if (size-of-larger-sized-child <= size-of-smaller-sized-child * 3) 140 // Here, larger and smaller have to do with the SIZE of the children, not the key values. 141 // hint: in the helper, return -1 if the tree is not semi-perfect, otherwise return the size 142 public boolean isSemiBalanced() { 143 // TODO 144 return false; 145 } 146 147 /* 148 * Mutator functions 149 * HINT: all of these are easier to write if the helper function returns Node, rather than void. 150 */ 151 152 // remove all subtrees with odd roots (if node is odd, remove it and its descendants) 153 // A node is odd if it has an odd key 154 // If the root is odd, then you should end up with the empty tree 155 public void removeOddSubtrees () { 156 // TODO 157 } 158 159 // remove all subtrees below depth k from the original tree 160 public void removeBelowDepth(int k) { 161 // TODO 162 } 163 164 // add a child with key=0 to all nodes that have only one child 165 // (you do not need to retain symmetric order or uniqueness of keys, obviously) 166 public void addZeroToSingles() { 167 // TODO 168 } 169 170 // remove all leaves from the original tree 171 // if you start with "41", then the result is the empty tree. 172 // if you start with "41 21 61", then the result is the tree "41" 173 // if you start with the BST "41 21 11 1", then the result is the tree "41 21 11" 174 // if you start with the BST "41 21 61 11", then the result is the tree "41 21" 175 // Hint: This requires that you check for "leafiness" before the recursive calls 176 public void removeLeaves() { 177 // TODO 178 } 179 180 // remove all nodes that have only one child by "promoting" that child 181 // repeat this recursively as you go up, so the final result should have no nodes with only one child 182 // if you start with "41", the tree is unchanged. 183 // if you start with "41 21 61", the tree is unchanged. 184 // if you start with the BST "41 21 11 1", then the result is the tree "1" 185 // if you start with the BST "41 21 61 11", then the result is the tree "41 11 61" 186 // Hint: This requires that you check for "singleness" after the recursive calls 187 public void removeSingles() { 188 // TODO 189 } 190 191 /* *************************************************************************** 192 * Test client 193 * You can modify any of these methods, if you wish 194 *****************************************************************************/ 195 public static void main(String[] args) { 196 testOne (); 197 testAccessors (); 198 testMutators (); 199 StdOut.println ("Finished Tests"); 200 } 201 private static void testOne () { 202 Trace.drawStepsOfMethod ("printLeftI"); 203 Trace.run (); 204 MyIntSET set1 = MyIntSET.fromString("41 21 61 11 31"); 205 set1.printLeftI (); 206 //MyIntSET set2 = MyIntSET.fromString ("41 21 61 11 31 51 71 111"); 207 //show (set1, "set1"); 208 //show (set2, "set2"); 209 } 210 private static void testAccessors () { 211 testSize (5, "41 21 61 11 31"); 212 testSize (8, "41 21 61 11 31 51 71 111"); 213 testSize (9, "101 41 21 61 11 31 51 71 111"); 214 testSize (15, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 215 testSize (11, "101 41 21 61 11 31 51 71 141 121 161"); 216 testSize (9, "101 41 21 61 11 31 51 71 141"); 217 testSize (15, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 218 testSize (13, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 219 testSize (7, "40 20 61 10 30 50 70"); 220 testSize (7, "41 21 61 11 30 51 70"); 221 testSize (0, ""); 222 testSize (1, "1"); 223 testSize (35, "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"); 224 225 testHeight (2, "41 21 61 11 31"); 226 testHeight (3, "41 21 61 11 31 51 71 111"); 227 testHeight (3, "101 41 21 61 11 31 51 71 111"); 228 testHeight (3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 229 testHeight (3, "101 41 21 61 11 31 51 71 141 121 161"); 230 testHeight (3, "101 41 21 61 11 31 51 71 141"); 231 testHeight (3, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 232 testHeight (8, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 233 testHeight (2, "40 20 61 10 30 50 70"); 234 testHeight (2, "41 21 61 11 30 51 70"); 235 testHeight (-1, ""); 236 testHeight (0, "1"); 237 testHeight (5, "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"); 238 239 testSizeOdd (5, "41 21 61 11 31"); 240 testSizeOdd (8, "41 21 61 11 31 51 71 111"); 241 testSizeOdd (9, "101 41 21 61 11 31 51 71 111"); 242 testSizeOdd (15, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 243 testSizeOdd (11, "101 41 21 61 11 31 51 71 141 121 161"); 244 testSizeOdd (9, "101 41 21 61 11 31 51 71 141"); 245 testSizeOdd (11, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 246 testSizeOdd (2, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 247 testSizeOdd (1, "40 20 61 10 30 50 70"); 248 testSizeOdd (5, "41 21 61 11 30 51 70"); 249 testSizeOdd (0, ""); 250 testSizeOdd (1, "1"); 251 testSizeOdd (0, "2"); 252 testSizeOdd (11, "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"); 253 254 testSizeAtDepth (2, 2, "41 21 61 11 31"); 255 testSizeAtDepth (4, 2, "41 21 61 11 31 51 71 111"); 256 testSizeAtDepth (2, 2, "101 41 21 61 11 31 51 71 111"); 257 testSizeAtDepth (8, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 258 testSizeAtDepth (0, 4, "101 41 21 61 11 31 51 71 141 121 161"); 259 testSizeAtDepth (2, 2, "101 41 21 61 11 31 51 71 141"); 260 testSizeAtDepth (4, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 261 testSizeAtDepth (2, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 262 testSizeAtDepth (4, 2, "40 20 61 10 30 50 70"); 263 testSizeAtDepth (2, 1, "41 21 61 11 30 51 70"); 264 testSizeAtDepth (0, 2, ""); 265 testSizeAtDepth (0, 2, "1"); 266 testSizeAtDepth (4, 5, "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"); 267 268 testSizeAboveDepth (3, 2, "41 21 61 11 31"); 269 testSizeAboveDepth (3, 2, "41 21 61 11 31 51 71 111"); 270 testSizeAboveDepth (3, 2, "101 41 21 61 11 31 51 71 111"); 271 testSizeAboveDepth (7, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 272 testSizeAboveDepth (11, 4, "101 41 21 61 11 31 51 71 141 121 161"); 273 testSizeAboveDepth (3, 2, "101 41 21 61 11 31 51 71 141"); 274 testSizeAboveDepth (3, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 275 testSizeAboveDepth (5, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 276 testSizeAboveDepth (3, 2, "40 20 61 10 30 50 70"); 277 testSizeAboveDepth (1, 1, "41 21 61 11 30 51 70"); 278 testSizeAboveDepth (0, 2, ""); 279 testSizeAboveDepth (1, 2, "1"); 280 testSizeAboveDepth (31, 5, "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"); 281 282 testSizeBelowDepth (0, 2, "41 21 61 11 31"); 283 testSizeBelowDepth (1, 2, "41 21 61 11 31 51 71 111"); 284 testSizeBelowDepth (4, 2, "101 41 21 61 11 31 51 71 111"); 285 testSizeBelowDepth (0, 3, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 286 testSizeBelowDepth (0, 4, "101 41 21 61 11 31 51 71 141 121 161"); 287 testSizeBelowDepth (4, 2, "101 41 21 61 11 31 51 71 141"); 288 testSizeBelowDepth (8, 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 289 testSizeBelowDepth (6, 3, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 290 testSizeBelowDepth (0, 2, "40 20 61 10 30 50 70"); 291 testSizeBelowDepth (4, 1, "41 21 61 11 30 51 70"); 292 testSizeBelowDepth (0, 2, ""); 293 testSizeBelowDepth (0, 2, "1"); 294 testSizeBelowDepth (0, 5, "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"); 295 296 testIsPerfectlyBalancedS (false, "100 40 140 20 120"); 297 testIsPerfectlyBalancedS (true, "17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32"); 298 testIsPerfectlyBalancedS (false, "17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32"); 299 testIsPerfectlyBalancedS (false, "16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 5 9 13 17 21 25 29"); 300 testIsPerfectlyBalancedS (true, "16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31"); 301 testIsPerfectlyBalancedS (false, "41 21 61 11 31"); 302 testIsPerfectlyBalancedS (false, "41 21 61 11 31 51 71 111"); 303 testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 111"); 304 testIsPerfectlyBalancedS (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 305 testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 141 121 161"); 306 testIsPerfectlyBalancedS (false, "101 41 21 61 11 31 51 71 141"); 307 testIsPerfectlyBalancedS (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 308 testIsPerfectlyBalancedS (false, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 309 testIsPerfectlyBalancedS (true, "40 20 61 10 30 50 70"); 310 testIsPerfectlyBalancedS (true, "41 21 61 11 30 51 70"); 311 testIsPerfectlyBalancedS (true, ""); 312 testIsPerfectlyBalancedS (true, "1"); 313 testIsPerfectlyBalancedS (false, "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"); 314 315 testIsPerfectlyBalancedH (false, "100 40 140 20 120"); 316 testIsPerfectlyBalancedH (true, "17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32"); 317 testIsPerfectlyBalancedH (false, "17 9 25 5 13 21 29 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32"); 318 testIsPerfectlyBalancedH (false, "16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 5 9 13 17 21 25 29"); 319 testIsPerfectlyBalancedH (true, "16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31"); 320 testIsPerfectlyBalancedH (false, "41 21 61 11 31"); 321 testIsPerfectlyBalancedH (false, "41 21 61 11 31 51 71 111"); 322 testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 111"); 323 testIsPerfectlyBalancedH (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 324 testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 141 121 161"); 325 testIsPerfectlyBalancedH (false, "101 41 21 61 11 31 51 71 141"); 326 testIsPerfectlyBalancedH (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 327 testIsPerfectlyBalancedH (false, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 328 testIsPerfectlyBalancedH (true, "40 20 61 10 30 50 70"); 329 testIsPerfectlyBalancedH (true, "41 21 61 11 30 51 70"); 330 testIsPerfectlyBalancedH (true, ""); 331 testIsPerfectlyBalancedH (true, "1"); 332 testIsPerfectlyBalancedH (false, "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"); 333 334 testIsOddBalanced (false, "41 21 61 11 31"); 335 testIsOddBalanced (false, "41 21 61 11 71"); 336 testIsOddBalanced (true, "41 21 61 10 30"); 337 testIsOddBalanced (true, "40 21 61"); 338 testIsOddBalanced (true, "41 20 60"); 339 testIsOddBalanced (false, "41 21 61 11 31 51 71 111"); 340 testIsOddBalanced (false, "101 41 21 61 11 31 51 71 111"); 341 testIsOddBalanced (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 342 testIsOddBalanced (false, "101 41 21 61 11 31 51 71 141 121 161"); 343 testIsOddBalanced (false, "101 41 21 61 11 31 51 71 141"); 344 testIsOddBalanced (false, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 345 testIsOddBalanced (false, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 346 testIsOddBalanced (false, "40 20 61 10 30 50 70"); 347 testIsOddBalanced (false, "41 21 61 11 30 51 70"); 348 testIsOddBalanced (true, ""); 349 testIsOddBalanced (true, "1"); 350 testIsOddBalanced (false, "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"); 351 352 testIsSemiBalanced (true, "41 21 61 11 31"); 353 testIsSemiBalanced (false, "41 21 61 11 31 51 71 111"); 354 testIsSemiBalanced (false, "101 41 21 61 11 31 51 71 111"); 355 testIsSemiBalanced (true, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 356 testIsSemiBalanced (true, "101 41 21 61 11 31 51 71 141 121 161"); 357 testIsSemiBalanced (false, "101 41 21 61 11 31 51 71 141"); 358 testIsSemiBalanced (true, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 359 testIsSemiBalanced (false, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 360 testIsSemiBalanced (true, "40 20 61 10 30 50 70"); 361 testIsSemiBalanced (true, "41 21 61 11 30 51 70"); 362 testIsSemiBalanced (true, ""); 363 testIsSemiBalanced (true, "1"); 364 testIsSemiBalanced (true, "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"); 365 } 366 private static void testMutators () { 367 testRemoveOddSubtrees ("", "41 21 61 11 31"); 368 testRemoveOddSubtrees ("", "101 41 21 61 11 31 51 71 141"); 369 testRemoveOddSubtrees ("100 40 140 20 120", "100 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 370 testRemoveOddSubtrees ("90 30 100 10 20", "90 30 100 10 81 20 40 60 50 70 62 63 64"); 371 testRemoveOddSubtrees ("40 20 10 30", "40 20 61 10 30 50 70"); 372 testRemoveOddSubtrees ("", "41 21 61 11 30 51 70"); 373 testRemoveOddSubtrees ("", ""); 374 testRemoveOddSubtrees ("", "1"); 375 testRemoveOddSubtrees ("0", "0"); 376 testRemoveOddSubtrees ("90 30 100 10 80 20 40 12 60 62", "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"); 377 378 testRemoveBelowDepth ("41 21 61 11 31", 2, "41 21 61 11 31"); 379 testRemoveBelowDepth ("41 21 61 11 31 51 71", 2, "41 21 61 11 31 51 71 111"); 380 testRemoveBelowDepth ("101 41 111 21 61", 2, "101 41 21 61 11 31 51 71 111"); 381 testRemoveBelowDepth ("101 41 141 21 61 121 161", 2, "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 382 testRemoveBelowDepth ("101 41 141 21 61 121 161 11 31 51 71", 4, "101 41 21 61 11 31 51 71 141 121 161"); 383 testRemoveBelowDepth ("101 41 141 21 61", 2, "101 41 21 61 11 31 51 71 141"); 384 testRemoveBelowDepth ("101 40 140 20 61 120 161", 2, "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 385 testRemoveBelowDepth ("90 30 100 10 81 20 40", 3, "90 30 100 10 81 20 40 60 50 70 62 63 64"); 386 testRemoveBelowDepth ("40 20 61 10 30 50 70", 2, "40 20 61 10 30 50 70"); 387 testRemoveBelowDepth ("41 21 61", 1, "41 21 61 11 30 51 70"); 388 testRemoveBelowDepth ("", 2, ""); 389 testRemoveBelowDepth ("1", 2, "1"); 390 testRemoveBelowDepth ("90 30 100 10 80 95 105 5 20 40 85 93 97 103 110", 3, "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"); 391 392 testAddZeroToSingles ("41 21 61 11 0 ", "41 21 61 11"); 393 testAddZeroToSingles ("41 21 61 11 0 51 71 ", "41 21 61 11 51 71"); 394 testAddZeroToSingles ("90 30 100 10 81 0 20 40 0 0 60 50 70 62 0 0 63 0 64 ", "90 30 100 10 81 20 40 60 50 70 62 63 64"); 395 testAddZeroToSingles ("40 20 61 10 30 50 70 ", "40 20 61 10 30 50 70"); 396 testAddZeroToSingles ("", ""); 397 testAddZeroToSingles ("1 ", "1"); 398 testAddZeroToSingles ("90 30 100 10 80 95 105 5 20 40 85 93 97 103 110 2 6 12 21 35 60 82 86 92 94 96 98 102 104 106 111 34 36 45 62 ", "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"); 399 400 testRemoveLeaves ("41 21", "41 21 61 11 31"); 401 testRemoveLeaves ("41 21 61 71", "41 21 61 11 31 51 71 111"); 402 testRemoveLeaves ("101 41 21 61", "101 41 21 61 11 31 51 71 111"); 403 testRemoveLeaves ("101 41 141 21 61 121 161", "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 404 testRemoveLeaves ("101 41 141 21 61", "101 41 21 61 11 31 51 71 141 121 161"); 405 testRemoveLeaves ("101 41 21 61", "101 41 21 61 11 31 51 71 141"); 406 testRemoveLeaves ("101 40 140 20 61 120 161", "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 407 testRemoveLeaves ("90 30 10 81 40 60 70 62 63", "90 30 100 10 81 20 40 60 50 70 62 63 64"); 408 testRemoveLeaves ("40 20 61", "40 20 61 10 30 50 70"); 409 testRemoveLeaves ("41 21 61", "41 21 61 11 30 51 70"); 410 testRemoveLeaves ("", ""); 411 testRemoveLeaves ("", "1"); 412 testRemoveLeaves ("90 30 100 10 80 95 105 5 20 40 85 93 97 103 110 35 60", "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"); 413 414 testRemoveSingles ("101 41 141 21 61 121 161 11 31 51 71 111 131 151 171", "101 41 21 61 11 31 51 71 141 121 161 111 131 151 171"); 415 testRemoveSingles ("101 41 141 21 61 121 161 11 31 51 71", "101 41 21 61 11 31 51 71 141 121 161"); 416 testRemoveSingles ("101 41 141 21 61 11 31 51 71", "101 41 21 61 11 31 51 71 141"); 417 testRemoveSingles ("101 40 140 20 61 120 161 11 31 51 71 111 131 151 171", "101 40 20 61 11 31 51 71 140 120 161 111 131 151 171"); 418 testRemoveSingles ("90 30 100 20 60 50 64", "90 30 100 10 81 20 40 60 50 70 62 63 64"); 419 testRemoveSingles ("40 20 61 10 30 50 70", "40 20 61 10 30 50 70"); 420 testRemoveSingles ("41 21 61 11 30 51 70", "41 21 61 11 30 51 70"); 421 testRemoveSingles ("", ""); 422 testRemoveSingles ("1", "1"); 423 testRemoveSingles ("90 30 100 10 80 95 105 5 20 40 85 93 97 103 110 2 6 12 21 35 60 82 86 92 94 96 98 102 104 106 111 34 36 45 62", "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"); 424 } 425 426 private static int exampleCount = 0; 427 private static void show(MyIntSET set, String filename) { 428 StdOut.format ("tree x%s-%s: %s\n", exampleCount, filename, set); 429 set.toGraphviz ("x" + exampleCount + "-" + filename + ".png"); 430 exampleCount++; 431 } 432 private static void testSize (int expected, String tree) { 433 MyIntSET set = MyIntSET.fromString(tree); 434 int actual = set.size (); 435 if (! areEquals (set, MyIntSET.fromString(tree))) { 436 StdOut.format ("Failed size(%s): Tree modified\n", tree); 437 } 438 if (expected != actual) { 439 StdOut.format ("Failed size(%s): Expecting (%d) Actual (%d)\n", tree, expected, actual); 440 } 441 } 442 private static void testHeight (int expected, String tree) { 443 MyIntSET set = MyIntSET.fromString(tree); 444 int actual = set.height (); 445 if (! areEquals (set, MyIntSET.fromString(tree))) { 446 StdOut.format ("Failed height(%s): Tree modified\n", tree); 447 } 448 if (expected != actual) { 449 StdOut.format ("Failed height(%s): Expecting (%d) Actual (%d)\n", tree, expected, actual); 450 } 451 } 452 private static void testSizeOdd (int expected, String tree) { 453 MyIntSET set = MyIntSET.fromString(tree); 454 int actual = set.sizeOdd (); 455 if (! areEquals (set, MyIntSET.fromString(tree))) { 456 StdOut.format ("Failed sizeOdd(%s): Tree modified\n", tree); 457 } 458 if (expected != actual) { 459 StdOut.format ("Failed sizeOdd(%s): Expecting (%d) Actual (%d)\n", tree, expected, actual); 460 } 461 } 462 private static void testSizeAtDepth (int expected, int depth, String tree) { 463 MyIntSET set = MyIntSET.fromString(tree); 464 int actual = set.sizeAtDepth (depth); 465 if (! areEquals (set, MyIntSET.fromString(tree))) { 466 StdOut.format ("Failed sizeAtDepth(%d,%s): Tree modified\n", depth, tree); 467 } 468 if (expected != actual) { 469 StdOut.format ("Failed sizeAtDepth(%d,%s): Expecting (%d) Actual (%d)\n", depth, tree, expected, actual); 470 } 471 } 472 private static void testSizeAboveDepth (int expected, int depth, String tree) { 473 MyIntSET set = MyIntSET.fromString(tree); 474 int actual = set.sizeAboveDepth (depth); 475 if (! areEquals (set, MyIntSET.fromString(tree))) { 476 StdOut.format ("Failed sizeAboveDepth(%d,%s): Tree modified\n", depth, tree); 477 } 478 if (expected != actual) { 479 StdOut.format ("Failed sizeAboveDepth(%d,%s): Expecting (%d) Actual (%d)\n", depth, tree, expected, actual); 480 } 481 } 482 private static void testSizeBelowDepth (int expected, int depth, String tree) { 483 MyIntSET set = MyIntSET.fromString(tree); 484 int actual = set.sizeBelowDepth (depth); 485 if (! areEquals (set, MyIntSET.fromString(tree))) { 486 StdOut.format ("Failed sizeBelowDepth(%d,%s): Tree modified\n", depth, tree); 487 } 488 if (expected != actual) { 489 StdOut.format ("Failed sizeBelowDepth(%d,%s): Expecting (%d) Actual (%d)\n", depth, tree, expected, actual); 490 } 491 } 492 private static void testIsPerfectlyBalancedS (boolean expected, String tree) { 493 MyIntSET set = MyIntSET.fromString(tree); 494 boolean actual = set.isPerfectlyBalancedS (); 495 if (! areEquals (set, MyIntSET.fromString(tree))) { 496 StdOut.format ("Failed isPerfectlyBalancedS(%s): Tree modified\n", tree); 497 } 498 if (expected != actual) { 499 StdOut.format ("Failed isPerfectlyBalancedS(%s): Expecting (%b) Actual (%b)\n", tree, expected, actual); 500 } 501 } 502 private static void testIsPerfectlyBalancedH (boolean expected, String tree) { 503 MyIntSET set = MyIntSET.fromString(tree); 504 boolean actual = set.isPerfectlyBalancedH (); 505 if (! areEquals (set, MyIntSET.fromString(tree))) { 506 StdOut.format ("Failed isPerfectlyBalancedH(%s): Tree modified\n", tree); 507 } 508 if (expected != actual) { 509 StdOut.format ("Failed isPerfectlyBalancedH(%s): Expecting (%b) Actual (%b)\n", tree, expected, actual); 510 } 511 } 512 private static void testIsOddBalanced (boolean expected, String tree) { 513 MyIntSET set = MyIntSET.fromString(tree); 514 boolean actual = set.isOddBalanced (); 515 if (! areEquals (set, MyIntSET.fromString(tree))) { 516 StdOut.format ("Failed isOddBalanced(%s): Tree modified\n", tree); 517 } 518 if (expected != actual) { 519 StdOut.format ("Failed isOddBalanced(%s): Expecting (%b) Actual (%b)\n", tree, expected, actual); 520 } 521 } 522 private static void testIsSemiBalanced (boolean expected, String tree) { 523 MyIntSET set = MyIntSET.fromString(tree); 524 boolean actual = set.isSemiBalanced (); 525 if (! areEquals (set, MyIntSET.fromString(tree))) { 526 StdOut.format ("Failed isSemiBalanced(%s): Tree modified\n", tree); 527 } 528 if (expected != actual) { 529 StdOut.format ("Failed isSemiBalanced(%s): Expecting (%b) Actual (%b)\n", tree, expected, actual); 530 } 531 } 532 private static void testRemoveOddSubtrees (String expected, String tree) { 533 MyIntSET actual = MyIntSET.fromString(tree); 534 actual.removeOddSubtrees (); 535 if (! areEquals (actual, MyIntSET.fromString(expected))) { 536 StdOut.format ("Failed removeOddSubtrees\n"); 537 show (MyIntSET.fromString(tree), "original"); 538 show (actual, "actual"); 539 show (MyIntSET.fromString(expected), "expected"); 540 } 541 } 542 private static void testRemoveBelowDepth (String expected, int depth, String tree) { 543 MyIntSET actual = MyIntSET.fromString(tree); 544 actual.removeBelowDepth (depth); 545 if (! areEquals (actual, MyIntSET.fromString(expected))) { 546 StdOut.format ("Failed removeBelowDepth(%d)\n", depth); 547 show (MyIntSET.fromString(tree), "original"); 548 show (actual, "actual"); 549 show (MyIntSET.fromString(expected), "expected"); 550 } 551 } 552 private static void testRemoveSingles (String expected, String tree) { 553 MyIntSET actual = MyIntSET.fromString(tree); 554 actual.removeSingles (); 555 if (! areEquals (actual, MyIntSET.fromString(expected))) { 556 StdOut.format ("Failed removeSingles\n"); 557 show (MyIntSET.fromString(tree), "original"); 558 show (actual, "actual"); 559 show (MyIntSET.fromString(expected), "expected"); 560 } 561 } 562 private static void testRemoveLeaves(String expected, String tree) { 563 MyIntSET actual = MyIntSET.fromString(tree); 564 actual.removeLeaves(); 565 if (! areEquals (actual, MyIntSET.fromString(expected))) { 566 StdOut.format ("Failed removeLeaves\n"); 567 show (MyIntSET.fromString(tree), "original"); 568 show (actual, "actual"); 569 show (MyIntSET.fromString(expected), "expected"); 570 } 571 } 572 private static void testAddZeroToSingles(String expected, String tree) { 573 MyIntSET actual = MyIntSET.fromString(tree); 574 actual.addZeroToSingles (); 575 if (! expected.equals (actual.toString ())) { 576 StdOut.format ("Failed addZeroToSingles\n"); 577 show (MyIntSET.fromString(tree), "original"); 578 show (actual, "actual"); 579 show (MyIntSET.fromString(expected), "expected"); 580 } 581 } 582 583 /* *************************************************************************** 584 * Some methods to create and display trees 585 * DO NOT MODIFY THESE METHODS 586 *****************************************************************************/ 587 // Add one element to a tree, in BST order 588 public void put(int key) { root = put(root, key); } 589 private static Node put(Node n, int key) { 590 if (n == null) return new Node(key); 591 if (key < n.key) n.left = put(n.left, key); 592 else if (key > n.key) n.right = put(n.right, key); 593 return n; 594 } 595 // Test for equality 596 public static boolean areEquals (MyIntSET a, MyIntSET b) { return areEquals(a.root, b.root); } 597 private static boolean areEquals (Node x, Node y) { 598 if (x == null) { 599 return (y == null); 600 } else { 601 return (y != null) && x.key == y.key && areEquals (x.left, y.left) && areEquals (x.right, y.right); 602 } 603 } 604 // Create a tree from a string 605 public static MyIntSET fromString (String ints) { 606 MyIntSET set = new MyIntSET (); 607 for (String s : ints.split (" ")) 608 try { set.put (Integer.parseInt (s)); } catch (NumberFormatException e) {} 609 return set; 610 } 611 // Return the values of the tree in level order 612 public Iterable<Integer> levelOrder() { 613 Queue<Integer> keys = new Queue<>(); 614 Queue<Node> queue = new Queue<>(); 615 queue.enqueue(root); 616 while (!queue.isEmpty()) { 617 Node n = queue.dequeue(); 618 if (n == null) continue; 619 keys.enqueue(n.key); 620 queue.enqueue(n.left); 621 queue.enqueue(n.right); 622 } 623 return keys; 624 } 625 // String representation of the tree 626 public String toString() { 627 StringBuilder sb = new StringBuilder(); 628 for (int key: levelOrder()) 629 sb.append (key + " "); 630 return sb.toString (); 631 } 632 // Graphical representation of the tree 633 public void toGraphviz(String filename) { 634 GraphvizBuilder gb = new GraphvizBuilder (); 635 toGraphviz (gb, null, root); 636 gb.toFileUndirected (filename, "ordering=\"out\""); 637 } 638 private static void toGraphviz (GraphvizBuilder gb, Node parent, Node n) { 639 if (n == null) { gb.addNullEdge (parent); return; } 640 gb.addLabeledNode (n, Integer.toString (n.key)); 641 if (parent != null) gb.addEdge (parent, n); 642 toGraphviz (gb, n, n.left); 643 toGraphviz (gb, n, n.right); 644 } 645}