其實二叉樹的3種遍歷策略缀台，無非是處理節(jié)點的時機(jī)不同：前序遍歷是在遇到節(jié)點時即處理，中序是在處理完左節(jié)點后再處理哮奇，而后序是在處理完左右節(jié)點后再處理膛腐。
使用非遞歸方法實現(xiàn)時睛约，除了記錄當(dāng)前的節(jié)點的訪問棧，還需要記錄當(dāng)前節(jié)點的狀態(tài)哲身。對于每一個節(jié)點辩涝，我們用0來表示尚未處理左右子節(jié)點，1表示僅僅處理完畢左節(jié)點勘天，2表示左右節(jié)點都處理完畢怔揩。那么，前序脯丝，中序商膊，后序遍歷的唯一不同，無非是將節(jié)點加入序列化結(jié)果集合的時機(jī)不同而已宠进。
Node的定義如下：
class Node{
int value;
Node left;
Node right;
};
下面是通用非遞歸遍歷的代碼（前序晕拆，中序，后序）：
public static final int STATE_NONE=0;//尚未處理任何一個節(jié)點
public static final int STATE_LEFT_DONE=1;//處理完左節(jié)點
public static final int STATE_LEFT_RIGHT_DONE=2;//左右節(jié)點都已經(jīng)處理完
/**
*
*@param node根節(jié)點材蹬，不為null
*@param when 指明處理節(jié)點的時機(jī)实幕，分別對應(yīng)：
* STATE_NONE 前序遍歷
* STATE_LEFT_DONE 中序遍歷
* STATE_LEFT_RIGHT_DONE 后序遍歷
*@return 對應(yīng)的序列化結(jié)果
*/
public static List<Node> traverse(Node node,int when)
{
List<Node> res=new ArrayList<>();//序列化結(jié)果
Stack<Node> stackNode=new Stack<>();//保存節(jié)點的棧
Stack<Integer> stackState=new Stack<>();//保存節(jié)點狀態(tài)的棧
stackNode.push(node); //初始時加入根節(jié)點
stackState.push(STATE_NONE);//標(biāo)記根節(jié)點為尚未處理任何子節(jié)點的狀態(tài)
/*算法說明：
* 初始時放入根節(jié)點，將其標(biāo)記為左右節(jié)點尚未處理的狀態(tài)
* 每個循環(huán)赚导，從棧中取出一個節(jié)點和其狀態(tài)茬缩，根據(jù)其當(dāng)前狀態(tài)轉(zhuǎn)移到下一個狀
態(tài)（很顯然赤惊，你可以從狀態(tài)轉(zhuǎn)換機(jī)的角度解讀這個算法）吼旧。
* 狀態(tài)轉(zhuǎn)換規(guī)則： STATE_NONE-->STATE_LEFT_DONE-->STATE_LEFT_RIGTH_DONE-->彈出棧
* 伴隨狀態(tài)的變化，還需要相應(yīng)的操作未舟，如將左右子節(jié)點放入棧中圈暗，或者將當(dāng)
前節(jié)點彈出棧；最重要的一點是裕膀，當(dāng)當(dāng)前節(jié)點的狀態(tài)符合處理狀態(tài)的要求時员串，就會將節(jié)點加入序列化集合。
*/
while(!stackNode.isEmpty())
{
Node n=stackNode.peek();
Integer state=stackState.peek();
if(state==when)//當(dāng)前狀態(tài)可處理節(jié)點
res.add(n);
//3種狀態(tài)之間的轉(zhuǎn)換
if(state==STATE_NONE)
{
stackState.set(stackState.size()-1,STATE_LEFT_DONE);
if(n.left!=null)
{
stackNode.push(n.left);
stackState.push(STATE_NONE);
}
}else if(state==STATE_LEFT_DONE){
stackState.set(stackState.size()-1,STATE_LEFT_RIGHT_DONE);
if(n.right!=null)
{
stackNode.push(n.right);
stackState.push(STATE_NONE);
}
}else if(state==STATE_LEFT_RIGHT_DONE){
stackNode.pop();
stackState.pop();
}
}
return res;
}
驗證程序：
public static void main(String[] args) {
Node root=new Node(1);
root.left=new Node(2);
root.right=new Node(3);
root.left.left=new Node(4);
root.left.right=new Node(5);
root.right.left=new Node(6);
/* 建立了如下結(jié)構(gòu)的樹
1
2 3
4 5 6
*/
System.out.println("前序:"+traverse(root,STATE_NONE));//前序
System.out.println("中序:"+traverse(root,STATE_LEFT_DONE));//中序
System.out.println("后序:"+traverse(root,STATE_LEFT_RIGHT_DONE));//后序
}
輸出：
前序:[1, 2, 4, 5, 3, 6]
中序:[4, 2, 5, 1, 6, 3]
后序:[4, 5, 2, 6, 3, 1]
證明
性能問題
從上面的證明中昼扛，我們可以看到棧狀態(tài)的變化過程中寸齐，總共10個變化過程，但是只有3個是我們需要處理節(jié)點的狀態(tài)抄谐，其他7個中間狀態(tài)都是無用的渺鹦。實際上，當(dāng)我們知道遍歷順序時蛹含，可以優(yōu)化掉不必要的中間狀態(tài)毅厚。本文只是就理論層面提出了一種統(tǒng)一遍歷的方式，實際中浦箱，我們?nèi)匀皇褂眠f歸方式進(jìn)行遍歷吸耿。
