26-07-2012, 02:09 PM
A Binary Search Tree Implementation
A Binary Search Tree Implementation.ppt (Size: 567 KB / Downloads: 438)
Getting Started
A binary search tree is a binary tree
Nodes contain Comparable objects
For each node in the tree
The data in a node is greater than the data in the node's left subtree
The data in a node is less than the data in the node's right subtree
An Interface for the Binary Search Tree
import java.util.Iterator;public interface SearchTreeInterface extends TreeInterface{ public boolean contains(Comparable entry); public Comparable getEntry(Comparable entry); public Comparable add(Comparable newEntry); public Comparable remove(Comparable entry); public Iterator getInorderIterator();} // end SearchTreeInterface
Beginning the Class Definition
import java.util.Iterator;public class BinarySearchTree extends BinaryTree implements SearchTreeInterface{ public BinarySearchTree() { super(); } // end default constructor public BinarySearchTree(Comparable rootEntry) { super(); setRootNode(new BinaryNode(rootEntry)); } // end constructor
Adding an Entry Recursively
.) Recursively adding Chad to smaller subtrees of a binary search tree.
. . .
Removing an Entry, Node Has Two Children
Algorithm Delete the entry e from a node N that has two children
Find the rightmost node R in N’s left subtree
Replace the entry in node N with the entry that is in node R
Delete node R