<![CDATA[
CSE143 Sample Program handout #24
GeneralTreeNode Class
---------------------
// Class GeneralTreeNode is used to build general trees.
public class GeneralTreeNode {
public Comparable data; // data stored in this node
public LinkedList children; // reference to list of children trees
// post: constructs a GeneralTreeNode as a leaf with given data
public GeneralTreeNode(Object _data) {
data = (Comparable)_data;
children = new LinkedList();
}
// post: adds a child tree to this node
public void addChild(GeneralTreeNode node) {
children.addLast(node);
}
// post: returns the number of subtrees of this node
public int numChildren() {
return children.size();
}
}
GeneralTree Class
-----------------
// Class GeneralTree stores and prints a general tree of Comparable
// objects. It has the following public methods:
//
// public GeneralTree()
// constructs an empty tree
// public void printPreOrder()
// print the tree in pre-order
// public boolean lookup(Comparable query)
// returns true if query is in the tree
public class GeneralTree {
private GeneralTreeNode root; // root of overall tree
// post: constructs an empty tree
public GeneralTree() {
root = null;
}
// post: prints the data fields of the tree, one per line
public void printPreOrder() {
printPreOrder(root);
}
// pre : node points to a general tree
// post: prints the data fields of the tree using an pre-order traversal
private void printPreOrder(GeneralTreeNode node) {
if (node != null) {
System.out.println(node.data);
for (int i = 0; i < node.children.size(); i++) {
printPreOrder((GeneralTreeNode)node.children.get(i));
}
}
}
// post: returns true if query is in the tree
public boolean lookup(Comparable query) {
return lookup(root, query);
}
// pre : node points to a general tree
// post: returns true if query is in the tree rooted at node
public boolean lookup(GeneralTreeNode node, Comparable query) {
if (node == null) {
return false;
} else if (node.data.compareTo(query) == 0) {
return true;
} else {
for (int i = 0; i < node.children.size(); i++) {
if (lookup((GeneralTreeNode)node.children.get(i), query)) {
return true;
}
}
return false;
}
}
}
]]>