Treetest.java
/** A NodeOperator that prints each node.
*
* Taken from Core Web Programming from
* Prentice Hall and Sun Microsystems Press,
* .
* © 2001 Marty Hall and Larry Brown;
* may be freely used or adapted.
*/
class PrintOperator implements NodeOperator {
public void operateOn(Node node) {
System.out.println(node.getNodeValue());
}
}
/** A sample tree representing a parse tree of
* the sentence "Java hackers hack Java", using
* some simple context-free grammar.
*/
public class TreeTest {
public static void main(String[] args) {
Node adjective =
new Node(" Adjective", new Leaf(" Java"));
Node noun1 =
new Node(" Noun", new Leaf(" hackers"));
Node verb =
new Node(" TransitiveVerb", new Leaf(" hack"));
Node noun2 =
new Node(" Noun", new Leaf(" Java"));
Node np = new Node(" NounPhrase", adjective, noun1);
Node vp = new Node(" VerbPhrase", verb, noun2);
Node sentence = new Node("Sentence", np, vp);
PrintOperator printOp = new PrintOperator();
System.out.println("Depth first traversal:");
sentence.depthFirstSearch(printOp);
System.out.println("\nBreadth first traversal:");
sentence.breadthFirstSearch(printOp);
}
}
Leaf.java
A leaf node with no children.
/** Leaf node: a node with no subtrees.
*
* Taken from Core Web Programming from
* Prentice Hall and Sun Microsystems Press,
* .
* © 2001 Marty Hall and Larry Brown;
* may be freely used or adapted.
*/
public class Leaf extends Node {
public Leaf(Object value) {
super(value, null, null);
}
}
Node.java A data structure representing a node in a binary tree.
import java.util.Vector;
/** A data structure representing a node in a binary tree.
* It contains a node value and a reference (pointer) to
* the left and right subtrees.
*
* Taken from Core Web Programming from
* Prentice Hall and Sun Microsystems Press,
* .
* © 2001 Marty Hall and Larry Brown;
* may be freely used or adapted.
*/
public class Node {
private Object nodeValue;
private Node leftChild, rightChild;
/** Build Node with specified value and subtrees. */
public Node(Object nodeValue, Node leftChild,
Node rightChild) {
this.nodeValue = nodeValue;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
/** Build Node with specified value and L subtree. R child
* will be null. If you want both children to be null, use
* the Leaf constructor.
*/
public Node(Object nodeValue, Node leftChild) {
this(nodeValue, leftChild, null);
}
/** Return the value of this node. */
public Object getNodeValue() {
return(nodeValue);
}
/** Specify the value of this node. */
public void setNodeValue(Object nodeValue) {
this.nodeValue = nodeValue;
}
/** Return the L subtree. */
public Node getLeftChild() {
return(leftChild);
}
/** Specify the L subtree. */
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
/** Return the R subtree. */
public Node getRightChild() {
return(rightChild);
}
/** Specify the R subtree. */
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
/** Traverse the tree in depth-first order, applying
* the specified operation to each node along the way.
*/
public void depthFirstSearch(NodeOperator op) {
op.operateOn(this);
if (leftChild != null) {
leftChild.depthFirstSearch(op);
}
if (rightChild != null) {
rightChild.depthFirstSearch(op);
}
}
/** Traverse the tree in breadth-first order, applying the
* specified operation to each node along the way.
*/
public void breadthFirstSearch(NodeOperator op) {
Vector nodeQueue = new Vector();
nodeQueue.addElement(this);
Node node;
while(!nodeQueue.isEmpty()) {
node = (Node)nodeQueue.elementAt(0);
nodeQueue.removeElementAt(0);
op.operateOn(node);
if (node.getLeftChild() != null) {
nodeQueue.addElement(node.getLeftChild());
}
if (node.getRightChild() != null) {
nodeQueue.addElement(node.getRightChild());
}
}
}
}
NodeOperator.java An interface used in the Node class to ensure that an object has an operateOn method.
/** An interface used in the Node class to ensure that
* an object has an operateOn method.
*
* Taken from Core Web Programming from
* Prentice Hall and Sun Microsystems Press,
* .
* © 2001 Marty Hall and Larry Brown;
* may be freely used or adapted.
*/
public interface NodeOperator {
void operateOn(Node node);
}
Similar Posts
Machine Learning, Big Data, Data Science, Analytics, Cloud, Security, AI, Robotics, Database, BI, Development: Software, Web, Mobile