import java.io.*; import java.util.*; // for Stack class //////////////////////////////////////////////////////////////// class Node { public int iData; // data item (key) public double dData; // data item public Node leftChild; // this node's left child public Node rightChild; // this node's right child

public void displayNode() // display ourself { System.out.print('{'); System.out.print(iData); System.out.print(", "); System.out.print(dData); System.out.print("} "); }

public boolean isLeaf() { return leftChild == null && rightChild == null; } } // end class Node //////////////////////////////////////////////////////////////// class Tree { private Node root; // first node of tree

// ------------------------------------------------------------- public Tree() // constructor { root = null; } // no nodes in tree yet // ------------------------------------------------------------- public Node find(int key) // find node with given key { // (assumes non-empty tree) Node current = root; // start at root while(current.iData != key) // while no match, { if(key < current.iData) // go left? current = current.leftChild; else // or go right? current = current.rightChild; if(current == null) // if no child, return null; // didn't find it } return current; // found it } // end find() // ------------------------------------------------------------- public int size() { return size(root); } // ------------------------------------------------------------- public int depth() { return depth(root) - 1; } // ------------------------------------------------------------- public void removeLeaves() { root = removeLeaves(root); } /// ------------------------------------------------------------- public int rightMinValue() { return min(root.rightChild); } /// ------------------------------------------------------------- public int leftMaxValue() { return max(root.leftChild); } /// ------------------------------------------------------------- public int maximum() { return max(root); } /// ------------------------------------------------------------- public int minimum() { return min(root); } /// ------------------------------------------------------------- public int min(Node n) { Node current = n; while (current.leftChild != null) { current = current.leftChild; } return current.iData; } /// ------------------------------------------------------------- public int max(Node n) { Node current = n; while (current.rightChild != null) { current = current.rightChild; } return current.iData; } /// ------------------------------------------------------------- public Node removeLeaves(Node node) { if (node.leftChild != null) { if (node.leftChild.isLeaf()) { node.leftChild = null; } else { removeLeaves(node.leftChild); } }

if (node.rightChild != null) { if (node.rightChild.isLeaf()) { node.rightChild = null; } else { removeLeaves(node.rightChild); } }

return node; } // ------------------------------------------------------------- public int depth(Node node) // Finds the depth of a node recursively { if (node == null) return 0; int rightDepth = depth(node.rightChild); int leftDepth = depth(node.leftChild); if (leftDepth > rightDepth) { return leftDepth + 1; } else { return rightDepth + 1; } } // ------------------------------------------------------------- public int size(Node node) // Recursively finds the size of a node { if (node == null) return 0; return (size(node.leftChild) + 1 + size(node.rightChild)); } // ------------------------------------------------------------- public void insert(int id, double dd) { Node newNode = new Node(); // make new node newNode.iData = id; // insert data newNode.dData = dd; if(root==null) // no node in root root = newNode; else // root occupied { Node current = root; // start at root Node parent; while(true) // (exits internally) { parent = current; if(id < current.iData) // go left? { current = current.leftChild; if(current == null) // if end of the line, { // insert on left parent.leftChild = newNode; return; } } // end if go left else // or go right? { current = current.rightChild; if(current == null) // if end of the line { // insert on right parent.rightChild = newNode; return; } } // end else go right } // end while } // end else not root } // end insert() // ------------------------------------------------------------- public boolean delete(int key) // delete node with given key { // (assumes non-empty list) Node current = root; Node parent = root; boolean isLeftChild = true;

while(current.iData != key) // search for node { parent = current; if(key < current.iData) // go left? { isLeftChild = true; current = current.leftChild; } else // or go right? { isLeftChild = false; current = current.rightChild; } if(current == null) // end of the line, return false; // didn't find it } // end while // found node to delete

// if no children, simply delete it if(current.leftChild==null && current.rightChild==null) { if(current == root) // if root, root = null; // tree is empty else if(isLeftChild) parent.leftChild = null; // disconnect else // from parent parent.rightChild = null; }

// if no right child, replace with left subtree else if(current.rightChild==null) if(current == root) root = current.leftChild; else if(isLeftChild) parent.leftChild = current.leftChild; else parent.rightChild = current.leftChild;

// if no left child, replace with right subtree else if(current.leftChild==null) if(current == root) root = current.rightChild; else if(isLeftChild) parent.leftChild = current.rightChild; else parent.rightChild = current.rightChild;

else // two children, so replace with inorder successor { // get successor of node to delete (current) Node successor = getSuccessor(current);

// connect parent of current to successor instead if(current == root) root = successor; else if(isLeftChild) parent.leftChild = successor; else parent.rightChild = successor;

// connect successor to current's left child successor.leftChild = current.leftChild; } // end else two children // (successor cannot have a left child) return true; // success } // end delete() // ------------------------------------------------------------- // returns node with next-highest value after delNode // goes to right child, then right child's left descendents private Node getSuccessor(Node delNode) { Node successorParent = delNode; Node successor = delNode; Node current = delNode.rightChild; // go to right child while(current != null) // until no more { // left children, successorParent = successor; successor = current; current = current.leftChild; // go to left child } // if successor not if(successor != delNode.rightChild) // right child, { // make connections successorParent.leftChild = successor.rightChild; successor.rightChild = delNode.rightChild; } return successor; } // ------------------------------------------------------------- public void traverse(int traverseType) { switch(traverseType) { case 1: System.out.print(" Preorder traversal: "); preOrder(root); break; case 2: System.out.print(" Inorder traversal: "); inOrder(root); break; case 3: System.out.print(" Postorder traversal: "); postOrder(root); break; } System.out.println(); } // ------------------------------------------------------------- private void preOrder(Node localRoot) { if(localRoot != null) { System.out.print(localRoot.iData + " "); preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); } } // ------------------------------------------------------------- private void inOrder(Node localRoot) { if(localRoot != null) { inOrder(localRoot.leftChild); System.out.print(localRoot.iData + " "); inOrder(localRoot.rightChild); } } // ------------------------------------------------------------- private void postOrder(Node localRoot) { if(localRoot != null) { postOrder(localRoot.leftChild); postOrder(localRoot.rightChild); System.out.print(localRoot.iData + " "); } } // ------------------------------------------------------------- public void displayTree() { Stack globalStack = new Stack(); globalStack.push(root); int nBlanks = 32; boolean isRowEmpty = false; System.out.println( "......................................................"); while(isRowEmpty==false) { Stack localStack = new Stack(); isRowEmpty = true;

for(int j=0; j

while(globalStack.isEmpty()==false) { Node temp = (Node)globalStack.pop(); if(temp != null) { System.out.print(temp.iData); localStack.push(temp.leftChild); localStack.push(temp.rightChild);

if(temp.leftChild != null || temp.rightChild != null) isRowEmpty = false; } else { System.out.print("--"); localStack.push(null); localStack.push(null); } for(int j=0; j

theTree.insert(50, 1.5); theTree.insert(25, 1.2); theTree.insert(75, 1.7); theTree.insert(12, 1.5); theTree.insert(37, 1.2); theTree.insert(43, 1.7); theTree.insert(30, 1.5); theTree.insert(33, 1.2); theTree.insert(87, 1.7); theTree.insert(93, 1.5); theTree.insert(97, 1.5);

while(true) { System.out.print("Enter first letter of view, "); System.out.print("insert, find, delete, size, levels(depth of the tree), maximum, removeLeaves or traverse. Enter x for rightMinValue, y for leftMaxValue, z for minimum"); int choice = getChar(); switch(choice) { case 's': System.out.println("The size of the tree is " + theTree.size()); break; case 'l': System.out.println("The depth of the tree is " + theTree.depth()); break; case 'r': theTree.removeLeaves(); System.out.println("Removed leaves on the tree."); break; case 'x': System.out.println("The right min of the tree is " + theTree.rightMinValue()); break; case 'y': System.out.println("The left max of the tree is " + theTree.leftMaxValue()); break; case 'z': System.out.println("The max of the tree is " + theTree.maximum()); break; case 'm': System.out.println("The max of the tree is " + theTree.maximum()); break; case 'v': theTree.displayTree(); break; case 'i': System.out.print("Enter value to insert: "); value = getInt(); theTree.insert(value, value + 0.9); break; case 'f': System.out.print("Enter value to find: "); value = getInt(); Node found = theTree.find(value); if(found != null) { System.out.print("Found: "); found.displayNode(); System.out.print(" "); } else System.out.print("Could not find "); System.out.print(value + ' '); break; case 'd': System.out.print("Enter value to delete: "); value = getInt(); boolean didDelete = theTree.delete(value); if(didDelete) System.out.print("Deleted " + value + ' '); else System.out.print("Could not delete "); System.out.print(value + ' '); break; case 't': System.out.print("Enter type 1, 2 or 3: "); value = getInt(); theTree.traverse(value); break; default: System.out.print("Invalid entry "); } // end switch } // end while } // end main() // ------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } // ------------------------------------------------------------- public static char getChar() throws IOException { String s = getString(); return s.charAt(0); } //------------------------------------------------------------- public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); } // ------------------------------------------------------------- } // end class TreeApp ////////////////////////////////////////////////////////////////

The depth method is not working. I need it to be fixed to run this program.