/**
*
*/
import java.util.Stack;
import java.util.Vector;
/**
* @author yovn
*
*/
public class TreeDemo {
static interface NodeVistor
{
<T> void visit(BinaryTreeNode<T> node);
}
static class BinaryTree<T>
{
BinaryTreeNode<T> root;
public BinaryTree(BinaryTreeNode<T> root) {
this.root=root;
}
//no recursion ,pre-order
void NLRVisit(NodeVistor visitor)
{
BinaryTreeNode<T> pointer=root;
Stack<BinaryTreeNode<T>> stack=new Stack<BinaryTreeNode<T>>();
while(!stack.isEmpty()||pointer!=null)
{
if(pointer!=null)
{
visitor.visit(pointer);
if(pointer.rightChild!=null)
{
stack.push(pointer.rightChild);
}
pointer=pointer.leftChild;
}
//go to right child
else
{
pointer=stack.pop();
}
}
}
//no recursion , in-order
void LNRVisit(NodeVistor visitor)
{
BinaryTreeNode<T> pointer=root;
Stack<BinaryTreeNode<T>> stack=new Stack<BinaryTreeNode<T>>();
while(!stack.isEmpty()||pointer!=null)
{
if(pointer!=null)
{
stack.push(pointer);
pointer=pointer.leftChild;
}
//no left child here, then visit root and then go to right child
else
{
pointer=stack.pop();
visitor.visit(pointer);
pointer=pointer.rightChild;
}
}
}
//no recursion ,post-order,this one is the most complex one.
//we need know from which side ,it back(left or right)
void LRNVisit(NodeVistor visitor)
{
if(root==null)return;
BinaryTreeNode<T> pointer=root;
Stack<BinaryTreeNode<T>> stack=new Stack<BinaryTreeNode<T>>();
while(true)
{
//mark left
while(pointer!=null)
{
stack.push(pointer);
pointer=pointer.leftChild;
}
pointer=stack.pop();
while(pointer.visitedRight)//back from right child, so we can visit it now.
{
visitor.visit(pointer);
if(stack.isEmpty())return;
pointer=stack.pop();
}
pointer.visitedRight=true;
stack.push(pointer);
pointer=pointer.rightChild;
}
}
void levelOrder(NodeVistor visitor)
{
if(root==null)return;
BinaryTreeNode<T> pointer=root;
Vector<BinaryTreeNode<T>> queue=new Vector<BinaryTreeNode<T>>();
queue.add(pointer);
while(!queue.isEmpty())
{
BinaryTreeNode<T> node=queue.remove(0);
visitor.visit(node);
if(node.leftChild!=null)
{
queue.add(node.leftChild);
}
if(node.rightChild!=null)
{
queue.add(node.rightChild);
}
}
}
}
static class BinaryTreeNode<T>
{
BinaryTreeNode(T data)
{
this.data=data;
}
T data;
boolean visitedRight;
BinaryTreeNode<T> leftChild;
BinaryTreeNode<T> rightChild;
}
/**
*
*/
public TreeDemo() {
// TODO Auto-generated constructor stub
}
/**
* @param args
*/
public static void main(String[] args) {
BinaryTreeNode<String> root=new BinaryTreeNode<String>("A");
root.leftChild=new BinaryTreeNode<String>("B");
root.rightChild=new BinaryTreeNode<String>("C");
root.leftChild.leftChild=new BinaryTreeNode<String>("D");
root.rightChild.leftChild=new BinaryTreeNode<String>("E");
root.rightChild.rightChild=new BinaryTreeNode<String>("F");
root.rightChild.leftChild.rightChild=new BinaryTreeNode<String>("G");
root.rightChild.rightChild.leftChild=new BinaryTreeNode<String>("H");
root.rightChild.rightChild.rightChild=new BinaryTreeNode<String>("I");
NodeVistor visitor=new NodeVistor()
{
@Override
public <T> void visit(BinaryTreeNode<T> node) {
System.out.print("'"+node.data+"'");
}
};
BinaryTree<String> tree=new BinaryTree<String>(root);
System.out.println("pre-order visit");
tree.NLRVisit(visitor);
System.out.println();
System.out.println("in-order visit");
tree.LNRVisit(visitor);
System.out.println();
System.out.println("post-order visit");
tree.LRNVisit(visitor);
System.out.println();
System.out.println("level-order visit");
tree.levelOrder(visitor);
}
}