-
-
Save bytecodeman/ec375646a641cd7664af9545fad9d1fd to your computer and use it in GitHub Desktop.
Updated Binary Search Tree Chapter 25 code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package chapter25; | |
interface Execution<E> { | |
void execute(E e); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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