Computer Science 210
Data Structures
Fall 2017, Siena College
BTTraversals BlueJ Project
Click here to download a BlueJ project for BTTraversals.
BTTraversals Source Code
The Java source code for BTTraversals is below. Click on a file name to download it.
import structure5.*;
/**
class to build a simple BinaryTree and traverse it in a number of ways
@author Jim Teresco, terescoj@cs.williams.edu, jteresco@mtholyoke.edu,
jteresco@siena.edu
*/
public class BTTraversals<T> {
/** the tree to be traversed */
protected BinaryTree<T> root;
public BTTraversals(BinaryTree<T> root) {
this.root = root;
}
public void doInorder() {
doInorder(root);
}
/**
method to traverse the tree "inorder"
each value will be passed to the method "process" according to
its position in an inorder traversal
@param root The root of the BinaryTree to be traversed
*/
protected void doInorder(BinaryTree<T> root) {
if (root.isEmpty()) return;
doInorder(root.left());
process(root.value());
doInorder(root.right());
}
public void doPreorder() {
doPreorder(root);
}
/**
method to traverse the tree "preorder"
each value will be passed to the method "process" according to
its position in a preorder traversal
@param root The root of the BinaryTree to be traversed
*/
protected void doPreorder(BinaryTree<T> root) {
if (root.isEmpty()) return;
process(root.value());
doPreorder(root.left());
doPreorder(root.right());
}
public void doPostorder() {
doPostorder(root);
}
/**
method to traverse the tree "postorder"
each value will be passed to the method "process" according to
its position in a postorder traversal
@param root The root of the BinaryTree to be traversed
*/
protected void doPostorder(BinaryTree<T> root) {
if (root.isEmpty()) return;
doPostorder(root.left());
doPostorder(root.right());
process(root.value());
}
/**
method to traverse the tree "level order"
each value will be passed to the method "process" according to
its position in a level order traversal
Here, we don't need a protected method, since there is no recursion
*/
public void doLevelorder() {
Queue<BinaryTree<T>> q = new QueueList<BinaryTree<T>>();
q.enqueue(root);
while (!q.isEmpty()) {
BinaryTree<T> tree = q.dequeue();
if (tree.isEmpty()) continue;
process(tree.value());
q.enqueue(tree.left());
q.enqueue(tree.right());
}
}
/**
The "process" method -- for our purposes, just print it out
@param value the Object of type T being visited
*/
protected void process(T value) {
System.out.print(value + " ");
}
/** main method to set up an answer */
public static void main(String[] args) {
/* build the binary tree:
8
/ \
4 10
/ \ / \
2 6 9 12
/ \ / \ / \
1 3 5 7 11 13
*/
/* we will build it from the bottom up */
BinaryTree<Integer> root =
new BinaryTree<Integer>(new Integer(8),
new BinaryTree<Integer>(new Integer(4),
new BinaryTree<Integer>(new Integer(2),
new BinaryTree<Integer>(new Integer(1)),
new BinaryTree<Integer>(new Integer(3))),
new BinaryTree<Integer>(new Integer(6),
new BinaryTree<Integer>(new Integer(5)),
new BinaryTree<Integer>(new Integer(7)))),
new BinaryTree<Integer>(new Integer(10),
new BinaryTree<Integer>(new Integer(9)),
new BinaryTree<Integer>(new Integer(12),
new BinaryTree<Integer>(new Integer(11)),
new BinaryTree<Integer>(new Integer(13)))));
/* what does it look like? */
System.out.println(root.treeString());
BTTraversals<Integer> btt = new BTTraversals<Integer>(root);
/* inorder traversal first */
System.out.println("In order: ");
btt.doInorder();
System.out.println("with doInorder()");
AbstractIterator<Integer> i = root.inorderIterator();
while (i.hasNext()) btt.process(i.next());
System.out.println("with inorderIterator()");
/* preorder traversal */
System.out.println("Preorder: ");
btt.doPreorder();
System.out.println("with doPreorder()");
i = root.preorderIterator();
while (i.hasNext()) btt.process(i.next());
System.out.println("with preorderIterator()");
/* postorder traversal */
System.out.println("Postorder: ");
btt.doPostorder();
System.out.println("with doPostorder()");
i = root.postorderIterator();
while (i.hasNext()) btt.process(i.next());
System.out.println("with postorderIterator()");
/* level order traversal */
System.out.println("Level order: ");
btt.doLevelorder();
System.out.println("with doLevelorder()");
i = root.levelorderIterator();
while (i.hasNext()) btt.process(i.next());
System.out.println("with levelorderIterator()");
}
}