/* * BinarySearchTree.java */import java.util.LinkedList;import java.util.List;public class BinarySearchTree <Key extends Comparable<Key>, Data> { // name of root Key name = null; // data of root Data value = null; // left subtree BinarySearchTree<Key, Data> leftSubtree = null; // right subtree BinarySearchTree<Key, Data> rightSubtree = null; /** * Creates a new empty binary search tree */ public BinarySearchTree() { } /** * Determines if tree is empty or not * @return * boolean describing if tree is empty or not */ public boolean isEmptyTree(){ return name == null; } /** * Determines the smallest right child/successor * @return * leftest node in right subtree */ public BinarySearchTree<Key, Data> findSmallestChild(){ // no left subtree exist -> found leftest node if (leftSubtree.isEmptyTree()) return this; // left subtree found -> go on with recursion else return leftSubtree.findSmallestChild(); } /** * Determines the greatest left child/successor * @return * rightest node in left subtree */ public BinarySearchTree<Key, Data> findGreatestChild(){ // right subtree is empty -> found rightest node if (rightSubtree.isEmptyTree()) return this; // there is another right subtree -> go further on with recursion else return rightSubtree.findGreatestChild(); } /** * Adds the specified key and the related data to the tree. * If the specified key already exists an KeyAlreadyExistsException should be thrown. */ public void add(Key key, Data data) { // check if key already contained in tree if (contains(key)) throw new KeyAlreadyExistsException(); // (sub)tree is empty -> add key if (isEmptyTree()){ name = key; value = data; // subtrees are new empty trees leftSubtree = new BinarySearchTree<Key, Data>(); rightSubtree = new BinarySearchTree<Key, Data>(); } // key is less than root -> go on with left subtree if (name.compareTo(key) > 0) // subtree is empty -> add key if (leftSubtree.isEmptyTree()){ leftSubtree.name = key; leftSubtree.value = data; // subtrees are new empty trees leftSubtree.leftSubtree = new BinarySearchTree<Key, Data>(); leftSubtree.rightSubtree = new BinarySearchTree<Key, Data>(); } // go on with left subtree else leftSubtree.add(key, data); // key is greater than root -> go on with right subtree if (name.compareTo(key) < 0) // subtree is empty -> add key if (rightSubtree.isEmptyTree()){ rightSubtree.name = key; rightSubtree.value = data; // subtrees are new empty trees rightSubtree.leftSubtree = new BinarySearchTree<Key, Data>(); rightSubtree.rightSubtree = new BinarySearchTree<Key, Data>(); } // go on with right subtree else rightSubtree.add(key, data); } /** * Removes the specified key and its related data from the tree. * If the tree does not contain the specified key, an KeyNotInTreeException should be thrown. */ public void remove (Key key) { // check if key exists in tree if (!contains(key)) throw new KeyNotInTreeException(); // check if key is less than root (-> left subtree) if (name.compareTo(key) > 0) leftSubtree.remove(key); // check if key is greater than root (-> right subtree) else if (name.compareTo(key) < 0) rightSubtree.remove(key); // key is wether in left nor in right subtree -> key must be root of actual subtree else{ // left subtree is empty if (leftSubtree.isEmptyTree()){ // replace key with right subtree name = rightSubtree.name; value = rightSubtree.value; leftSubtree = rightSubtree.leftSubtree; rightSubtree = rightSubtree.rightSubtree; } // right subtree is empty else if (rightSubtree.isEmptyTree()){ // replace key with left subtree name = leftSubtree.name; value = leftSubtree.value; leftSubtree = leftSubtree.leftSubtree; rightSubtree = leftSubtree.rightSubtree; } // both subtrees are non-empty else{ // get leftest(smallest) right(greater) child/successor BinarySearchTree<Key, Data> child = rightSubtree.findSmallestChild(); // replace key with leftest right child name = child.name; value = child.value; // no left subtree exist because got leftest right child -> take right one child.name = child.rightSubtree.name; child.value = child.rightSubtree.value; } } } /** * Returns the data of the specified key. * If the tree does not contain the specified key, an KeyNotInTreeException should be thrown. */ public Data getData (Key key) { // tree is empty if (isEmptyTree()) throw new KeyNotInTreeException(); // key belongs to left subtree if (name.compareTo(key) > 0) return leftSubtree.getData(key); // key belongs to right subtree if (name.compareTo(key) < 0) return rightSubtree.getData(key); // found key (key doesn't belong to left or right subtree but exists) else return value; } /** * Returns true, if the tree contains the specified key and false otherwise */ public boolean contains (Key key){ // tree is empty -> key can't be contained if (isEmptyTree()) return false; // search for key in left subtree if (name.compareTo(key) > 0) return leftSubtree.contains(key); // search for key in right subtree if (name.compareTo(key) < 0) return rightSubtree.contains(key); // key found else return true; } /** * Returns a List with all the keys saved in pre-order (WLR) */ public List <Key> getPreOrder(){ // initialize list LinkedList<Key> result = new LinkedList<Key>(); // first add root result.add(name); // then add left subtree if (!leftSubtree.isEmptyTree()) result.addAll(leftSubtree.getPreOrder()); // and last add right subtree if (!rightSubtree.isEmptyTree()) result.addAll(rightSubtree.getPreOrder()); return result; } /** * Returns a List with all the keys saved in in-order (LWR) */ public List <Key> getInOrder(){ // initialize list LinkedList<Key> result = new LinkedList<Key>(); // first add left subtree if (!leftSubtree.isEmptyTree()) result.addAll(leftSubtree.getInOrder()); // then add root result.add(name); // and last add right subtree if (!rightSubtree.isEmptyTree()) result.addAll(rightSubtree.getInOrder()); return result; } /** * Returns a List with all the keys saved in post-order (LRW) */ public List <Key> getPostOrder(){ // initialize list LinkedList<Key> result = new LinkedList<Key>(); // first add left subtree if (!leftSubtree.isEmptyTree()) result.addAll(leftSubtree.getPostOrder()); // then add right subtree if (!rightSubtree.isEmptyTree()) result.addAll(rightSubtree.getPostOrder()); // and last add root result.add(name); return result; }}