<![CDATA[/************************ BST.java **************************
* generic binary search tree
*/
public class BST {
protected BSTNode root = null;
public BST() {
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public void insert(BaseObject el) {
BSTNode p = root, prev = null;
while (p != null) { // find a place for inserting new node;
prev = p;
if (p.key.isLessThan(el))
p = p.right;
else p = p.left;
}
if (root == null) // tree is empty;
root = new BSTNode(el);
else if (prev.key.isLessThan(el))
prev.right = new BSTNode(el);
else prev.left = new BSTNode(el);
}
public boolean isInTree(BaseObject el) {
return search(el) != null;
}
public BaseObject search(BaseObject el) {
return search(root,el);
}
protected BaseObject search(BSTNode p, BaseObject el) {
while (p != null)
if (el.equals(p.key))
return p.key;
else if (el.isLessThan(p.key))
p = p.left;
else p = p.right;
return null;
}
public void preorder() {
preorder(root);
}
public void inorder() {
inorder(root);
}
public void postorder() {
postorder(root);
}
protected void inorder(BSTNode p) {
if (p != null) {
inorder(p.left);
p.visit();
inorder(p.right);
}
}
protected void preorder(BSTNode p) {
if (p != null) {
p.visit();
preorder(p.left);
preorder(p.right);
}
}
protected void postorder(BSTNode p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
p.visit();
}
}
public void deleteByCopying(BaseObject el) {
BSTNode node, p = root, prev = null;
while (p != null && !p.key.equals(el)) { // find the node p
prev = p; // with element el;
if (p.key.isLessThan(el))
p = p.right;
else p = p.left;
}
node = p;
if (p != null && p.key.equals(el)) {
if (node.right == null) // node has no right child;
node = node.left;
else if (node.left == null) // no left child for node;
node = node.right;
else {
BSTNode tmp = node.left; // node has both children;
BSTNode previous = node; // 1.
while (tmp.right != null) { // 2. find the rightmost
previous = tmp; // position in the
tmp = tmp.right; // left subtree of node;
}
node.key = tmp.key; // 3. overwrite the reference
// of the key being deleted;
if (previous == node) // if node's left child's
previous.left = tmp.left; // right subtree is null;
else previous.right = tmp.left; // 4.
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else prev.right = node;
}
else if (root != null)
System.out.println("key " + el.toString() + " is not in the tree");
else System.out.println("the tree is empty");
}
public void deleteByMerging(BaseObject el) {
BSTNode tmp, node, p = root, prev = null;
while (p != null && !p.key.equals(el)) { // find the node p
prev = p; // with element el;
if (p.key.isLessThan(el))
p = p.right;
else p = p.left;
}
node = p;
if (p != null && p.key.equals(el)) {
if (node.right == null) // node has no right child: its left
node = node.left; // child (if any) is attached to its parent;
else if (node.left == null) // node has no left child: its right
node = node.right; // child is attached to its parent;
else { // be ready for merging subtrees;
tmp = node.left; // 1. move left
while (tmp.right != null) // 2. and then right as far as
tmp = tmp.right; // possible;
tmp.right = // 3. establish the link between the
node.right; // the rightmost node of the left
// subtree and the right subtree;
node = node.left; // 4.
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else prev.right = node;
}
else if (root != null)
System.out.println("key " + el.toString() + " is not in the tree");
else System.out.println("the tree is empty");
}
public void iterativePreorder() {
BSTNode p = root;
Stack travStack = new Stack();
if (p != null) {
travStack.push(p);
while (!travStack.isEmpty()) {
p = (BSTNode) travStack.pop();
p.visit();
if (p.right != null)
travStack.push(p.right);
if (p.left != null) // left child pushed after right
travStack.push(p.left);// to be on the top of the stack;
}
}
}
public void iterativeInorder() {
BSTNode p = root;
Stack travStack = new Stack();
while (p != null) {
while(p != null) { // stack the right child (if any)
if (p.right != null) // and the node itself when going
travStack.push(p.right); // to the left;
travStack.push(p);
p = p.left;
}
p = (BSTNode) travStack.pop(); // pop a node with no left child
while (!travStack.isEmpty() && p.right == null) { // visit it and all
p.visit(); // nodes with no right child;
p = (BSTNode) travStack.pop();
}
p.visit(); // visit also the first node with
if (!travStack.isEmpty()) // a right child (if any);
p = (BSTNode) travStack.pop();
else p = null;
}
}
public void iterativePostorder() {
BSTNode p = root, q = root;
Stack travStack = new Stack();
while (p != null) {
for ( ; p.left != null; p = p.left)
travStack.push(p);
while (p != null && (p.right == null || p.right == q)) {
p.visit();
q = p;
if (travStack.isEmpty())
return;
p = (BSTNode) travStack.pop();
}
travStack.push(p);
p = p.right;
}
}
public void breadthFirst() {
BSTNode p = root;
Queue queue = new Queue();
if (p != null) {
queue.enqueue(p);
while (!queue.isEmpty()) {
p = (BSTNode) queue.dequeue();
p.visit();
if (p.left != null)
queue.enqueue(p.left);
if (p.right != null)
queue.enqueue(p.right);
}
}
}
public void MorrisInorder() {
BSTNode p = root, tmp;
while (p != null)
if (p.left == null) {
p.visit();
p = p.right;
}
else {
tmp = p.left;
while (tmp.right != null && // go to the rightmost node of
tmp.right != p) // the left subtree or
tmp = tmp.right; // to the temporary parent of p;
if (tmp.right == null) {// if 'true' rightmost node was
tmp.right = p; // reached, make it a temporary
p = p.left; // parent of the current root,
}
else { // else a temporary parent has been
p.visit(); // found; visit node p and then cut
tmp.right = null; // the right pointer of the current
p = p.right; // parent, whereby it ceases to be
} // a parent;
}
}
public void MorrisPreorder() {
BSTNode p = root, tmp;
while (p != null) {
if (p.left == null) {
p.visit();
p = p.right;
}
else {
tmp = p.left;
while (tmp.right != null &&// go to the rightmost node of
tmp.right != p) // the left subtree or
tmp = tmp.right; // to the temporary parent of p;
if (tmp.right == null) {// if 'true' rightmost node was
p.visit(); // reached, visit the root and
tmp.right = p; // make the rightmost node a temporary
p = p.left; // parent of the current root,
}
else { // else a temporary parent has been
tmp.right = null; // found; cut the right pointer of
p = p.right; // the current parent, whereby it ceases
} // to be a parent;
}
}
}
public void MorrisPostorder() {
BSTNode p = new BSTNode(), tmp, q, r, s;
p.left = root;
while (p != null)
if (p.left == null)
p = p.right;
else {
tmp = p.left;
while (tmp.right != null && // go to the rightmost node of
tmp.right != p) // the left subtree or
tmp = tmp.right; // to the temporary parent of p;
if (tmp.right == null) {// if 'true' rightmost node was
tmp.right = p; // reached, make it a temporary
p = p.left; // parent of the current root,
}
else { // else a temporary parent has been found;
// process nodes between p.left (included) and p (excluded)
// extended to the right in modified tree in reverse order;
// the first loop descends this chain of nodes and reverses
// right pointers; the second loop goes back, visits nodes,
// and reverses right pointers again to restore the pointers
// to their original setting;
for (q = p.left, r = q.right, s = r.right;
r != p; q = r, r = s, s = s.right)
r.right = q;
for (s = q.right; q != p.left;
q.right = r, r = q, q = s, s = s.right)
q.visit();
p.left.visit(); // visit node p.left and then cut
tmp.right = null; // the right pointer of the current
p = p.right; // parent, whereby it ceases to be
} // a parent;
}
}
public void balance(BaseObject data[], int first, int last) {
if (first <= last) {
int middle = (first + last)/2;
insert(data[middle]);
balance(data,first,middle-1);
balance(data,middle+1,last);
}
}
}
]]>