二叉樹的遍歷-遞歸與非遞歸
二叉樹是一種非常重要的數據結構，很多其它數據結構都是基於二叉樹的基礎演變而來的。對於二叉樹，有前序、中序以及後序三種遍歷方法。因為樹的定義本身就是遞歸定義，因此采用遞歸的方法去實現樹的三種遍歷不僅容易理解而且代碼很簡潔。而對於樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實現。在三種遍歷中，前序和中序遍歷的非遞歸算法都很容易實現，非遞歸後序遍歷實現起來相對來說要難一點。
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
一.前序遍歷
前序遍歷按照“根結點-左孩子-右孩子”的順序進行訪問。
1.遞歸實現
void preOrder1(BinTree *root) //遞歸前序遍歷
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
2.非遞歸實現
方法一：
根據前序遍歷訪問的順序，優先訪問根結點，然後再分別訪問左孩子和右孩子。即對於任一結點，其可看做是根結點，因此可以直接訪問，訪問完之後，若其左孩子不為空，按相同規則訪問它的左子樹；當訪問其左子樹時，再訪問它的右子樹。因此其處理過程如下：
對於任一結點P：
1)訪問結點P，並將結點P入棧;
2)判斷結點P的左孩子是否為空，若為空，則取棧頂結點並進行出棧操作，並將棧頂結點的右孩子置為當前的結點P，循環至1);若不為空，則將P的左孩子置為當前的結點P;
3)直到P為NULL並且棧為空，則遍歷結束。
void preOrder2(BinTree *root) // 非遞歸前序遍歷
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
方法二（更加容易理解的方式）：
初始：維護一個棧，將根節點壓入棧中。
循環：每次從棧頂讀出一個節點信息，直接將節點值輸出，同時將兒子節點按從右到做的順序推到棧頂。
分析：跟遞歸調用的整體思路一樣，不同的是，遞歸調用時是利用運行時系統所維護的程序調用棧來維護順序，而這個非遞歸方法是用過自己維護的棧來保存信息。如此節省了調用棧的空間。
public void preOrderTravNoRecur(Node n) {
Stack<Node> stack= new Stack<Node>();
stack.add(root);
while (!stack.empty()) {
Node t = stack.pop();
System.out.print(t.value + " ");
if (t.rightNode != null)
stack.add(t.rightNode);
if (t.leftNode != null)
stack.add(t.leftNode);
}
}
二.中序遍歷
中序遍歷按照“左孩子-根結點-右孩子”的順序進行訪問。
1.遞歸實現
void inOrder1(BinTree *root) //遞歸中序遍歷
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
}
2.非遞歸實現
根據中序遍歷的順序，對於任一結點，優先訪問其左孩子，而左孩子結點又可以看做一根結點，然後繼續訪問其左孩子結點，直到遇到左孩子結點為空的結點才進行訪問，然後按相同的規則訪問其右子樹。因此其處理過程如下：
對於任一結點P，
1)若其左孩子不為空，則將P入棧並將P的左孩子置為當前的P，然後對當前結點P再進行相同的處理；
2)若其左孩子為空，則取棧頂元素並進行出棧操作，訪問該棧頂結點，然後將當前的P置為棧頂結點的右孩子；
3)直到P為NULL並且棧為空則遍歷結束
void inOrder2(BinTree *root) // 非遞歸中序遍歷
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-07/104853p2.htm
