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