二叉树的遍历

        二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。


        Java实现二叉树遍历算法相关代码如下：

package cn.xj.bitree;

public class BiTreeNode {
	
	private char data;
	private BiTreeNode leftNode;
	private BiTreeNode rightNode;

	public BiTreeNode(char data, BiTreeNode leftNode, BiTreeNode rightNode) {
		this.data = data;
		this.leftNode = leftNode;
		this.rightNode = rightNode;
	}
	
	public char getData() {
		return data;
	}
	public void setData(char data) {
		this.data = data;
	}
	
	public BiTreeNode getLeftNode() {
		return leftNode;
	}
	public void setLeftNode(BiTreeNode leftNode) {
		this.leftNode = leftNode;
	}
	
	public BiTreeNode getRightNode() {
		return rightNode;
	}
	public void setRightNode(BiTreeNode rightNode) {
		this.rightNode = rightNode;
	}
}

 

package cn.xj.bitree;

import java.util.Stack;

public class BiTree {
	
	private BiTreeNode rootNode;
	
	public BiTree(BiTreeNode rootNode) {
		this.rootNode = rootNode;
	}

	public BiTreeNode getRootNode() {
		return rootNode;
	}
	
	//构造树
	public static BiTreeNode init(){
		BiTreeNode a = new BiTreeNode('A',null,null);  
		BiTreeNode b = new BiTreeNode('B', null, a);   
		BiTreeNode c = new BiTreeNode('C',null,null);   
		BiTreeNode d = new BiTreeNode('D', b, c);   
		BiTreeNode e = new BiTreeNode('E',null,null);   
		BiTreeNode f = new BiTreeNode('F', e, null);   
		BiTreeNode g = new BiTreeNode('G', null, f);   
		BiTreeNode h = new BiTreeNode('H', d, g);   
		return h;// root
	}
	
	//打印节点
	public void visit(BiTreeNode node){
		System.out.print(node.getData()+"");
	}
	
	//递归
	/**递归实现前序遍历:根首先访问*/
	public void preOrder(BiTreeNode node){
		if(node!=null){
			visit(node);
			preOrder(node.getLeftNode());			
			preOrder(node.getRightNode());
		}
	}
	/**递归实现中序遍历:根中间访问*/
	public void midOrder(BiTreeNode node){
		if(node!=null){			
			midOrder(node.getLeftNode());
			visit(node);
			midOrder(node.getRightNode());
		}
	}
	/**递归实现后序遍历:根最后访问*/
	public void poster(BiTreeNode node){
		if(node!=null){
			poster(node.getLeftNode());
			poster(node.getRightNode());
			visit(node);
		}
	}
	
	
	
	
	//非递归
	/**非递归前序遍历*/
	public void iterativePre(BiTreeNode node){
		Stack<BiTreeNode> stack = new Stack<BiTreeNode>();
		if(node!=null){
			stack.push(node);
			while(!stack.isEmpty()){
				node = stack.pop();
				visit(node);  //先访问根节点，栈底节点
				if(node.getRightNode()!=null)
					stack.push(node.getRightNode());//右节点进栈,等同于stack.add(node.getRightNode());					 
				if(node.getLeftNode()!=null)
					stack.push(node.getLeftNode());	//左节点进栈stack.add(node.getLeftNode());			
			}
		}
	}
	/**非递归实现中序遍历*/
	public void iterativeMid(BiTreeNode p){
		Stack<BiTreeNode> stack = new Stack<BiTreeNode>();
		while (p != null) { 
			//先按右中左的顺序把所有节点放入栈；
			while(p!=null){
				if(p.getRightNode()!=null)
					stack.push(p.getRightNode());// 当前节点右子入栈 
				stack.push(p);// 当前节点入栈
				p = p.getLeftNode();			
			}
			p = stack.pop();
			while(!stack.empty()&&p.getRightNode()==null){
				visit(p);
				p = stack.pop();
			}
			visit(p);
			if(!stack.empty())
				p = stack.pop();
			else
				p = null;
		}
	
	}
	/**非递归实现后序遍历*/
	public void iterativePost(BiTreeNode p){
		BiTreeNode q = p;
		Stack<BiTreeNode> stack = new Stack<BiTreeNode>();
		while(p!=null){
			//左子树入栈
			for(;p.getLeftNode()!=null;p=p.getLeftNode())
				stack.push(p);
			//当前节点无右子或右子已经输出
			while(p!=null&&(p.getRightNode()==null||p.getRightNode()==q)){
				visit(p);
				q=p;//记录上一个已输出节点
				if(stack.empty())
					return;
				p = stack.pop();
			}
			//处理右子节点
			stack.push(p);
			p=p.getRightNode();
		}
	}
	
	
	public static void main(String[] args){
		BiTree tree = new BiTree(init());
		
		/**递归*/
		System.out.print("Pre-Order:");
		tree.preOrder(tree.getRootNode());
		System.out.println();
		System.out.print("Mid-Order:");
		tree.midOrder(tree.getRootNode());
		System.out.println();
		System.out.print("Post-Order:");   
		tree.poster(tree.getRootNode());  
		
		System.out.println("\r\n------------");
		
		/**非递归*/
		System.out.print("非递归Pre-Order:");
		tree.iterativePre(tree.getRootNode());
		System.out.println();
		System.out.print("非递归Mid-Order:");
		tree.iterativeMid(tree.getRootNode());
		System.out.println();
		System.out.print("非递归Post-Order:");
		tree.iterativePost(tree.getRootNode());
	}
}