Question
Implement the BinarySearchTree class. The BinarySearchTree class extends the BinaryTree class which implements the Tree interface. All can be seen here. Your assignment is to implement all of the abstract methods of the BinaryTree class recursively.
They are:
Insert.
Iterator (non-recursive).
Remove.
Search.
You must also implement an Iterator inner class for the BinarySearchTree class. You must submit a modified BinarySearchTree.java file with your source code.
Do not submit and do not modify the Tree.java or BinaryTree.java files.
THE GIVEN CODE in ""HERE"" FILE IS AS FOLLOWS :
Explanation / Answer
import java.util.*; public class BST implements Iterable { public static void main(String[] args) { Integer[] a = {1,5,2,7,4}; BST bst = new BST(); for(Integer n : a) bst.insert(n); bst.preOrderTraversal(); System.out.println(); //testing comparator //build a mirror BST with a rule: Left > Parent > Right //code for the comparator at the bottom of the file bst = new BST(new MyComp1()); for(Integer n : a) bst.insert(n); bst.preOrderTraversal(); System.out.println(); bst.inOrderTraversal(); System.out.println(); for(Integer n : bst) System.out.print(n); System.out.println(); System.out.println(bst); //testing restoring a tree from two given traversals bst.restore(new Integer[] {11,8,6,4,7,10,19,43,31,29,37,49}, new Integer[] {4,6,7,8,10,11,19,29,31,37,43,49}); bst.preOrderTraversal(); System.out.println(); bst.inOrderTraversal(); System.out.println(); //testing diameter System.out.println("diameter = " + bst.diameter()); //testing width System.out.println("width = " + bst.width()); } private Node root; private Comparator comparator; public BST() { root = null; comparator = null; } public BST(Comparator comp) { root = null; comparator = comp; } private int compare(T x, T y) { if(comparator == null) return x.compareTo(y); else return comparator.compare(x,y); } /***************************************************** * * INSERT * ******************************************************/ public void insert(T data) { root = insert(root, data); } private Node insert(Node p, T toInsert) { if (p == null) return new Node(toInsert); if (compare(toInsert, p.data) == 0) return p; if (compare(toInsert, p.data) < 0) p.left = insert(p.left, toInsert); else p.right = insert(p.right, toInsert); return p; } /***************************************************** * * SEARCH * ******************************************************/ public boolean search(T toSearch) { return search(root, toSearch); } private boolean search(Node p, T toSearch) { if (p == null) return false; else if (compare(toSearch, p.data) == 0) return true; else if (compare(toSearch, p.data) < 0) return search(p.left, toSearch); else return search(p.right, toSearch); } /***************************************************** * * DELETE * ******************************************************/ public void delete(T toDelete) { root = delete(root, toDelete); } private Node delete(Node p, T toDelete) { if (p == null) throw new RuntimeException("cannot delete."); else if (compare(toDelete, p.data) < 0) p.left = delete (p.left, toDelete); else if (compare(toDelete, p.data) > 0) p.right = delete (p.right, toDelete); else { if (p.left == null) return p.right; else if (p.right == null) return p.left; else { // get data from the rightmost node in the left subtree p.data = retrieveData(p.left); // delete the rightmost node in the left subtree p.left = delete(p.left, p.data) ; } } return p; } private T retrieveData(Node p) { while (p.right != null) p = p.right; return p.data; } public Iterator iterator() { return new MyIterator(); } //pre-order private class MyIterator implements Iterator { Stack stk = new Stack(); public MyIterator() { if(root != null) stk.push(root); } public boolean hasNext() { return !stk.isEmpty(); } public T next() { Node cur = stk.peek(); if(cur.left != null) { stk.push(cur.left); } else { Node tmp = stk.pop(); while( tmp.right == null ) { if(stk.isEmpty()) return cur.data; tmp = stk.pop(); } stk.push(tmp.right); } return cur.data; }//end of next() public void remove() { } }//end of MyIterator