二叉树的非递归遍历算法
关键词：二叉树，中序，前序，后序遍历，非递归
作者：BIce 创建时间：2012-09-24 00:31:21
今天面试碰到了二叉树遍历的问题，由于之前都用递归写，觉得很整洁就没有考虑过这个问题，面对这个问题就发挥不是很好。回来后经过考虑和实验，总结了下中序、前序和后序非递归算法的具体实现。总结下，放到下面。
关于这个问题，应该有不同的实现方法。下面简单的算法的思想大致就是用Stack来模拟递归的实现，并且向Node中加入一个boolean的childPushed来标识节点是否已经展开过，可以访问。Java代码如下：
package main;
import java.util.Stack;
public class TestBinTree {
public class Node{
//树的节点类.
private int id;
private String value;
public Node left;
public Node right;
public boolean childPushed=false;//用于判别是否已经执行过压栈
Node(int id,String value){
this.id=id;
this.value=value;
left=null;
right=null;
}
}
private Node root=null; //测试用根
private Node [] nodeList;//方便快速访问
TestBinTree(){
//生成测试用的树及跟
//生成一个50个节点的完全二叉树来进行测试
int n=50;
nodeList=new Node[n+1];
root=new Node(1,1+"-");
nodeList[1]=root;
for(int i=2;i<=n;i++){
Node temp=new Node(i,i+"-");
nodeList[i]=temp;
if(i%2==0){//左子节点
nodeList[i/2].left=temp;
}
else{
nodeList[i/2].right=temp;
}
}
}
public String PreOrder(Node node){
if(node==null)return "";
String order="";
order+=node.value;
order+=PreOrder(node.left);
order+=PreOrder(node.right);
return order;
}
public String InOrder(Node node){
if(node==null) return "";
String order="";
order+=InOrder(node.left);
order+=node.value;
order+=InOrder(node.right);
return order;
}
public String PostOrder(Node node){
if(node==null) return "";
String order="";
order+=PostOrder(node.left);
order+=PostOrder(node.right);
order+=node.value;
return order;
}
public String PreOrderNoRecursion(Node node){
Stack<Node> stack=new Stack<Node>();
stack.push(root);
String retStr="";
while(!stack.isEmpty()){
Node item=stack.pop();
retStr+=item.value;
if(item.right!=null)
stack.push(item.right);
if(item.left!=null)
stack.push(item.left);
}
return retStr;
}
public String InOrderNoRecursion(Node node){
Stack<Node> stack=new Stack<Node>();
stack.push(root);
String retStr="";
while(!stack.isEmpty()){
Node item=stack.pop();
if(item.left==null||item.childPushed){
retStr+=item.value;
item.childPushed=false;
continue;
}
if(item.right!=null)
stack.push(item.right);
stack.push(item);
if(item.left!=null)
stack.push(item.left);
item.childPushed=true;
}
return retStr;
}
public String PostOrderNoRecursion(Node node){
Stack<Node> stack=new Stack<Node>();
stack.push(root);
if(root.right!=null)
stack.push(root.right);
if(root.left!=null)
stack.push(root.left);
root.childPushed=true;
String retStr="";
while(!stack.isEmpty()){
Node item=stack.pop();
if(item.childPushed){
retStr+=item.value;
item.childPushed=false;
continue;
}
else{
stack.push(item);
if(item.right!=null)
stack.push(item.right);
if(item.left!=null)
stack.push(item.left);
item.childPushed=true;
}
}
return retStr;
}
public void Test(){
//PreOrder
if(PreOrder(root).equals(PreOrderNoRecursion(root))){
System.out.println("PreOrder Ok!");
}
else{
System.out.println("PreOrder:"+PreOrder(root));
System.out.println("PreOrderNoRecursion:"+PreOrderNoRecursion(root));
}
//InOrder
if(InOrder(root).equals(InOrderNoRecursion(root))){
System.out.println("InOrder Ok!");
}
else{
System.out.println("InOrder:"+InOrder(root));
System.out.println("InOrderNoRecursion:"+InOrderNoRecursion(root));
}
//PostOrder
if(PostOrder(root).equals(PostOrderNoRecursion(root))){
System.out.println("PostOrder Ok!");
}
else{
System.out.println("PostOrder:"+PostOrder(root));
System.out.println("PostOrderNoRecursion:"+PostOrderNoRecursion(root));
}
}
public static void main(String [] args){
TestBinTree testCase=new TestBinTree();
testCase.Test();
}
}