| << Chapter < Page | Chapter >> Page > |
package brs.visitor;import brs.*;
import java.util.*;/*** Inserts an Object into the host maintaining the host's binary search
* tree property via a given Comparator.* Can also be used for Comparable objects.
* Duplication is not allowed: replaces old data object with the new one.*/
public class BSTInserter implements IVisitor {private Comparator _order;/**
* Used when the items in the tree are Comparable objects.*/
public BSTInserter() {_order = new Comparator() {
public int compare(Object x, Object y) {return ((Comparable)x).compareTo(y);
}};
}
/**
* Used to order the items according to a given Comparator.* @param order a total ordering on the items to be stored in the tree.*/
public BSTInserter (Comparator order) {_order = order;
}/*** Returns the host tree where the input is inserted as the root.
* @param host an empty binary tree, which obviously satisfies BSTP.* @param input[0] new data to be inserted.* @return host (which is no longer empty).
*/public Object emptyCase(BiTree host, Object... input) {
host.insertRoot (input[0]);
return host;}/**
* If the input is equal to host.getRootDat) then the old root data* is replaced by input. Equality here is implicitly defined by the
* total ordering represented by the Comparator _order.* @param host non-empty and satisfies BSTP.
* @param input[0]new data to be inserted.
* @return the tree where input[0]is inserted as the root.
*/public Object nonEmptyCase(BiTree host, Object... input) {
Object root = host.getRootDat();if (_order.compare(input[0], root)<0) {
return host.getLeftSubTree().execute(this, input[0]);
}if (_order.compare(input[0], root)>0) {
return host.getRightSubTree().execute(this, input[0]);
}host.setRootDat(input[0]);return host;
}}
Suppose we have a binary search tree based on a given Comparator ordering. The following algorithm will allow us to lookup and retrieve a particular data object from the tree. This algorithm also works for binary search tree containing Comparable objects.
package brs.visitor;
import brs.*;import java.util.*;/**
* Finds a data object in a binary host tree that satisfies the* Binary Search Tree Property.
* The algorithm is similar to that of insertion.*/
public class BSTFinder implements IVisitor {private Comparator _order;
/*** Used when the items in the tree are Comparable objects.
*/public BSTFinder() {
_order = new Comparator() {public int compare(Object x, Object y) {
return ((Comparable)x).compareTo(y);}
};}
/**
* Used when the items are ordered according to a given Comparator.* @param order a total ordering on the items stored in the tree.
*/public BSTFinder(Comparator order) {
_order = order;}/**
* Returns the empty host tree itself.* @param host an empty binary (which obviously satisfies the
* Binary Search Tree Property).* @param nu not used
* @return BiTree the empty host tree.*/
public Object emptyCase(BiTree host, Object... nu) {return host;
}/*** Returns the tree such that whose root, if it exists, is equal to input
* via the given Comparator _order.* @param host non empty and satisfies BSTP.
* @param input[0]object to be looked up.
* @return BiTree*/
public Object nonEmptyCase(BiTree host, Object... input) {Object root = host.getRootDat();
if (_order.compare(input[0], root)<0) {
return host.getLeftSubTree().execute(this, input[0]);
}if (_order.compare(input[0], root)>0) {
return host.getRightSubTree().execute(this, input[0]);
}return host;
}}
Notification Switch
Would you like to follow the 'Principles of object-oriented programming' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|