package treenode;

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ import java.io.*; import java.util.*; // for Stack class //////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////

public class Tree { public static void main(String[] args) throws IOException { int value; Tree theTree = new Tree(); 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.println("Please enter:"); System.out.println("1. Show"); System.out.println("2. Insert"); System.out.println("3. Find"); System.out.println("4. Delete"); System.out.println("5. Traverse"); System.out.println("6. Size"); System.out.println("7. Depth"); System.out.println("8. RemoveLeaves"); System.out.println("9. RightMinValue"); System.out.println("10. LeftMaxValue"); System.out.println("11. Maximum"); System.out.println("12. Minimum");

int choice = getInt(); switch (choice) { case 1: theTree.displayTree(); break; case 2: System.out.print("Enter value to insert: "); value = getInt(); theTree.insert(value, value + 0.9); break; case 3: 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 4: 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 5: System.out.print("Enter type 1, 2 or 3: "); value = getInt(); theTree.traverse(value); break; case 6: System.out.println("Size of the tree is: " + theTree.getSize()); break; case 7: System.out.println("Depth of the tree is: " + theTree.depth2(theTree.root)); break; case 8: System.out.println("Removing Leaf node of the tree: "); theTree.root = theTree.removeLeafNode(theTree.root); System.out.println("Removed leafs"); break; case 9: System.out.println("Right Min Value of the tree: "+ theTree.rightMinValue()); break; case 10: System.out.println("Left Max Value of the tree: "+ theTree.leftMaxValue()); break; case 11: System.out.println("Maximum Value of the tree: "+ theTree.maxValue()); break; case 12: System.out.println("Minimum Value of the tree: "+ theTree.minValue()); 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); }

private Node root; // first node of tree private int size; // -------------------------------------------------------------

public Tree() // constructor { root = null; size = 0; } // no nodes in tree yet // -------------------------------------------------------------

public int getSize() { return this.size; }

public int depth2(Node node) { if (node == null) return 0; int left = depth2(node.leftChild); int right = depth2(node.rightChild);

int x = left > right ? left + 1 : right + 1; return x; }

public Node removeLeafNode(Node root) { if (root == null) return null; else { if (root.leftChild == null && root.rightChild == null) { // if both // left // and // right // child // are // null root = null; // delete it (by assigning null) } else { root.leftChild = removeLeafNode(root.leftChild); // set new left // node root.rightChild = removeLeafNode(root.rightChild); // set new // right // node } return root; } }

public int rightMinValue() { if (root.rightChild != null){ return rightMinValue(root.rightChild); } return root.iData; }

/* Function to return least value recursively */ private int rightMinValue(Node r) { if (r.leftChild == null) return r.iData; return rightMinValue(r.leftChild); } public int leftMaxValue() { if (root.leftChild != null){ return leftMaxValue(root.leftChild); } return root.iData; }

/* Function to return least value recursively */ private int leftMaxValue(Node r) { if (r.rightChild == null) return r.iData; return leftMaxValue(r.rightChild); }

public int minValue() { return minValue(root); }

/* Function to return least value recursively */ private int minValue(Node r) { if (r.leftChild == null) return r.iData; return rightMinValue(r.leftChild); } public int maxValue() { return maxValue(root); }

/* Function to return least value recursively */ private int maxValue(Node r) { if (r.rightChild == null) return r.iData; //System.out.println(r.iData+" "); return maxValue(r.rightChild); } 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 void insert(int id, double dd) { Node newNode = new Node(); // make new node newNode.iData = id; // insert data newNode.dData = dd; size++; 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 < nBlanks; j++) System.out.print(' '); 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 < nBlanks * 2 - 2; j++) System.out.print(' '); } // end while globalStack not empty System.out.println(); nBlanks /= 2; while (localStack.isEmpty() == false) globalStack.push(localStack.pop()); } // end while isRowEmpty is false System.out.println("......................................................"); } // end displayTree()

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("} "); } } // end class Node // ------------------------------------------------------------- } // end class Tree

import java.io.*; class TreeApp0 { public static void main(String[] args)throws IOException { Tree theTree = new Tree(); // make a tree theTree.insert(50, 1.5); // insert 3 nodes theTree.insert(25, 1.7); theTree.insert(75, 1.9); Node found = theTree.find(25); // find node with key 25 if(found != null) System.out.println("Found the node with key 25"); else System.out.println("Could not find node with key 25"); }

// ------------------------------------------------------------- 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 ////////////////////////////////////////////////////////////////

My main class isn't working need to be fixed. Please modify it so it can work with the sub class.