Skip to content

Instantly share code, notes, and snippets.

@bytecodeman bytecodeman/BST.java Secret
Last active Nov 26, 2019

Embed
What would you like to do?
Updated Binary Search Tree Chapter 25 code
package chapter25;
public class BST<E extends Comparable<E>> implements Tree<E> {
/**
* This inner class is static, because it does not access any instance members
* defined in its outer class
*/
static class TreeNode<E> {
public E data;
public TreeNode<E> left = null;
public TreeNode<E> right = null;
public TreeNode(E e) {
this.data = e;
}
}
protected TreeNode<E> root = null;
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 < objects.length; i++)
add(objects[i]);
}
/** Recursively duplicate tree */
private TreeNode<E> copy(TreeNode<E> p) {
TreeNode<E> temp = null;
if (p != null) {
temp = new TreeNode<E>(p.data);
temp.left = copy(p.left);
temp.right = copy(p.right);
}
return temp;
}
public void copyTree(BST<E> p) {
root = copy(p.root);
}
@Override /** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
@Override /** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
// **************************************************************************************************
// Traversals
// @Override
// public void inorder() {
// inorder(root, new Execution<E>() {
// public void execute(E e) {
// System.out.println(e);
// }});
// }
@Override
public void inorder() {
inorder(root, e -> System.out.println(e));
}
public void inorder(Execution<E> e) {
inorder(root, e);
}
@Override
public void preorder() {
preorder(root, e -> System.out.println(e));
}
public void preorder(Execution<E> e) {
preorder(root, e);
}
@Override
public void postorder() {
postorder(root, e -> System.out.println(e));
}
public void postorder(Execution<E> e) {
postorder(root, e);
}
private void inorder(TreeNode<E> p, Execution<E> e) {
if (p != null) {
inorder(p.left, e);
e.execute(p.data);
inorder(p.right, e);
}
}
private void preorder(TreeNode<E> p, Execution<E> e) {
if (p != null) {
e.execute(p.data);
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.data);
}
}
// **************************************************************************************************
// Recursive Counting Routines
public int treeHeight() {
return height(root);
}
public int treeNodeCount() {
return nodeCount(root);
}
public int treeLeavesCount() {
return leavesCount(root);
}
private int height(TreeNode<E> p) {
if (p == null)
return 0;
else
return 1 + Math.max(height(p.left), height(p.right));
}
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);
}
@Override /** Returns true if the data is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.data) < 0) {
current = current.left;
} else if (e.compareTo(current.data) > 0) {
current = current.right;
} else // data matches current.data
return true; // data 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.data))
return true;
else if (searchItem.compareTo(ptr.data) < 0)
return recSearch(ptr.left, searchItem);
else
return recSearch(ptr.right, searchItem);
}
@Override /**
* Insert data e into the binary tree Return true if the data 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.data) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.data) > 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.data) < 0)
parent.left = new TreeNode<E>(e);
else
parent.right = new TreeNode<E>(e);
}
size++;
return true; // data inserted successfully
}
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 (e.compareTo(p.data) < 0) {
p.left = recinsertHelper(p.left, e);
retval = p;
} else if (e.compareTo(p.data) == 0)
retval = p;
else {
p.right = recinsertHelper(p.right, e);
retval = p;
}
return retval;
}
/** Returns a path from the root leading to the specified data */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list = new java.util.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.data) < 0) {
current = current.left;
} else if (e.compareTo(current.data) > 0) {
current = current.right;
} else
break;
}
return list; // Return an array list of nodes
}
@Override /**
* Delete an data from the binary tree. Return true if the data is deleted
* successfully Return false if the data 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.data) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.data) > 0) {
parent = current;
current = current.right;
} else
break; // data is in the tree pointed at by current
}
if (current == null)
return false; // data 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.data) < 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 data in current by the data in rightMost
current.data = rightMost.data;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // data deleted successfully
}
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.data) < 0) { // p.data > insertItem
p.left = recdeleteHelper(p.left, e);
retval = p;
} else if (e.compareTo(p.data) < 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.data
TreeNode<E> current = p.left;
while (current.right != null)
current = current.right;
p.data = current.data;
p.left = recdeleteHelper(p.left, current.data);
retval = p;
}
}
return retval;
}
@Override /** Obtain an iterator. Use inorder. */
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<>();
private int current = 0; // Point to the current data 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<E> root) {
if (root == null)
return;
inorder(root.left);
list.add(root.data);
inorder(root.right);
}
@Override /** More elements for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
@Override /** Get the current data and move to the next */
public E next() {
return list.get(current++);
}
@Override // Remove the data returned by the last next()
public void remove() {
if (current == 0) // next() has not been called yet
throw new IllegalStateException();
delete(list.get(--current));
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
}
package chapter25;
interface Execution<E> {
void execute(E e);
}
package chapter25;
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");
BST<String> kyle = new BST<>();
kyle.copyTree(tree);
//System.out.println("Printout Kyle: ");
kyle.inorder(e->System.out.println("Hi: " + e));
//System.out.println();
//System.out.println();
//tree.inorder(new TreeNodeExecutor<String>());
// or
kyle.inorder(new Execution<String>() {
private int count = 0;
@Override
public void execute(String e) {
count++;
System.out.println(count + ": " + e);
}
});
/*
// Traverse tree
System.out.print("Inorder (sorted): ");
tree.inorder();
System.out.print("\nPostorder: ");
tree.postorder();
System.out.print("\nPreorder: ");
tree.preorder();
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: ");
java.util.ArrayList<BST.TreeNode<String>> path = tree.path("Peter");
for (int i = 0; path != null && i < path.size(); i++)
System.out.print(path.get(i).data + " ");
Integer[] numbers = { 2, 4, 3, 1, 8, 5, 6, 7 };
BST<Integer> intTree = new BST<>(numbers);
System.out.print("\nInorder (sorted): ");
intTree.inorder();
*/
}
}
class TreeNodeExecutor<E> implements Execution<E> {
private int count = 0;
@Override
public void execute(E e) {
count++;
System.out.println(count + ": " + e);
}
}
package chapter25;
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 tree) {
// Traverse tree
System.out.print("Inorder (sorted): ");
tree.inorder();
System.out.print("\nPostorder: ");
tree.postorder();
System.out.print("\nPreorder: ");
tree.preorder();
System.out.print("\nThe number of nodes is " + tree.getSize());
System.out.println();
}
}
package chapter25;
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.toUpperCase() + " ");
System.out.println();
Iterator<String> it = tree.iterator();
while (it.hasNext())
{
System.out.print(it.next().toUpperCase() + " ");
}
System.out.println();
}
}
package chapter25;
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 void inorder();
/** Postorder traversal from the root */
public void postorder();
/** Preorder traversal from the root */
public void preorder();
@Override /** Return true if the tree is empty */
public default boolean isEmpty() {
return this.size() == 0;
}
@Override
public default boolean contains(Object e) {
return search((E) e);
}
@Override
public default boolean add(E e) {
return insert(e);
}
@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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.