CSC-220 Chapter 25 Modified Code

BST.java

package chapter25.silvestri;

import java.util.*;

public class BST<E extends Comparable<E>> implements Tree<E>, Iterable<E> {
	protected TreeNode<E> root;
	protected int size;

	/** Inner class tree node */
	protected static class TreeNode<E extends Comparable<E>> {
		E element;
		TreeNode<E> left;
		TreeNode<E> right;

		public TreeNode(E e) {
			this(e, null, null);
		}

		public TreeNode(E e, TreeNode<E> left, TreeNode<E> right) {
			this.element = e;
			this.left = left;
			this.right = right;
		}
	}

	// **************************************************************************************************
	// Constructors

	/** Default Constructor */
	public BST() {
	}

	/** Copy Constructor */
	public BST(BST<E> otherTree) {
		this.root = copy(otherTree.root);
	}

	/** Create a binary tree from an array of objects */
	public BST(E[] objects) {
		for (int i = 0; i < objects.length; i++)
			insert(objects[i]);
	}

	/** Recursively duplicate tree */
	private TreeNode<E> copy(TreeNode<E> p) {
		TreeNode<E> temp = null;
		if (p != null) {
			temp = new TreeNode<E>(p.element);
			temp.left = copy(p.left);
			temp.right = copy(p.right);
		}
		return temp;
	}

	public void copyTree(BST<E> p) {
		root = copy(p.root);
	}

	public void clear() {
		this.root = null;
		this.size = 0;
	}

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

	// **************************************************************************************************
	// Traversals
	@Override
	public void inOrder(Execution<E> e) {
		inOrder(root, e);
	}

	@Override
	public void preOrder(Execution<E> e) {
		preOrder(root, e);
	}

	@Override
	public void postOrder(Execution<E> e) {
		postOrder(root, e);
	}

	@Override
	public void levelOrder(Execution<E> e) {
		Queue<TreeNode<E>> q = new LinkedList<>();
		q.add(root);
		levelOrder(q, e);
	}

	private void inOrder(TreeNode<E> p, Execution<E> e) {
		if (p != null) {
			inOrder(p.left, e);
			e.execute(p.element);
			inOrder(p.right, e);
		}
	}

	private void preOrder(TreeNode<E> p, Execution<E> e) {
		if (p != null) {
			e.execute(p.element);
			preOrder(p.left, e);
			preOrder(p.right, e);
		}
	}

	private void postOrder(TreeNode<E> p, Execution<E> e) {
		if (p != null) {
			postOrder(p.left, e);
			postOrder(p.right, e);
			e.execute(p.element);
		}
	}

	private void levelOrder(Queue<TreeNode<E>> q, Execution<E> e) {
		if (!q.isEmpty()) {
			TreeNode<E> item = q.remove();
			e.execute(item.element);
			if (item.left != null)
				q.add(item.left);
			if (item.right != null)
				q.add(item.right);
			levelOrder(q, e);
		}
	}

	// **************************************************************************************************
	// Recursive Counting Routines

	public int treeNodeCount() {
		return nodeCount(root);
	}

	public int treeLeavesCount() {
		return leavesCount(root);
	}

	public int treeHeight() {
		return height(root);
	}

	private int nodeCount(TreeNode<E> p) {
		if (p == null)
			return 0;
		else
			return 1 + nodeCount(p.left) + nodeCount(p.right);
	}

	private int leavesCount(TreeNode<E> p) {
		if (p == null)
			return 0;
		else if (p.left == null && p.right == null)
			return 1;
		else
			return leavesCount(p.left) + leavesCount(p.right);
	}

	private int height(TreeNode<E> p) {
		if (p == null)
			return 0;
		else
			return 1 + Math.max(height(p.left), height(p.right));
	}

	// **************************************************************************************************
	// Search Routines

	/** Returns true if the element is in the tree */
	public boolean search(E e) {
		TreeNode<E> current = root; // Start from the root

		while (current != null) {
			if (e.compareTo(current.element) < 0) {
				current = current.left;
			}
			else if (e.compareTo(current.element) > 0) {
				current = current.right;
			}
			else
				// element matches current.element
				return true; // Element is found
		}

		return false;
	}

	public boolean recSearch(E searchItem) {
		return recSearch(root, searchItem);
	}

	private boolean recSearch(TreeNode<E> ptr, E searchItem) {
		if (ptr == null)
			return false;
		else if (searchItem.equals(ptr.element))
			return true;
		else if (searchItem.compareTo(ptr.element) < 0)
			return recSearch(ptr.left, searchItem);
		else
			return recSearch(ptr.right, searchItem);
	}

	// **************************************************************************************************
	// Insert Routines

	/**
	 * Insert element o into the binary tree Return true if the element is inserted
	 * successfully
	 */
	public boolean insert(E e) {
		if (root == null)
			root = new TreeNode<E>(e); // Create a new root
		else {
			// Locate the parent node
			TreeNode<E> parent = null;
			TreeNode<E> current = root;
			while (current != null)
				if (e.compareTo(current.element) < 0) {
					parent = current;
					current = current.left;
				}
				else if (e.compareTo(current.element) > 0) {
					parent = current;
					current = current.right;
				}
				else
					return false; // Duplicate node not inserted

			// Create the new node and attach it to the parent node
			if (e.compareTo(parent.element) < 0)
				parent.left = new TreeNode<E>(e);
			else
				parent.right = new TreeNode<E>(e);
		}

		size++;
		return true; // Element inserted
	}

	public void recinsert(E e) {
		root = recinsertHelper(root, e);
	}

	private TreeNode<E> recinsertHelper(TreeNode<E> p, E e) {
		TreeNode<E> retval;
		if (p == null) {
			TreeNode<E> newNode = new TreeNode<E>(e);
			retval = newNode;
		}
		else if (p.element.compareTo(e) < 0) {
			p.left = recinsertHelper(p.left, e);
			retval = p;
		}
		else if (p.element.compareTo(e) == 0)
			retval = p;
		else {
			p.right = recinsertHelper(p.right, e);
			retval = p;
		}
		return retval;
	}

	// **************************************************************************************************
	// Delete Routines

	/**
	 * Delete an element from the binary tree. Return true if the element is deleted
	 * successfully Return false if the element is not in the tree
	 */
	public boolean delete(E e) {
		// Locate the node to be deleted and also locate its parent node
		TreeNode<E> parent = null;
		TreeNode<E> current = root;
		while (current != null) {
			if (e.compareTo(current.element) < 0) {
				parent = current;
				current = current.left;
			}
			else if (e.compareTo(current.element) > 0) {
				parent = current;
				current = current.right;
			}
			else
				break; // Element is in the tree pointed by current
		}

		if (current == null)
			return false; // Element is not in the tree

		if (current.left == null) {
			// Connect the parent with the right child of the current node
			if (parent == null) {
				root = current.right;
			}
			else {
				if (e.compareTo(parent.element) < 0)
					parent.left = current.right;
				else
					parent.right = current.right;
			}
		}
		else {
			// Case 2: The current node has a left child
			// Locate the rightmost node in the left subtree of
			// the current node and also its parent
			TreeNode<E> parentOfRightMost = current;
			TreeNode<E> rightMost = current.left;

			while (rightMost.right != null) {
				parentOfRightMost = rightMost;
				rightMost = rightMost.right; // Keep going to the right
			}

			// Replace the element in current by the element in rightMost
			current.element = rightMost.element;

			// Eliminate rightmost node
			if (parentOfRightMost.right == rightMost)
				parentOfRightMost.right = rightMost.left;
			else
				// Special case: parentOfRightMost == current
				parentOfRightMost.left = rightMost.left;
		}

		size--;
		return true; // Element inserted
	}

	public void recdelete(E e) {
		root = recdeleteHelper(root, e);
	}

	private TreeNode<E> recdeleteHelper(TreeNode<E> p, E e) {
		TreeNode<E> retval;
		if (p == null)
			retval = null;
		else if (e.compareTo(p.element) < 0) { // p.element > insertItem
			p.left = recdeleteHelper(p.left, e);
			retval = p;
		}
		else if (e.compareTo(p.element) < 0) {
			p.right = recdeleteHelper(p.right, e);
			retval = p;
		}
		else { // Found Item to delete!!!
			size--;
			if (p.left == null && p.right == null)
				retval = null;
			else if (p.left == null)
				retval = p.right;
			else if (p.right == null)
				retval = p.left;
			else {
				// Find Item whose value is immediately before p.element
				TreeNode<E> current = p.left;
				while (current.right != null)
					current = current.right;
				p.element = current.element;
				p.left = recdeleteHelper(p.left, current.element);
				retval = p;
			}
		}
		return retval;
	}

	/** Returns a path from the root leading to the specified element */
	public ArrayList<TreeNode<E>> path(E e) {
		ArrayList<TreeNode<E>> list = new ArrayList<>();
		TreeNode<E> current = root; // Start from the root

		while (current != null) {
			list.add(current); // Add the node to the list
			if (e.compareTo(current.element) < 0)
				current = current.left;
			else if (e.compareTo(current.element) > 0) {
				current = current.right;
			}
			else
				break;
		}

		return list; // Return an array of nodes
	}

	/** Obtain an iterator. Use inorder. */
	@Override
	public Iterator<E> iterator() {
		return new InorderIterator();
	}

	// Inner class InorderIterator
	class InorderIterator implements Iterator<E> {
		// Store the elements in a list
		private ArrayList<E> list = new ArrayList<E>();

		private int current = 0; // Point to the current element in list

		public InorderIterator() {
			inorder(root);
		}

		/** Inorder traversal from a subtree */
		private void inorder(TreeNode<E> root) {
			if (root != null) {
				inorder(root.left);
				list.add(root.element);
				inorder(root.right);
			}
		}

		/** Next element for traversing? */
		public boolean hasNext() {
			if (current < list.size())
				return true;

			return false;
		}

		/** Get the current element and move cursor to the next */
		public E next() {
			return list.get(current++);
		}

		/** Remove the current element and refresh the list */
		public void remove() {
			delete(list.get(current)); // Delete the current element
			list.clear(); // Clear the list
			inorder(root); // Rebuild the list
		}
	}

}

Exec.java

package chapter25.silvestri;

public class Exec<E> implements Execution<E> {
	public void execute(E e) {
		System.out.println(e);
	}
}

Execution.java

package chapter25.silvestri;

interface Execution<E> {
	void execute(E e);
}

TestBST.java

package chapter25.silvestri;

import java.util.ArrayList;

public class TestBST {
  public static void main(String[] args) {
    // Create a BST
    BST<String> tree = new BST<>();
    tree.insert("George");
    tree.insert("Michael");
    tree.insert("Tom");
    tree.insert("Adam");
    tree.insert("Jones");
    tree.insert("Peter");
    tree.insert("Daniel");

    // Traverse tree
    System.out.println("Level order: ");
    tree.levelOrder(new Exec<String>());
    System.out.println("\nInorder (sorted): ");
    tree.inOrder(new Exec<String>());
    System.out.println("\nPostorder: ");
    tree.postOrder(new Exec<String>());
    System.out.println("\nPreorder: ");
    tree.preOrder(new Exec<String>());
    
    System.out.print("\nThe number of nodes is " + tree.getSize());
    
    // Search for an element
    System.out.print("\nIs Peter in the tree? " + 
      tree.search("Peter"));

    // Get a path from the root to Peter
    System.out.print("\nA path from the root to Peter is: ");
    ArrayList<BST.TreeNode<String>> path = tree.path("Peter");
    for (int i = 0; path != null && i < path.size(); i++)
      System.out.print(path.get(i).element + " ");

    Integer[] numbers = {2, 4, 3, 1, 8, 5, 6, 7};
    BST<Integer> intTree = new BST<>(numbers); 
    System.out.print("\nInorder (sorted): ");
    intTree.inOrder(new Exec<Integer>());
  }
}

TestBSTDelete.java

package chapter25.silvestri;

public class TestBSTDelete {
	public static void main(String[] args) {
		BST<String> tree = new BST<>();
		tree.insert("George");
		tree.insert("Michael");
		tree.insert("Tom");
		tree.insert("Adam");
		tree.insert("Jones");
		tree.insert("Peter");
		tree.insert("Daniel");
		printTree(tree);

		System.out.println("\nAfter delete George:");
		tree.delete("George");
		printTree(tree);

		System.out.println("\nAfter delete Adam:");
		tree.delete("Adam");
		printTree(tree);

		System.out.println("\nAfter delete Michael:");
		tree.delete("Michael");
		printTree(tree);
	}

	public static void printTree(BST<String> tree) {
		// Traverse tree
		System.out.print("Inorder (sorted): ");
		tree.inOrder(new Exec<String>());
		System.out.print("\nPostorder: ");
		tree.postOrder(new Exec<String>());
		System.out.print("\nPreorder: ");
		tree.preOrder(new Exec<String>());
		System.out.print("\nThe number of nodes is " + tree.getSize());
		System.out.println();
	}
}

TestBSTWithIterator.java

package chapter25.silvestri;

import java.util.Iterator;

public class TestBSTWithIterator {
  public static void main(String[] args) {
    BST<String> tree = new BST<>();
    tree.insert("George");
    tree.insert("Michael");
    tree.insert("Tom");
    tree.insert("Adam");
    tree.insert("Jones");
    tree.insert("Peter");
    tree.insert("Daniel");
    
    for (String s: tree)
      System.out.print(s + " ");
    System.out.println();
    
    // or
    
    Iterator<String> it = tree.iterator();
    while(it.hasNext()) {
    	String s = it.next();
    	System.out.print(s + " ");
    }
    System.out.println();
    
  }
}

Tree.java

package chapter25.silvestri;

import java.util.Collection;

public interface Tree<E> extends Collection<E> {
  /** Return true if the element is in the tree */
  public boolean search(E e);

  /** Insert element e into the binary tree
   * Return true if the element is inserted successfully */
  public boolean insert(E e);

  /** Delete the specified element from the tree
   * Return true if the element is deleted successfully */
  public boolean delete(E e);
  
  /** Get the number of elements in the tree */
  public int getSize();
  
  /** Inorder traversal from the root*/
  public default void inOrder(Execution<E> e) {
  }

  /** Postorder traversal from the root */
  public default void postOrder(Execution<E> e) {
  }

  /** Preorder traversal from the root */
  public default void preOrder(Execution<E> e) {
  }
  
  /** LevelOrder traversal from the root */
  public default void levelOrder(Execution<E> e) {
  }
  
  @Override /** Return true if the tree is empty */
  public default boolean isEmpty() {
    return getSize() == 0;
  }

  @SuppressWarnings("unchecked")
  @Override
  public default boolean contains(Object e) {
    return search((E)e);
  }
  
  @Override
  public default boolean add(E e) {
    return insert(e);
  }
  
  @SuppressWarnings("unchecked")
  @Override
  public default boolean remove(Object e) {
		return delete((E) e);
  }
  
  @Override
  public default int size() {
    return getSize();
  }
  
  @Override
  public default boolean containsAll(Collection<?> c) {
    // Left as an exercise
    return false;
  }

  @Override
  public default boolean addAll(Collection<? extends E> c) {
    // Left as an exercise
    return false;
  }

  @Override
  public default boolean removeAll(Collection<?> c) {
    // Left as an exercise
    return false;
  }

  @Override
  public default boolean retainAll(Collection<?> c) {
    // Left as an exercise
    return false;
  }

  @Override
  public default Object[] toArray() {
    // Left as an exercise
    return null;
  }

  @Override
  public default <T> T[] toArray(T[] array) {
    // Left as an exercise
    return null;
  }
}