Java Programing: Binary Search Tree
Fully implement the BST class in Listing 25.4 (on page 961 of the 11thEdition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like.
Listing 25.4 BST.java
public class BST>
extends AbstractTree {
protected TreeNode root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i
insert(objects[i]);
}
@Override /** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element)
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;
}
@Override /** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode parent = null;
TreeNode current = root;
while (current != null)
if (e.compareTo(current.element)
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)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted successfully
}
protected TreeNode createNewNode(E e) {
return new TreeNode<>(e);
}
@Override /** Inorder traversal from the root */
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
@Override /** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
@Override /** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/** This inner class is static, because it does not access
any instance members defined in its outer class */
public static class TreeNode> {
public E element;
public TreeNode left;
public TreeNode right;
public TreeNode(E e) {
element = e;
}
}
@Override /** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList> path(E e) {
java.util.ArrayList> list =
new java.util.ArrayList<>();
TreeNode current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element)
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array list of nodes
}
@Override /** 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 parent = null;
TreeNode current = root;
while (current != null) {
if (e.compareTo(current.element)
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 at by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left child
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)
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 parentOfRightMost = current;
TreeNode 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 deleted successfully
}
@Override /** Obtain an iterator. Use inorder. */
public java.util.Iterator iterator() {
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator {
// Store the elements in a list
private java.util.ArrayList list =
new java.util.ArrayList<>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode root) {
if (root == null)return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
@Override /** More elements for traversing? */
public boolean hasNext() {
if (current
return true;
return false;
}
@Override /** Get the current element and move to the next */
public E next() {
return list.get(current++);
}