本文共 2278 字，大约阅读时间需要 7 分钟。

二叉树的递归遍历比较简单，这里就不聊了。今天主要聊聊二叉树的非递归遍历，主要借助于“栈”后进先出的特性来保存节点的顺序，先序遍历和中序遍历相对来说比较简单，重点理解后序遍历。

1. 先看看节点类型：

//二叉树的节点类型	private class Node{
   		int data;   //节点值		Node leftChild;  //左孩子		Node rightChild; //右孩子		public Node(int data) {
   			this.data=data;		}	}

2.先序遍历。非递归先序遍历的思路如下：

1.先将根节点入栈 2.访问根节点 3.如果根节点存在右孩子，则将右孩子入栈 4.如果根节点存在左孩子，则将左孩子入栈（注意：一定是右孩子先入栈，然后左孩子入栈） 5.重复2-4

public void preOrder(Node Root) {
   		if(Root==null) {
   			System.out.println("空树");			return;		}		Node tmp=Root;		Stack
   
     s=new Stack
    
     ();		s.push(tmp);  //根节点入栈		while(!s.empty()) {
   			//1.访问根节点			Node p=s.pop();			System.out.print(p.data+" ");			//2.如果根节点存在右孩子，则将右孩子入栈			if(p.rightChild!=null) {
   				s.push(p.rightChild);			}			//3.如果根节点存在左孩子，则将左孩子入栈			if(p.leftChild!=null) {
   				s.push(p.leftChild);			}		}		System.out.println();	}
    
   

3.中序遍历。 非递归中序遍历的思路如下：

1.先将根节点入栈 2.将当前节点的所有左孩子入栈，直到左孩子为空 3.访问栈顶元素，如果栈顶元素存在右孩子，则继续第2步 4.重复第2、3步，直到栈为空并且所有的节点都被访问

public void inOrder(Node Root) {
   		if(Root==null) {
   			System.out.println("空树");			return;		}		Node tmp=Root;		Stack
   
     s=new Stack
    
     ();		while(tmp!=null || !s.empty()) {
   			//1.将根节点入栈			//2.将所有左孩子入栈			while(tmp!=null) {
   				s.push(tmp);				tmp=tmp.leftChild;			}			//3.访问栈顶元素			tmp=s.pop();			System.out.print(tmp.data+" ");			//4.如果栈顶元素存在右孩子，则将右孩子赋值给tmp，也就是将右孩子入栈			if(tmp.rightChild!=null) {
   				tmp=tmp.rightChild;			}			//否则，将tmp置为null，表示下次要访问的是栈顶元素			else {
   				tmp=null;			}		}		System.out.println();	}
    
   

4.后序遍历。 后续遍历的非递归实现思路：

1.根节点入栈 2.将根节点的左子树入栈，直到最左，没有左孩子为止 3.得到栈顶元素的值，先不访问，判断栈顶元素是否存在右孩子，如果存在并且没有被访问，则将右孩子入栈，否则，就访问栈顶元素

public void postOrder(Node Root) {
   		if(Root==null) {
   			System.out.println("空树");			return;		}		Node tmp=Root;  //当前节点		Node prev=null; //上一次访问的节点		Stack
   
     s=new Stack
    
     ();		while(tmp!=null || !s.empty()) {
   			//1.将根节点及其左孩子入栈			while(tmp!=null) {
   				s.push(tmp);				tmp=tmp.leftChild;			}						if(!s.empty()) {
   				//2.获取栈顶元素值				tmp=s.peek();				//3.没有右孩子，或者右孩子已经被访问过				if(tmp.rightChild==null || tmp.rightChild==prev) {
   					//则可以访问栈顶元素					tmp=s.pop();					System.out.print(tmp.data+" ");					//标记上一次访问的节点					prev=tmp;					tmp=null;				}				//4.存在没有被访问的右孩子				else {
   					tmp=tmp.rightChild;				}			}		}		System.out.println();	}
    
   

转载地址：http://mohzi.baihongyu.com/