1. 二叉樹遍歷定義
遍歷二叉樹，即遵從某種次序訪問二叉樹中的所有節點，使得每個節點僅被訪問一次。這裡提到的“訪問”是指對節點施行某種操作，可以是輸出節點信息，修改節點值等，但要求這種訪問不破壞它原來的數據結構。在本文中，遍歷操作操作為訪問並輸出節點值，且以二叉鏈表作為二叉樹的存貯結構。由於二叉樹是一種非線性結構，每個節點可能有一個以上的直接後繼，因此，必須規定遍歷的規則，並按此規則遍歷二叉樹，最後得到二叉樹所有節點的一個線性序列。
令L,R,D分別代表二叉樹的左子樹、右子樹、根節點，則遍歷二叉樹有6種規則：DLR、DRL、LDR、LRD、RDL、RKD。若規定二叉樹中必須先左後右(左右順序不能顛倒)，則只有DLR、LDR、LRD三種遍歷規則。DLR稱為前根遍歷(或前序遍歷、先序遍歷、先根遍歷)，LDR稱為中根遍歷(或中序遍歷)，LRD稱為後根遍歷(或後序遍歷)。
二叉樹結構定義為：
typedef struct _BinaryTreeNode
{
int value;
struct _BinaryTreeNode* pLeft; //指向左子節點的指針
struct _BinaryTreeNode* pRight; //指向右子節點的指針
}BinaryTreeNode_t;
2.先根遍歷
所謂先根遍歷，就是根節點最先遍歷，其次左子樹，最後右子樹。
2.1 遞歸遍歷
先根遍歷二叉樹的遞歸遍歷算法描述為：
若二叉樹為空，則算法結束；否則
1）輸出根節點；
2）先根遍歷左子樹；
3）先根遍歷右子樹；
void PreOrder(BinaryTreeNode_t* pRoot)
{
BinaryTreeNode_t* p;
p = pRoot;
if (p != NULL)
{
std::cout<<p->value<<" ";
PreOrder(p->pLeft);
PreOrder(p->pRight);
}
}
2.2 非遞歸遍歷
利用棧存儲二叉樹節點，算法思想為：
從二叉樹根節點開始，沿左子樹一直走到末端(左孩子為空)為止。在走的過程中，訪問所遇節點，並依次把所遇節點進棧，當左子樹為空時，從棧頂退出某節點，並將指針指向該節點的右孩子。如此重復，直到棧為空或指針為空止。
void PreOrder(const BinaryTreeNode_t* pRoot)
{
std::stack<BinaryTreeNode_t*> s;
BinaryTreeNode_t* p;
p = pRoot;
while(p != NULL || s.size()>0)
{
while(p != NULL)
{
//訪問當前節點
std::cout<<p->value<<std::endl;
//將當前節點入棧
s.push(p);
//訪問其左兒子
p = p->pLeft;
}
//處理完左兒子，再處理右子兒子
p = s.top();
s.pop();
p = p->pRight;
}
}
3. 中根遍歷
所謂中根遍歷，就是根在中間，先左子樹，然後根節點，最後右子樹。
3.1 遞歸遍歷
中根遍歷二叉樹的遞歸遍歷算法描述為：
若二叉樹為空，則算法結束；否則
1） 中根遍歷左子樹;
2） 輸出根節點;
3） 中根遍歷右子樹；
void InOrder(BinaryTreeNode_t* pRoot)
{
BinaryTreeNode_t* p;
p = pRoot;
if (p != NULL)
{
InOrder(p->pLeft);
cout<<p->value<<" ";
InOrder(p->pRight);
}
}
3.2 非遞歸遍歷
同樣使用棧來存貯二叉樹節點，算法思想為：
從二叉樹根節點開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，把依次遇到的節點進棧，待左子樹為空時，從棧中退出節點並訪問，然後再轉向它的右子樹。如此重復，直到棧空或指針為空止。
void InOrder(const BinaryTreeNode_t* pRoot)
{
stack<BinaryTreeNode_t*> s;
BinaryTreeNode_t* p;
p = pRoot;
while(p != NULL || s.size()>0)
{
//一直訪問左兒子
while(p != NULL)
{
s.push(p);
p = p->pLeft;
}
//指向棧頂元素，即左兒子為NULL的節點
p = s.top();
//彈出該節點並訪問
s.pop();
std::cout<<p->value<<std::endl;
//同樣處理其右兒子
p = p->pRight;
}
}
4. 後根遍歷
所謂後根遍歷，就是根在最後，即先左子樹，然後右子樹，最後根節點。
4.1 遞歸遍歷
後根遍歷二叉樹的遞歸遍歷算法描述為：
若二叉樹為空，則算法結束;否則
1）後根遍歷左子樹:
2）後根遍歷歷子樹;
3）訪問根節點。
void PostOrder(BinaryTreeNode_t* pRoot)
{
BinaryTreeNode_t* p;
p = root;
if (p != NULL)
{
PostOrder(p->pLeft);
PostOrder(p->pRight);
cout<<p->value<<" ";
}
}
4.2 非遞歸遍歷
利用棧來實現二叉樹的後根遍歷要比前序和中序遍歷復雜得多。在後根遍歷中，當搜索指針指向某一個節點時，不能馬上進行訪問，而先要遍歷左子樹，所以此節點應先進棧保存，當遍歷完它的左子樹後，再次回到該節點，還不能訪問它，還需先遍歷其右子樹。只有等它的右子樹遍歷完後再次退棧時才能訪問該節點。
void PostOrder(const BinaryTreeNode_t* pRoot)
{
stack<BinaryTreeNode_t*> s;
BinaryTreeNode_t* p;
BinaryTreeNode_t* pre = NULL;
p = pRoot;
while(p != NULL || s.size()>0)
{
//一直向左遍歷左子節點
while(p != NULL)
{
s.push(p);
p = p->pLeft;
}
//指向棧頂元素，即最後一個左兒子為NULL的節點
p = s.top();
//p = p->pRight;
//如果該節點的右兒子也為空，則其為葉子節點，訪問該節點
//如果該節點的右兒子已經被訪問過，則訪問該節點
if(p->pRight == NULL || p->pRight == pre)
{
//p = s.top();
std::cout<<p->value<<std::endl;
s.pop();
pre = p;
p = NULL;
}
//該節點右兒子不為空，同樣遍歷其右兒子為根節點的子樹
else
p = p->pRight;
}
}
本文出自 “redpaopaw” 博客，請務必保留此出處http://redpaopaw.blog.51cto.com/7900594/1297972
