看了一些關于二叉樹遍歷算法的文章怀大，例如：
二叉樹三種遍歷方式的遞歸和循環(huán)實現
二叉樹的遞歸與非遞歸遍歷（前序凡简、中序逼友、后序）
二叉樹遍歷之morris traversal
回憶了一下二叉樹的遍歷思路，然后用遞歸的方式來寫三種遍歷算法秤涩，都非常簡單帜乞，但是使用非遞歸方式來寫三種遍歷算法就有點繞了。所以總結了一下比較簡單并且邏輯清晰的遍歷算法筐眷。
二叉樹的基本結構
//頭文件
#include <stdio.h>
#include <iostream>
#include <stack> //非遞歸方式用到了棧
//二叉樹基本結構
struct BTree{
std::string value;
BTree* leftChild;
BTree* rightChild;
BTree(const std::string &val, BTree* left = NULL, BTree* right = NULL)
{
value = val;
leftChild = left;
rightChild = right;
}
};
先序（先根）遍歷算法
遍歷順序：根節(jié)點 - 左子節(jié)點 - 右子節(jié)點
這里也可以寫作：根節(jié)點 - 右子節(jié)點 - 左子節(jié)點黎烈。
因為對于二叉樹（非排序二叉樹）來說，先遍歷左節(jié)點還是右節(jié)點實際上是一樣的匀谣，在算法上也只是交換一下所指元素的區(qū)別照棋。
先序、中序振定、后序遍歷算法中的順序，實際上是指的訪問根節(jié)點的順序肉拓。
遞歸實現思路：先處理當前節(jié)點的值后频，然后將左子節(jié)點遞歸處理，最后將右子節(jié)點遞歸處理暖途。
//先序遍歷（遞歸）
void pre_visit_recursive(BTree* root)
{
if(root)
{
std::cout << root->value.c_str() << "\t"; //處理當前節(jié)點值
pre_visit_recursive(root->leftChild); //遞歸處理左子節(jié)點
pre_visit_recursive(root->rightChild); //遞歸處理右子節(jié)點
}
}
非遞歸實現思路：使用棧來保存需要返回后處理的節(jié)點卑惜。
- 如果當前節(jié)點存在，則處理當前節(jié)點的value（先處理根節(jié)點的值）驻售，然后將當前節(jié)點入棧露久，當前節(jié)點指向leftChild，并對leftChild（此時的當前節(jié)點）進行相同處理欺栗。重復1
- （當前節(jié)點不存在）當前節(jié)點指向棧頂元素毫痕，棧頂元素出棧，當前節(jié)點指向rightChild迟几，并對rightChild（此時的當前節(jié)點）進行相同處理消请。重復1
//先序遍歷（非遞歸）
void pre_visit(BTree* root)
{
std::stack<BTree*> stack_tree; //使用棧來保存需要返回再處理的元素
BTree* cur_node = root; //定義一個指針用來指向當前節(jié)點
while(cur_node != NULL || !stack_tree.empty())
{
if(cur_node != NULL)
{
std::cout << cur_node->value.c_str() << "\t"; //處理當前節(jié)點的值
stack_tree.push(cur_node); //當前節(jié)點入棧
cur_node = cur_node->leftChild; //指向左子節(jié)點，進行相同處理
}
else
{
cur_node = stack_tree.top(); //指向棧頂元素类腮，這里不會將棧頂元素出出棧
stack_tree.pop(); //棧頂元素出棧
cur_node = cur_node->rightChild; //指向右子節(jié)點臊泰，進行相同處理
}
}
}
中序遍歷
遍歷順序：左子節(jié)點 - 根節(jié)點 - 右子節(jié)點
遞歸實現思路：先將左子節(jié)點進行遞歸處理，然后處理當前節(jié)點的值蚜枢，最后將右子節(jié)點進行遞歸處理缸逃。
//中序遍歷（遞歸）
void mid_visit_recursive(BTree* root)
{
if(root)
{
mid_visit_recursive(root->leftChild); //左子節(jié)點遞歸處理
std::cout << root->value.c_str() << "\t"; //處理當前節(jié)點的值
mid_visit_recursive(root->rightChild); //右子節(jié)點遞歸處理
}
}
非遞歸實現思路：只用棧來保存需要返回處理的節(jié)點针饥。與先序遍歷類似。
- 如果當前節(jié)點存在需频，則當前節(jié)點入棧丁眼，指向leftChild，并leftChild（此時的當前節(jié)點）進行相同處理贺辰。重復1
- （當前節(jié)點不存在）當前指向棧頂元素户盯，棧頂元素出棧，處理當前節(jié)點值（因為左子節(jié)點不存在或者已經處理完了）饲化，指向rightChild莽鸭，并對rightChild（此時的當前節(jié)點）進行相同處理。重復1
//中序遍歷（非遞歸）
void mid_visit(BTree* root)
{
std::stack<BTree*> stack_tree;
BTree* cur_node = root;
while(cur_node != NULL || !stack_tree.empty())
{
if(cur_node != NULL)
{
stack_tree.push(cur_node); //當前節(jié)點入棧
cur_node = cur_node->leftChild; //指向左子節(jié)點吃靠，進行相同處理
}
else
{
cur_node = stack_tree.top(); //指向棧頂節(jié)點
stack_tree.pop(); //棧頂節(jié)點出棧
std::cout << cur_node->value.c_str() << "\t"; //處理當前節(jié)點的值
cur_node = cur_node->rightChild; //指向右子節(jié)點硫眨，進行相同處理
}
}
}
后序遍歷
遍歷順序：左子節(jié)點 - 右子節(jié)點 - 根節(jié)點
遞歸實現思路：先將左子節(jié)點進行遞歸處理，再將右子節(jié)點進行遞歸處理巢块，最后處理當前節(jié)點的值礁阁。
//后序遍歷（遞歸）
void post_visit_recursive(BTree* root)
{
if(root)
{
post_visit_recursive(root->leftChild); //左子節(jié)點遞歸處理
post_visit_recursive(root->rightChild); //右子節(jié)點遞歸處理
std::cout << root->value.c_str() << "\t"; //處理根節(jié)點的值
}
}
非遞歸實現思路：使用棧來保存需要返回處理的節(jié)點。這里用到了兩個棧族奢，一個用于存放二叉樹節(jié)點姥闭，一個用于存放標志位，0表示處理了左子節(jié)點越走，1表示處理了右子節(jié)點棚品。
后序遍歷與前兩者不同，前兩者在代碼邏輯上區(qū)分處理了左廊敌、右子節(jié)點（即壓棧時铜跑，就已經處理過了左子節(jié)點，出棧后直接指向右子節(jié)點即可）骡澈，但是后續(xù)遍歷存在著需要區(qū)分是否處理過左子節(jié)點的問題（壓棧時左右子節(jié)點都沒有先處理過锅纺，需要等待左右子節(jié)點均處理完后才能處理根節(jié)點的值），所以需要添加標識來判斷當前是否已經處理過左右子節(jié)點肋殴。
- 如果當前節(jié)點存在囤锉，則當前節(jié)點入棧，指向leftChild护锤，標識0入棧嚼锄，并對leftChild（此時的當前節(jié)點）進行相同處理。重復1
- （當前節(jié)點不存在）指向棧頂元素蔽豺，棧頂元素出棧区丑，標志位出棧。如果標志位為0，則當前節(jié)點入棧沧侥，指向rightChild可霎，標識1入棧，并對rightChild（此時的當前節(jié)點）進行步驟1的處理宴杀，重復1癣朗；如果標志位為1，則說明處理過了左右子節(jié)點旺罢，此時處理當前節(jié)點的value旷余，繼續(xù)對棧頂元素進行相同處理（當前節(jié)點置空，重復步驟2扁达，重復2）正卧。
//后序遍歷（非遞歸）
void post_visit(BTree* root)
{
std::stack<BTree*> stack_tree; //保存需要返回處理的節(jié)點
std::stack<int> stack_flag; //保存返回的路徑標識
BTree* cur_node = root;
while(cur_node != NULL || !stack_tree.empty())
{
if(cur_node != NULL)
{
stack_tree.push(cur_node); //當前節(jié)點入棧
stack_flag.push(0); //下一步處理leftChild，返回時從leftChild返回跪解，保存標識為0
cur_node = cur_node->leftChild; //指向leftChild炉旷，進行步驟1處理
}
else
{
cur_node = stack_tree.top(); //指向棧頂元素
stack_tree.pop(); //節(jié)點出棧
int flag = stack_flag.top(); //獲取返回路徑
stack_flag.pop(); //標識出棧
if(flag == 0)
{
//從leftChild返回，此時應該處理rightChild
stack_tree.push(cur_node); //當前節(jié)點入棧
stack_flag.push(1); //下一步處理rightChild叉讥，保存標識1
cur_node = cur_node->rightChild; //指向rightChild窘行，進行步驟1處理
}
else
{
//從rightChild返回，此時應該處理根節(jié)點的值
std::cout << cur_node->value.c_str() << "\t"; //處理根節(jié)點的值
cur_node = NULL; //為了進行步驟2图仓，根據循環(huán)邏輯罐盔，這里要將cur_node置空
}
}
}
}
最后測試用的代碼如下：
int main()
{
BTree* A = new BTree("A");
BTree* B = new BTree("B");
BTree* C = new BTree("C");
BTree* D = new BTree("D");
BTree* E = new BTree("E");
BTree* F = new BTree("F");
A->leftChild = B;
A->rightChild = C;
B->leftChild = D;
B->rightChild = E;
C->leftChild = F;
//測試代碼
std::cout << "先序遍歷-遞歸" << std::endl;
pre_visit_recursive(A);
std::cout << std::endl;
std::cout << "先序遍歷-非遞歸" << std::endl;
pre_visit(A);
std::cout << std::endl;
std::cout << "中序遍歷-遞歸" << std::endl;
mid_visit_recursive(A);
std::cout << std::endl;
std::cout << "中序遍歷-非遞歸" << std::endl;
mid_visit(A);
std::cout << std::endl;
std::cout << "后序遍歷-遞歸" << std::endl;
post_visit_recursive(A);
std::cout << std::endl;
std::cout << "后序遍歷-非遞歸" << std::endl;
post_visit(A);
std::cout << std::endl;
getchar();
return 0;
}
結果：
先序遍歷-遞歸
A B D E C F
先序遍歷-非遞歸
A B D E C F
中序遍歷-遞歸
D B E A F C
中序遍歷-非遞歸
D B E A F C
后序遍歷-遞歸
D E B F C A
后序遍歷-非遞歸
D E B F C A
總結
上述算法只是相對便于理解的寫法，對于后續(xù)遍歷的非遞歸算法肯定還有更高效的解救崔。
除了了解二叉樹的遍歷惶看，還應該了解二叉樹的應用場景，以及優(yōu)勢與劣勢帚豪。
