Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

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.

BTTraversals.java

/* $Id: BTTraversals.java 999 2009-11-02 02:23:25Z terescoj $ */

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
 */
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()");
    }
}