java构造二叉树并且实现先，中，后序遍历

关于二叉树的基本概念前面已经有所涉及，这里不在赘述:

一些基本概念可以参考这里:

http://blog.csdn.net/yalishadaa/article/details/54851324

下面直接使用代码实现:

package bbb;public class TreeNode {	PRivate TreeNode left;	private TreeNode right;	private char data;	public TreeNode(char data,TreeNode left, TreeNode right) {		super();		this.left = left;		this.right = right;		this.data = data;	}	public TreeNode(char data) {		super();		this.data = data;	}	public TreeNode getLeft() {		return left;	}	public void setLeft(TreeNode left) {		this.left = left;	}	public TreeNode getRight() {		return right;	}	public void setRight(TreeNode right) {		this.right = right;	}	public char getData() {		return data;	}	public void setData(char data) {		this.data = data;	}		}
package bbb;public class Bintree {		public TreeNode initTree(){				TreeNode A=new TreeNode('A');		TreeNode B=new TreeNode('B',A,null);		TreeNode C=new TreeNode('C');		TreeNode D=new TreeNode('D',B,C);		TreeNode E=new TreeNode('E');		TreeNode F=new TreeNode('F',E,null);		TreeNode G=new TreeNode('G',null,F);		TreeNode H=new TreeNode('H',D,G);		return H;	}	public void visitNode(TreeNode node){		System.out.print(node.getData()+" ");	}	//先序遍历	public void preOrder(TreeNode t){		if(t!=null){			visitNode(t);			preOrder(t.getLeft());			preOrder(t.getRight());		}					}	//中序遍历	public void midOrder(TreeNode t){		if(t!=null){			midOrder(t.getLeft());			visitNode(t);			midOrder(t.getRight());		}			}	//后续遍历	public void tailOrder(TreeNode t){		if(t!=null){		tailOrder(t.getLeft());		tailOrder(t.getRight());		visitNode(t);		}	}	/**	 * @param args	 */	public static void main(String[] args) {		// TODO Auto-generated method stub		Bintree myTree=new Bintree();		TreeNode t=myTree.initTree();		myTree.preOrder(t);		System.out.println();		myTree.midOrder(t);		System.out.println();		myTree.tailOrder(t);	}}最后是输出的结果:
前面遍历二叉树是使用递归方式实现的，效率比较低下，下面使用非递归方式遍历二叉树,使用一个堆栈来存放节点，
具体的规则如下:
1.前序遍历
对于任一节点P，
1）输出节点P，然后将其入栈，再看P的左孩子是否为空；
2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作；
3）若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；
4）若不为空，则循环至1）操作；
5）如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复4）和5）操作；
        6）直到当前节点P为NULL并且栈空，遍历结束。
2.中序遍历
对于任一节点P，
1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3）若不为空，则重复1）和2）的操作；
4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
5）直到当前节点P为NULL并且栈为空，则遍历结束。
3.后序遍历
对于任一节点P，
1）先将节点P入栈；
2）若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；
3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；
4）直到栈空，遍历结束。
具体的实现代码如下:
//非递归方式实现	public void unPreOrder(TreeNode t){		Stack< TreeNode> s=new Stack<TreeNode>();		 while (t != null || !s.empty()) {  	            while (t != null) {  	            	visitNode(t) ;	                s.push(t);  	                t = t.getLeft();  	            }  	            if (!s.empty()) {  	                t = s.pop();  	                t = t.getRight();  	            }  	        }  	}	public void unmidOrder(TreeNode t){		Stack< TreeNode> s=new Stack<TreeNode>();		while (t != null || !s.empty()) {              while (t != null) {                  s.push(t);                  t = t.getLeft();              }              if (!s.empty()) {                  t = s.pop();                  visitNode(t) ;                t = t.getRight();              }          }  	}	public void untailOrder(TreeNode t){		 Stack<TreeNode> s = new Stack<TreeNode>();  	        Stack<Integer> s2 = new Stack<Integer>();  	        Integer i = new Integer(1);  	        while (t != null || !s.empty()) {  	            while (t != null) {  	                s.push(t);  	                s2.push(new Integer(0));  	                t = t.getLeft();  	            }  	            while (!s.empty() && s2.peek().equals(i)) {  	                s2.pop();  	                	                visitNode(s.pop());	            }  	  	            if (!s.empty()) {  	                s2.pop();  	                s2.push(new Integer(1));  	                t = s.peek();  	                t = t.getRight();  	            }  	        }  	}最后是输出的结果: