Wednesday, November 16, 2011

Iterative Traversals in Java


package Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author ssundara
 *
 */
public class BinaryTree1 {
 
  BinaryTree1 left;
  BinaryTree1 right;
  int value;

  BinaryTree1(int value){
    this.value=value;
   
}
 
  /**
   * @param args
   */
  public static void main(String[] args){
   
    BinaryTree root=new BinaryTree(20);
    insert(root,8);
    insert(root,4);
   
    insert(root,22);
   
    insert(root,12);
    insert(root,10);
    insert(root,14);
    iterative_inorder(root);
    iterative_Preorder(root);
    iterative_Postorder(root);

}
 
  public static void insert(BinaryTree node, int value){
   if(value<node.value){
     if(node.left!=null)
       insert(node.left,value);
     else
       node.left=new BinaryTree(value);
   }
   if(value>node.value){
     if(node.right!=null)
       insert(node.right,value);
     else
       node.right=new BinaryTree(value);
   }
}
 
  public static void iterative_inorder(BinaryTree root){
 BinaryTree curr;
 Stack<BinaryTree> stk = new Stack<BinaryTree>();
 boolean done = false;
 stk.push(root);
 while(!stk.isEmpty()){
 done=false;
BinaryTree temp = stk.peek();
if(temp.left!=null)
stk.push(temp.left);

else {
while(!done){
if(stk.isEmpty()) return;
curr = stk.pop();
   System.out.println(curr.value);
curr=curr.right;
if(curr!=null){
done=true;
stk.push(curr);
}
}
 }
  }
  }
 
  public static void iterative_Preorder(BinaryTree root){
 BinaryTree curr;
 Stack<BinaryTree> stk = new Stack<BinaryTree>();
 boolean done = false;
 stk.push(root);
 System.out.println("DFS");
 System.out.print(root.value + " ");
 while(!stk.isEmpty()){
 done=false;
BinaryTree temp = stk.peek();
if(temp.left!=null){
stk.push(temp.left);
System.out.print(temp.left.value + " ");
}

else {
while(!done){
if(stk.isEmpty()) return;
curr = stk.pop();
   curr=curr.right;
if(curr!=null){
done=true;
stk.push(curr);
System.out.print(curr.value + " ");

}
}
 }
  }
  }
 
 
public static void iterative_Postorder(BinaryTree root){
 BinaryTree curr,tmp=null;
 System.out.println("asdfasdf");
 Stack<BinaryTree> stk = new Stack<BinaryTree>();
boolean pop=false;
 stk.push(root);
 while(!stk.isEmpty()){
BinaryTree temp = stk.peek();
if(temp.left!=null && !pop)
stk.push(temp.left);
else {
curr = stk.peek();
curr=curr.right;
if(curr!=null && curr!=tmp){
stk.push(curr);
pop=false;
}
else{
tmp = stk.pop();
pop=true;
System.out.println(tmp.value);
}
}
}
}
}

No comments:

Post a Comment