public class BinaryTree { Node root; public void addNode(int key, String name) { // Create a new Node and initialize it Node newNode = new Node(key, name); // If there is no root this becomes root if (root == null) { root = newNode; } else { // Set root as the Node we will start // with as we traverse the tree Node focusNode = root; // Future parent for our new Node Node parent; while (true) { // root is the top parent so we start // there parent = focusNode; // Check if the new node should go on // the left side of the parent node if (key < focusNode.key) { // Switch focus to the left child focusNode = focusNode.leftChild; // If the left child has no children if (focusNode == null) { // then place the new node on the left of it parent.leftChild = newNode; return; // All Done } } else { // If we get here put the node on the right focusNode = focusNode.rightChild; // If the right child has no children if (focusNode == null) { // then place the new node on the right of it parent.rightChild = newNode; return; // All Done } } } } } // All nodes are visited in ascending order // Recursion is used to go to one node and // then go to its child nodes and so forth public void inOrderTraverseTree(Node focusNode) { if (focusNode != null) { // Traverse the left node preorderTraverseTree(focusNode.leftChild); // Visit the currently focused on node System.out.println(focusNode); // Traverse the right node preorderTraverseTree(focusNode.rightChild); } } public void preorderTraverseTree(Node focusNode) { if (focusNode != null) { System.out.println(focusNode); preorderTraverseTree(focusNode.leftChild); preorderTraverseTree(focusNode.rightChild); } } public void postOrderTraverseTree(Node focusNode) { if (focusNode != null) { preorderTraverseTree(focusNode.leftChild); preorderTraverseTree(focusNode.rightChild); System.out.println(focusNode); } } public Node findNode(int key) { // Start at the top of the tree Node focusNode = root; // While we haven't found the Node // keep looking while (focusNode.key != key) { // If we should search to the left if (key < focusNode.key) { // Shift the focus Node to the left child focusNode = focusNode.leftChild; } else { // Shift the focus Node to the right child focusNode = focusNode.rightChild; } // The node wasn't found if (focusNode == null) return null; } return focusNode; } public boolean remove(int key) { // Start at the top of the tree Node focusNode = root; Node parent = root; // When searching for a Node this will // tell us whether to search to the // right or left boolean isItALeftChild = true; // While we haven't found the Node // keep looking while (focusNode.key != key) { parent = focusNode; // If we should search to the left if (key < focusNode.key) { isItALeftChild = true; // Shift the focus Node to the left child focusNode = focusNode.leftChild; } else { // Greater than focus node so go to the right isItALeftChild = false; // Shift the focus Node to the right child focusNode = focusNode.rightChild; } // The node wasn't found if (focusNode == null) return false; } // If Node doesn't have children delete it if (focusNode.leftChild == null && focusNode.rightChild == null) { // If root delete it if (focusNode == root) root = null; // If it was marked as a left child // of the parent delete it in its parent else if (isItALeftChild) parent.leftChild = null; // Vice versa for the right child else parent.rightChild = null; } // If no right child else if (focusNode.rightChild == null) { if (focusNode == root) root = focusNode.leftChild; // If focus Node was on the left of parent // move the focus Nodes left child up to the // parent node else if (isItALeftChild) parent.leftChild = focusNode.leftChild; // Vice versa for the right child else parent.rightChild = focusNode.leftChild; } // If no left child else if (focusNode.leftChild == null) { if (focusNode == root) root = focusNode.rightChild; // If focus Node was on the left of parent // move the focus Nodes right child up to the // parent node else if (isItALeftChild) parent.leftChild = focusNode.rightChild; // Vice versa for the left child else parent.rightChild = focusNode.rightChild; } // Two children so I need to find the deleted nodes // replacement else { Node replacement = getReplacementNode(focusNode); // If the focusNode is root replace root // with the replacement if (focusNode == root) root = replacement; // If the deleted node was a left child // make the replacement the left child else if (isItALeftChild) parent.leftChild = replacement; // Vice versa if it was a right child else parent.rightChild = replacement; replacement.leftChild = focusNode.leftChild; } return true; } public Node getReplacementNode(Node replacedNode) { Node replacementParent = replacedNode; Node replacement = replacedNode; Node focusNode = replacedNode.rightChild; // While there are no more left children while (focusNode != null) { replacementParent = replacement; replacement = focusNode; focusNode = focusNode.leftChild; } // If the replacement isn't the right child // move the replacement into the parents // leftChild slot and move the replaced nodes // right child into the replacements rightChild if (replacement != replacedNode.rightChild) { replacementParent.leftChild = replacement.rightChild; replacement.rightChild = replacedNode.rightChild; } return replacement; } public static void main(String[] args) { BinaryTree theTree = new BinaryTree(); theTree.addNode(50, "Boss"); theTree.addNode(25, "Vice President"); theTree.addNode(15, "Office Manager"); theTree.addNode(30, "Secretary"); theTree.addNode(75, "Sales Manager"); theTree.addNode(85, "Salesman 1"); // Different ways to traverse binary trees // theTree.inOrderTraverseTree(theTree.root); // theTree.preorderTraverseTree(theTree.root); // theTree.postOrderTraverseTree(theTree.root); // Find the node with key 75 System.out.println("\nNode with the key 75"); System.out.println(theTree.findNode(75)); System.out.println("Remove Key 25"); theTree.remove(25); System.out.println(theTree.findNode(25)); theTree.inOrderTraverseTree(theTree.root); } } class Node { int key; String name; Node leftChild; Node rightChild; Node(int key, String name) { this.key = key; this.name = name; } public String toString() { return name + " has the key " + key; /* * return name + " has the key " + key + "\nLeft Child: " + leftChild + * "\nRight Child: " + rightChild + "\n"; */ } }