package algs32;
import algs13.Queue;
import stdlib.*;
/* ***********************************************************************
* A simple BST with int keys
*
* Recall that:
* Depth of root==0.
* Height of leaf==0.
* Size of empty tree==0.
* Height of empty tree=-1.
*
* TODO: complete the functions in this file.
*
* Restrictions:
* - DO NOT change the Node class.
* - DO NOT change the first line of any function: name, parameters, types.
* - you may add new functions, but don't delete anything
* - functions must be recursive, except printLeftI
* - no loops, except in printLeftI (you cannot use "while" "for" etc...)
* - no fields (variables declared outside of a function)
* - each function must have exactly one recursive helper function, which you add
* - each function must be independent --- do not call any function other than the helper
* (But you may use Math.max)
*
* See the method testAll for examples that explain the expected behavior.
*************************************************************************/
public class MyIntSET {
private Node root;
private static class Node {
public final int key;
public Node left, right;
public Node(int key) { this.key = key; }
}
// Print only the elements going down the left side of the tree
// in the BST with level order traversal "41 21 61 11 31", this should print "41 21 11"
public void printLeftI () {
// TODO
}
// the number of nodes in the tree
// in the BST with level order traversal "41 21 61 11 31", the size is 5
public int size() {
// TODO
return 0;
}
// Recall the definitions of height and depth.
// in the BST with level order traversal "41 21 61 11 31",
// node 41 has depth 0, height 2
// node 21 has depth 1, height 1
// node 61 has depth 1, height 0
// node 11 has depth 2, height 0
// node 31 has depth 2, height 0
// height of the whole tree is the height of the root
// the height of the tree
public int height() {
// TODO
return 0;
}
// the number of nodes with odd keys
public int sizeOdd() {
// TODO
return 0;
}
// The next three functions compute the size of the tree at depth k.
// It should be the case that for any given k,
//
// sizeAbove(k) + sizeAt(k) + sizeBelow(k) = size()
//
// The words "above" and "below" assume that the root is at the "top".
//
// Suppose we have with size N and height H (so max depth also H).
// For such a tree, we expect
//
// sizeAboveDepth (-1) = 0
// sizeAtDepth (-1) = 0
// sizeBelowDepth (-1) = N
//
// sizeAboveDepth (0) = 0
// sizeAtDepth (0) = 1
// sizeBelowDepth (0) = N-1
//
// sizeAboveDepth (H+1) = N
// sizeAtDepth (H+1) = 0
// sizeBelowDepth (H+1) = 0
//
// the number of nodes in the tree, at exactly depth k
// include node n if depth(n) == k
public int sizeAtDepth(int k) {
// TODO
return 0;
}
// the number of nodes in the tree, "above" depth k (not including k)
// include node n if depth(n) k
public int sizeBelowDepth(int k) {
// TODO
return 0;
}
// tree is perfect if for every node, size of left == size of right
// hint: in the helper, return -1 if the tree is not perfect, otherwise return the size
public boolean isPerfectlyBalancedS() {
// TODO
return false;
}
// tree is perfect if for every node, height of left == height of right
// hint: in the helper, return -2 if the tree is not perfect, otherwise return the height
public boolean isPerfectlyBalancedH() {
// TODO
return false;
}
// tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right
// A node is odd if it has an odd key
// hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size
public boolean isOddBalanced() {
// TODO
return false;
}
// tree is semi-perfect if every node is semi-perfect
// A node with 0 children is semi-perfect.
// A node with 1 child is NOT semi-perfect.
// A node with 2 children is semi-perfect if (size-of-larger-sized-child n.key) n.right = put(n.right, key);
return n;
}
// Test for equality
public static boolean areEquals (MyIntSET a, MyIntSET b) { return areEquals(a.root, b.root); }
private static boolean areEquals (Node x, Node y) {
if (x == null) {
return (y == null);
} else {
return (y != null) x.key == y.key areEquals (x.left, y.left) areEquals (x.right, y.right);
}
}
// Create a tree from a string
public static MyIntSET fromString (String ints) {
MyIntSET set = new MyIntSET ();
for (String s : ints.split (" "))
try { set.put (Integer.parseInt (s)); } catch (NumberFormatException e) {}
return set;
}
// Return the values of the tree in level order
public Iterable levelOrder() {
Queue keys = new Queue 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;
}
// String representation of the tree
public String toString() {
StringBuilder sb = new StringBuilder();
for (int key: levelOrder())
sb.append (key + " ");
return sb.toString ();
}
// Graphical representation of the tree
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);
}
}