CS 112 Lab 6

LevelOrder traversal: Traverse nodes level by level from the root, output nodes at each level in left to right order.

Inorder traversal: Traverse left sub tree, output self, traverse right sub tree.

Preorder traversal: Output self, traverse left sub tree, traverse right sub tree

Postorder traversal: Traverse left sub tree, traverse right sub tree, ouptut self

package lab06;
import java.util.*;
 
class BTreeNode<T> {
    T element;
    BTreeNode<T> leftChild, rightChild;
    BTreeNode( T element, BTreeNode<T> leftChild, BTreeNode<T> rightChild ){
        this.element = element;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
    T getElement(){ return element; }
    BTreeNode<T> getLeft(){ return leftChild; }
    BTreeNode<T> getRight(){ return rightChild; }
}
 
class LevelorderIterator<T> implements Iterator<T>{
    // We will use the LinkedList implementation for our Queue
    LinkedList<BTreeNode<T>> iteratorQueue;
    
    LevelorderIterator(BTreeNode<T> root){
        iteratorQueue = new LinkedList<BTreeNode<T>>();
        iteratorQueue.add(root);
    }
    public boolean hasNext() {
        return !iteratorQueue.isEmpty();
    }    
    public T next() {
        // Remove current node from the queue.
        BTreeNode<T> curNode = iteratorQueue.remove();
                
        // Add the left child of curNode if present to the queue.
        
        // Add the right child of curNode if present to the queue.
        
        // Return the data (element) for curNode.
        return curNode.getElement();
    }
    public void remove() {}    
}
 
// StackElement has two fields: BTreeNode and a boolean visited,
// this class will be used in Inorder, Preorder and Postorder iterators below.  
class StackElement<T> {
    BTreeNode<T> btreeNode;
    boolean visited;
    StackElement( BTreeNode<T> btreeNode, boolean visited ){
        this.btreeNode = btreeNode;
        this.visited = visited;
    }
    BTreeNode<T> getNode(){    return btreeNode; }
    boolean isVisited(){ return visited; }
}
 
class InorderIterator<T> implements Iterator<T>{
    Stack<StackElement<T>> iteratorStack;
    
    InorderIterator(BTreeNode<T> root){
        iteratorStack = new Stack<StackElement<T>>();
        iteratorStack.push(new StackElement<T>(root, false));
    }
    public boolean hasNext() {        
        return !iteratorStack.isEmpty();
    }
    public T next() {
    
        // Repeat until we have a visited node on top of the stack.
        while( !iteratorStack.peek().isVisited() ){
        
            // Get current node from top of the stack.
            
            // If right child is present, push it on the stack as not-visited.
            
            // Push current node on the stack as visited.
            
            // If left child is present, push it on the stack as not-visited.
        }
        
        // Pop the node on top of the stack (this node is a visited node) 
        // and return its data.
        return iteratorStack.pop().getNode().getElement();
    }
    public void remove() {}
}
 
class PreorderIterator<T> implements Iterator<T>{
    Stack<StackElement<T>> iteratorStack;
    
    PreorderIterator(BTreeNode<T> root){
        iteratorStack = new Stack<StackElement<T>>();
        iteratorStack.push(new StackElement<T>(root, false));
    }
    public boolean hasNext() {        
        return !iteratorStack.isEmpty();
    }
    public T next() {
        while( !iteratorStack.peek().isVisited() ){
            BTreeNode<T> curNode = iteratorStack.pop().getNode();
            
            // TASK:
            // Fill in the code here for PreorderIterator.next() following 
            // the example for InorderIterator.next().
            
        }
        return iteratorStack.pop().getNode().getElement();
    }
    public void remove() {}
}
 
class PostorderIterator<T> implements Iterator<T>{
    Stack<StackElement<T>> iteratorStack;
    
    PostorderIterator(BTreeNode<T> root){
        iteratorStack = new Stack<StackElement<T>>();
        iteratorStack.push(new StackElement<T>(root, false));
    }
    public boolean hasNext() {        
        return !iteratorStack.isEmpty();
    }
    public T next() {
        while( !iteratorStack.peek().isVisited() ){
            BTreeNode<T> curNode = iteratorStack.pop().getNode();
            
            // TASK:
            // Fill in the code here for PostorderIterator.next() following 
            // the example for InorderIterator.next().
            
        }
        return iteratorStack.pop().getNode().getElement();
    }
    public void remove() {}
}
 
public class BTree<T> {
    BTreeNode<T> root;    
    BTree(BTreeNode<T> root){
        this.root = root;
    }
    Iterator<T> getLevelOrderIterator(){
        return new LevelorderIterator<T>(root);
    }
    Iterator<T> getInOrderIterator(){
        return new InorderIterator<T>(root); 
    }
    Iterator<T> getPreOrderIterator(){
        return new PreorderIterator<T>(root); 
    }
    Iterator<T> getPostOrderIterator(){
        return new PostorderIterator<T>(root); 
    }
}

package lab06;
import java.util.*;
 
public class BTreeClient {
 
    public static void main(String[] args) {
        
        // Initialize the example binary tree
        BTree<Integer> testTree = setupTree();
        
        System.out.println("Levelorder tree traversal");
        Iterator<Integer> levelOrderIterator = testTree.getLevelOrderIterator();
        while( levelOrderIterator.hasNext() )
            System.out.print(levelOrderIterator.next()+" ");
        System.out.println("\n");
        
        System.out.println("Inorder tree traversal");
        Iterator<Integer> inOrderIterator = testTree.getInOrderIterator();
        while( inOrderIterator.hasNext() )
            System.out.print(inOrderIterator.next()+" ");
        System.out.println("\n");
        
        System.out.println("Preorder tree traversal");
        Iterator<Integer> preOrderIterator = testTree.getPreOrderIterator();
        while( preOrderIterator.hasNext() )
            System.out.print(preOrderIterator.next()+" ");
        System.out.println("\n");
        
        System.out.println("Postorder tree traversal");
        Iterator<Integer> postOrderIterator = testTree.getPostOrderIterator();
        while( postOrderIterator.hasNext() )
            System.out.print(postOrderIterator.next()+" ");
        System.out.println("\n");
        
    }
    
    static BTree<Integer> setupTree(){
        
        BTreeNode<Integer> n6 = new BTreeNode<Integer>(6, null, null);
        BTreeNode<Integer> n7 = new BTreeNode<Integer>(7, null, null);
        BTreeNode<Integer> n4 = new BTreeNode<Integer>(4, n6, n7);
        BTreeNode<Integer> n3 = new BTreeNode<Integer>(3, null, null);
        BTreeNode<Integer> n12 = new BTreeNode<Integer>(12, n3, n4);
        BTreeNode<Integer> n8 = new BTreeNode<Integer>(8, null, null);
        BTreeNode<Integer> n2 = new BTreeNode<Integer>(2, null, n8);
        BTreeNode<Integer> n11 = new BTreeNode<Integer>(11, null, null);
        BTreeNode<Integer> n5 = new BTreeNode<Integer>(5, n11, n2);
        BTreeNode<Integer> n10 = new BTreeNode<Integer>(10, n12, n5);
        
        return new BTree<Integer>(n10);
    }
 
}

Levelorder tree traversal
10, 12, 5, 3, 4, 11, 2, 6, 7, 8, 
 
Inorder tree traversal
3, 12, 6, 4, 7, 10, 11, 5, 2, 8, 
 
Preorder tree traversal
10, 12, 3, 4, 6, 7, 5, 11, 2, 8, 
 
Postorder tree traversal
3, 6, 7, 4, 12, 11, 8, 2, 5, 10,

http://cs-people.bu.edu/tvashwin/cs112_spring09/lab04.html