001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
package algs32;
import algs13.Queue;
import stdlib.*;

/* ***********************************************************************
 * A simple BST with int keys and no values
 *
 * Complete each function below.
 * Write each function as a separate recursive definition (do not use more than one helper per function).
 * Depth of root==0.
 * Height of leaf==0.
 * Size of empty tree==0.
 * Height of empty tree=-1.
 *************************************************************************/
public class MyIntSET2 {
  private Node root;
  private static class Node {
    public final int key;
    public Node left, right;
    public int H;
    public Node(int key) { this.key = key; }
  }

  // The field "H" indicates the height of each node.
  // You must then modify "put" to update the height of each node.
  // "removeHeight" should also update the field "H".

  // the number of nodes in the tree, at exactly height k
  // include node n if height(n) == k
  public int sizeAtHeight(int k) { return 0; }

  // the number of nodes in the tree, above height k (not including k)
  // include node n if height(n) > k
  public int sizeAboveHeight(int k) { return 0; }

  // the number of nodes in the tree, below height k (not including k)
  // include node n if height(n) < k
  public int sizeBelowHeight(int k) { return 0; }

  // remove all subtrees of height k from the original tree
  public void removeHeight(int k) {}

  /* ***************************************************************************
   * Some methods to create and display trees
   *****************************************************************************/

  // Modify "put" to update the field "H".
  public void put(int key) { root = put(root, key); }
  private Node put(Node n, int key) {
    if (n == null) return new Node(key);
    if      (key < n.key) n.left  = put(n.left,  key);
    else if (key > n.key) n.right = put(n.right, key);
    return n;
  }
  // Do not modify "copy"
  public MyIntSET2 copy () {
    MyIntSET2 that = new MyIntSET2 ();
    for (int key : levelOrder())
      that.put (key);
    return that;
  }
  // Do not modify "levelOrder"
  public Iterable<Integer> levelOrder() {
    Queue<Integer> keys = new Queue<>();
    Queue<Node> queue = new Queue<>();
    queue.enqueue(root);
    while (!queue.isEmpty()) {
      Node n = queue.dequeue();
      if (n == null) continue;
      keys.enqueue(n.key);
      queue.enqueue(n.left);
      queue.enqueue(n.right);
    }
    return keys;
  }
  // Do not modify "toString"
  public String toString() {
    StringBuilder sb = new StringBuilder();
    for (int key: levelOrder())
      sb.append (key + " ");
    return sb.toString ();
  }
  // You may modify "toGraphviz" if you wish
  public void toGraphviz(String filename) {
    GraphvizBuilder gb = new GraphvizBuilder ();
    toGraphviz (gb, null, root);
    gb.toFileUndirected (filename, "ordering=\"out\"");
  }
  private static void toGraphviz (GraphvizBuilder gb, Node parent, Node n) {
    if (n == null) { gb.addNullEdge (parent); return; }
    gb.addLabeledNode (n, Integer.toString (n.key));
    if (parent != null) gb.addEdge (parent, n);
    toGraphviz (gb, n, n.left);
    toGraphviz (gb, n, n.right);
  }

  // You may modify "drawTree" if you wish
  public void drawTree() {
    if (root != null) {
      StdDraw.setPenColor (StdDraw.BLACK);
      StdDraw.setCanvasSize(1200,700);
      drawTree(root, .5, 1, .25, 0);
    }
  }
  private static void drawTree (Node n, double x, double y, double range, int depth) {
    int CUTOFF = 5;
    StdDraw.text (x, y, Integer.toString (n.key));
    StdDraw.setPenRadius (.007);
    if (n.left != null && depth != CUTOFF) {
      StdDraw.line (x-range, y-.13, x-.01, y-.01);
      drawTree (n.left, x-range, y-.15, range*.5, depth+1);
    }
    if (n.right != null && depth != CUTOFF) {
      StdDraw.line (x+range, y-.13, x+.01, y-.01);
      drawTree (n.right, x+range, y-.15, range*.5, depth+1);
    }
  }
  /* ***************************************************************************
   *  Test client
   *  You can modify any of these methods, if you wish
   *****************************************************************************/
  // create a tree from a string
  public static MyIntSET2 fromString (String ints) {
    MyIntSET2 set = new MyIntSET2 ();
    for (String s : ints.split (" "))
      try { set.put (Integer.parseInt (s)); } catch (NumberFormatException e) {}
    return set;
  }
  private static int exampleCount = 0;
  public static void show(MyIntSET2 set, String filename) {
    // comment out the next line to stop drawing the trees
    //        set.drawTree (); StdDraw.show (2000);
    exampleCount++;
    set.toGraphviz ("x" + exampleCount + "-" + filename + ".png");
  }
  public static void test(String s) {
    MyIntSET2 set = MyIntSET2.fromString(s);
    StdOut.println ("###############################################################");
    StdOut.format ("tree: %s\n", set); show(set, "original");

    //StdOut.format ("size()                 = %d\n", set.size());
    //StdOut.format ("height()               = %d\n", set.height());
    //StdOut.format ("sizeOdd()              = %d\n", set.sizeOdd());
    //StdOut.format ("sizeAtDepth(2)         = %d\n", set.sizeAtDepth(2));
    //StdOut.format ("sizeAboveDepth(2)      = %d\n", set.sizeAboveDepth(2));
    //StdOut.format ("sizeBelowDepth(2)      = %d\n", set.sizeBelowDepth(2));
    //StdOut.format ("isPerfectlyBalancedS() = %b\n", set.isPerfectlyBalancedS());
    //StdOut.format ("isPerfectlyBalancedH() = %b\n", set.isPerfectlyBalancedH());
    //StdOut.format ("isOddBalanced()        = %b\n", set.isOddBalanced());
    //StdOut.format ("isSemiBalanced()       = %b\n", set.isSemiBalanced());
    StdOut.format ("sizeAtHeight(2)        = %d\n", set.sizeAtHeight(2));
    StdOut.format ("sizeAboveHeight(2)     = %d\n", set.sizeAboveHeight(2));
    StdOut.format ("sizeBelowHeight(2)     = %d\n", set.sizeBelowHeight(2));
    
    //set = MyIntSET2.fromString(s); set.removeOddSubtrees(); StdOut.format ("removeOddSubtrees()  %s\n", set); show(set, "removeOddSubtrees");
    //set = MyIntSET2.fromString(s); set.removeBelowDepth(2); StdOut.format ("removeBelowDepth(2)  %s\n", set); show(set, "removeBelowDepth2");
    //set = MyIntSET2.fromString(s); set.removeLeaves();      StdOut.format ("removeLeaves()       %s\n", set); show(set, "removeLeaves");
    //set = MyIntSET2.fromString(s); set.removeSingles();     StdOut.format ("removeSingles()      %s\n", set); show(set, "removeSingles");
    //set = MyIntSET2.fromString(s); set.addZeroToSingles();  StdOut.format ("addZeroToSingles()   %s\n", set); show(set, "addZeroToSingles");
    set = MyIntSET2.fromString(s); set.removeHeight(2);     StdOut.format ("removeHeight(2)      %s\n", set); show(set, "removeHeight2");
  }
  public static void main(String[] args) {
    test ("90 30 100 10 80 20 40 60 50 70");
    //test ("40 20 60 10 30 50 70");
    //test ("");
    //test ("1");
    //test ("41 21 61 11 31");
    //test ("41 21 61 11 31 51 71 111");
    //test ("101 41 21 61 11 31 51 71 111");
    //test ("101 41 21 61 11 31 51 71 141 121 161 111 131 151 171 ");
    //test ("101 40 20 61 11 31 51 71 140 120 161 111 131 151 171 ");
    //test ("90 30 100 10 81 20 40 60 50 70 62 63 64");
    //test ("40 20 61 10 30 50 70");
    //test ("41 21 61 11 30 51 70");
    //test ("");
    //test ("1");
    //test ("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");

  }
}