实现：

//二叉树类public class MyBiTree {	private MyBiTreeNode  root;//根节点				MyBiTree()	{		this.root = null;	}		MyBiTree(Object data,MyBiTree left,MyBiTree right)	{		MyBiTreeNode l,r;		if(left==null)		{			l = null;		}		else		{		   l=left.root; 		}				if(right==null)		{			r = null;		}		else		{			r = right.root;		}				this.root = new MyBiTreeNode(data,l,r);	}		//打印二叉树	public static void printBiTree(MyBiTreeNode root,int level)	{		if(root!=null)		{			printBiTree(root.getRightChild(),level+1);						if(level!=0)			{				//输出6*（level-1）个空格				for(int i=0;i<6*(level-1);i++)				{					System.out.print(" ");				}				System.out.print("-----");			}			System.out.println(root.getData());				    printBiTree(root.getLeftChild(),level+1);		}	}		//获得二叉树的结点	public static MyBiTreeNode getTreeNode(Object data,MyBiTreeNode left,MyBiTreeNode right)	{		MyBiTreeNode node = new MyBiTreeNode(data,left,right);		return node;	}		//查找指定元素	public static MyBiTreeNode search(MyBiTreeNode root,Object obj)	{		MyBiTreeNode node=null;		if(root==null)		{			return null;		}		if(root.getData().equals(obj))		{			return root;		}		if(root.getLeftChild()!=null)		{			node = search(root.getLeftChild(),obj);		}		if(root.getRightChild()!=null)		{			node = search(root.getRightChild(),obj);		}				return node;	}}

二叉树节点类

//二叉树结点类public class MyBiTreeNode {	private MyBiTreeNode leftChild; // 左孩子	private MyBiTreeNode rightChild; // 右孩子	private Object data; // 数据元素	MyBiTreeNode() {		this.leftChild = null;		this.rightChild = null;	}    	MyBiTreeNode(Object data,MyBiTreeNode leftNode,MyBiTreeNode rightNode)	{		this.data = data;		this.leftChild = leftNode;		this.rightChild = rightNode;	}			public MyBiTreeNode getLeftChild() {		return leftChild;	}	public void setLeftChild(MyBiTreeNode leftChild) {		this.leftChild = leftChild;	}	public MyBiTreeNode getRightChild() {		return rightChild;	}	public void setRightChild(MyBiTreeNode rightChild) {		this.rightChild = rightChild;	}	public Object getData() {		return data;	}	public void setData(Object data) {		this.data = data;	}}

游标遍历类：

reset方法是初始化；

如果栈中无元素了，isComplete则为false，结束标志。

其中的next方法是指：取得待打印的下一个节点，用next方法取得的节点就是要处理的节点。

public class MyBiTreeIterator {   	MyBiTreeNode root; //根节点	MyBiTreeNode curr;// 当前结点；	boolean isComplete;  //判断是否遍历结束		MyBiTreeIterator()	{			}	、	MyBiTreeIterator(MyBiTreeNode root)	{		this.root = root;	}		public void reset()	{			}		public void next()	{	  		}		public boolean endOfBiTree()	{	  return isComplete;		}		public Object getData()	{		return this.curr.getData();	}}

前序遍历：

//二叉树游标前序遍历类public class MyBiTreePreIterator extends MyBiTreeIterator{   	Stack
     
       stack = new Stack
      
       ();     		MyBiTreePreIterator()	{			}	MyBiTreePreIterator(MyBiTreeNode root)	{	   super(root);		}		@Override	public void next() {		// TODO Auto-generated method stub		if(this.isComplete)		{			System.out.println("已经遍历到二叉树结尾！");			return ;		}		if(this.curr.getRightChild()!=null)		{			stack.push(this.curr.getRightChild());		}		if(this.curr.getLeftChild()!=null)		{			stack.push(this.curr.getLeftChild());		}				if(!stack.empty())		{			this.curr = stack.pop();		}		else		{			this.isComplete = true;		}	}		@Override	public void reset() {		// TODO Auto-generated method stub		if(this.root==null)		{			this.isComplete = true;		}		else		{			this.isComplete = false;		}		if(this.root==null)		{			return ;		}		this.curr = this.root;	}}
      
     

中序遍历：

getFarLeft是找出最左侧节点，用于打印。

next方法是找到下一个需要处理的节点。

相比较上面的前序遍历，这里是左根右的方法，因此要处理每一个节点是，在过程中，把路过的节点入栈，用getFarLeft方法把最左侧的节点找出，并赋值给current节点。打印这个节点的data后，用next的方法再去找下一个，会先判断是否有右侧节点，如果有，则会在用getFarLeft方法找这个节点最左侧的节点，如果没有则用栈里的元素向上找。

二叉树游标中序遍历类public class MyBiTreeInIterator extends MyBiTreeIterator {  	Stack
     
       stack = new Stack
      
       ();    	MyBiTreeInIterator()	{			}	MyBiTreeInIterator(MyBiTreeNode root)	{		super(root);	}    	//得到最左边的结点	public MyBiTreeNode getFarLeft(MyBiTreeNode node)	{	   if(node==null)	   {		   return null;	   }	   while(node.getLeftChild()!=null)	   {		  stack.push(node);		  node = node.getLeftChild(); 	   }	   return node;	}		@Override	public void next() {		// TODO Auto-generated method stub		if(this.isComplete)		{			System.out.println("已经遍历到二叉树结尾！");			return ;		}				//这里如果执行了next，说明已经打印了这个节点，下一步要看右侧节点是否有子节点。		if(this.curr.getRightChild()!=null)		{			//在右孩子当中找最左边的。			this.curr = getFarLeft(this.curr.getRightChild());		}		else if(!stack.isEmpty())		{			this.curr = stack.pop();		}		else		{			this.isComplete = true;		}	}	@Override	//这里进行初始化时，就要用getFarLeft找到最右侧的点进行打印。	public void reset() {		// TODO Auto-generated method stub		if(this.root==null)		{			this.isComplete = true;		}		else		{			this.isComplete = false;		}		if(this.root==null)		{			return ;		}		this.curr = getFarLeft(this.root);	}}
      
     

中序遍历（2）

 public static void inTraverse(BinaryTree root) {  Stack s = new Stack();  BinaryTree p = root;  while(p!=null || !s.isEmpty()) {   if(p!=null) {   //这里只管push元素，然后找左侧元素    s.push(p);    p = p.lchild;   }   else {   //如果p为空的话，则说明左侧没有元素，把p这个点的元素打印出，再找右侧元素    p = (BinaryTree)s.pop();    visit(p);    p = p.rchild;   }  } }

后序遍历：

双堆栈方法！把所有的元素顺序全都放入temp栈中。stack栈就是一个中间栈。

///二叉树游标后序遍历类public class MyBiTreePostIterator extends MyBiTreeIterator{  	Stack
     
       stack = new Stack
      
       ();	Stack
       
         temp = new Stack
        
         ();	MyBiTreePostIterator()	{			}	MyBiTreePostIterator(MyBiTreeNode root)	{	   super(root);		}			@Override	public void next() {		// TODO Auto-generated method stub		if(this.isComplete)		{			System.out.println("已经遍历到二叉树结尾！");			return ;		}		if(!temp.isEmpty())		{			this.curr = temp.pop();		}		else		{			this.isComplete = true;		}	}	@Override	public void reset() {		// TODO Auto-generated method stub		if (this.root == null) {			this.isComplete = true;		} else {			this.isComplete = false;		}		if (this.root == null) {			return;		}		this.curr = root;				while (this.curr != null || stack.size() > 0)		{                        while (this.curr != null) {                            temp.push(this.curr);                        //System.out.println(this.curr.getData());                        stack.push(this.curr);                            curr = this.curr.getRightChild();                        }                        if (stack.size() > 0) {                            this.curr = stack.pop();                            this.curr = this.curr.getLeftChild();                        }                    }   		this.curr = temp.pop();	}}
        
       
      
     

层序遍历

这里使用的是队列；

//二叉树游标层次遍历类public class MyBiTreeLevIterator extends MyBiTreeIterator {   	Queue
     
       queue = new LinkedList
      
       ();		MyBiTreeLevIterator()	{			}		MyBiTreeLevIterator(MyBiTreeNode root)	{	  super(root);		}	@Override	public void next() {		// TODO Auto-generated method stub		if(this.isComplete)		{			System.out.println("已经遍历到二叉树结尾！");			return ;		}		if(!queue.isEmpty())		{			this.curr = queue.remove();			if(this.curr.getLeftChild()!=null)			{				queue.add(this.curr.getLeftChild());			}			if(this.curr.getRightChild()!=null)			{				queue.add(this.curr.getRightChild());			}		}		else		{			this.isComplete = true;		}	}	@Override	public void reset() {		// TODO Auto-generated method stub		if (this.root == null) {			this.isComplete = true;		} else {			this.isComplete = false;		}		if (this.root == null) {			return;		}		this.curr = root;		if(this.curr.getLeftChild()!=null)		{			queue.add(this.curr.getLeftChild());		}		if(this.curr.getRightChild()!=null)		{			queue.add(this.curr.getRightChild());		}	}		}
      
     

后序遍历的牛逼方法：

在遍历的同时通过flag来判断是否需要打印，如不是flag，则就需找到该节点两侧的子节点。

public static void main(String[] args) {		//这个是创建一个树		BiTreeNode root = Test.makeTree();				final Object flag = new Object(); // 仅作为标记用的对象		Deque

 测试：

public class Test {    	public static MyBiTreeNode makeTree()	{		MyBiTreeNode b,c,d,e,f,g;		g = MyBiTree.getTreeNode(new Character('G'), null, null);		d = MyBiTree.getTreeNode(new Character('D'), null, g);		b = MyBiTree.getTreeNode(new Character('B'), d, null);		e = MyBiTree.getTreeNode(new Character('E'), null, null);		f = MyBiTree.getTreeNode(new Character('F'), null, null);	    c = MyBiTree.getTreeNode(new Character('C'), e, f);	    return MyBiTree.getTreeNode(new Character('A'), b, c);	}		public static void main(String[] args) {				MyBiTreeNode root;		root = Test.makeTree();		System.out.println("前序遍历的结果是：");		MyBiTreeIterator it = new MyBiTreePreIterator(root);				for(it.reset();!it.endOfBiTree();it.next())		{		   System.out.print(it.getData()+" ");			}		System.out.println();				System.out.println("前序遍历的结果是：");		it = new MyBiTreeInIterator(root);						for(it.reset();!it.endOfBiTree();it.next())		{		   System.out.print(it.getData()+" ");			}		System.out.println();				System.out.println("后序遍历的结果是：");		it = new MyBiTreePostIterator(root);						for(it.reset();!it.endOfBiTree();it.next())		{		   System.out.print(it.getData()+" ");			}		System.out.println();				System.out.println("层次遍历的结果是：");		it = new MyBiTreeLevIterator(root);						for(it.reset();!it.endOfBiTree();it.next())		{		   System.out.print(it.getData()+" ");			}		System.out.println();	}}