0. 前言
遞歸是計(jì)算機(jī)中基本而實(shí)用的算法思想。
主要用于解決有邊界的重復(fù)性操作問(wèn)題，即滿足數(shù)學(xué)歸納法特性的問(wèn)題。比如斐波那契數(shù)列埃唯。
可遞歸卻有不少缺陷：運(yùn)行效率低下、遞歸過(guò)多容易棧溢出等等鹰晨。
但作為一把鋒刃的解題利器墨叛，我們也不能拋棄它。眾所周知模蜡，遞歸的本質(zhì)即為棧漠趁，它運(yùn)行在內(nèi)存中，受操作系統(tǒng)控制忍疾，一個(gè)函數(shù)就是棧中的一個(gè)單位(棧幀)闯传。遞歸的過(guò)程，就是內(nèi)存中棧的入棧出棧操作卤妒。
因而甥绿，我們必然可以用自定義的棧來(lái)實(shí)現(xiàn)這個(gè)過(guò)程字币，即將遞歸轉(zhuǎn)化為非遞歸。
那如何快速地將一個(gè)遞歸程序轉(zhuǎn)化為一個(gè)非遞歸程序呢共缕？我想用樹(shù)的先洗出、中、后序遍歷图谷，來(lái)表述我的一己之見(jiàn)翩活。
1. 樹(shù)的先、中便贵、后序遍歷(遞歸模式)
1.1. 先中后序遍歷解釋
對(duì)于一棵樹(shù)菠镇，先序遍歷先輸出根結(jié)點(diǎn)的數(shù)據(jù)、再輸出左孩子樹(shù)的數(shù)據(jù)嫉沽、最后輸出右孩子樹(shù)的數(shù)據(jù)辟犀。簡(jiǎn)而言之，輸出順序?yàn)?strong>根—左—右绸硕。
以此類推堂竟，中序和后序遍歷的輸出順序分別為：左—根—右、左—右—根玻佩。
1.2. 示例
對(duì)于如下的一棵樹(shù)：
A
B C
D E F
G H J
I K L
先序遍歷：ABDEGIHKLCFJ
中序遍歷：DBIGEKHLACFJ
后序遍歷：DIGKLHEBJFCA
1.3. 遞歸實(shí)現(xiàn)遍歷
先中后序遍歷一棵樹(shù)出嘹，代碼十分簡(jiǎn)單。如下：
// 樹(shù)的數(shù)據(jù)結(jié)構(gòu)
typedef struct BTNode {
char data;
BTNode *lchild, *rchild;
}BTNode, *BiTree;
// 先序遍歷咬崔，遞歸
void preOrderTraverse(BiTree bTree) {
if (bTree) {
cout<<bTree->data; // 先輸出根節(jié)點(diǎn)的數(shù)據(jù)
preOrderTraverse(bTree->lchild); // 輸出左子樹(shù)的數(shù)據(jù)
preOrderTraverse(bTree->rchild); // 輸出右子樹(shù)的數(shù)據(jù)
}
}
// 中序遍歷税稼，遞歸
void inOrderTraverse(BiTree bTree) {
if (bTree) {
inOrderTraverse(bTree->lchild);
cout<<bTree->data;
inOrderTraverse(bTree->rchild);
}
}
// 后序遍歷，遞歸
void postOrderTraverse(BiTree bTree) {
if (bTree) {
postOrderTraverse(bTree->lchild);
postOrderTraverse(bTree->rchild);
cout<<bTree->data;
}
}
2. 非遞歸遍歷
2.1. 遞歸到非遞歸轉(zhuǎn)換分析
對(duì)于遞歸的非遞歸轉(zhuǎn)換垮斯，我們以函數(shù)棧的角度去解析就十分簡(jiǎn)單了郎仆。
以中序的遞歸遍歷為例：
typedef struct BTNode {
char data;
BTNode *lchild, *rchild;
} BTNode, *BiTree;
// 中序遍歷，遞歸
void inOrderTraverse(BiTree bTree) {
if (bTree) {
inOrderTraverse(bTree->lchild);
cout<<bTree->data;
inOrderTraverse(bTree->rchild);
}
}
當(dāng)主函數(shù)inOrderTraverse(bTree)中第一個(gè)inOrderTraverse(bTree->lchild)子函數(shù)被調(diào)用時(shí)兜蠕，主函數(shù)中剩余的數(shù)據(jù)和步驟被保留在當(dāng)前的函數(shù)棧幀中扰肌。而子函數(shù)入函數(shù)棧，成為棧頂函數(shù)熊杨。當(dāng)子函數(shù)運(yùn)行結(jié)束曙旭，返回時(shí)，子函數(shù)出棧晶府，棧頂又變?yōu)橹骱瘮?shù)桂躏。然后，程序繼續(xù)執(zhí)行主函數(shù)中的剩余步驟川陆。
同理子函數(shù)的子函數(shù)也是如此操作剂习。過(guò)程如下：
主函數(shù)入棧：
主函數(shù)調(diào)用第一個(gè)子函數(shù)的操作出棧，剩余步驟保存在棧中，而被調(diào)用子函數(shù)(藍(lán)色)入棧：
顯而易見(jiàn)进倍，這就是一個(gè)出棧入棧的過(guò)程土至。函數(shù)保存在棧幀中的操作和數(shù)據(jù)购对，我們可以通過(guò)自定義的棧來(lái)儲(chǔ)存猾昆。
2.2. 非遞歸的實(shí)現(xiàn)
如果，棧中可以存放操作語(yǔ)句骡苞，那非遞歸的實(shí)現(xiàn)將會(huì)變得十分容易垂蜗，可惜，棧中只能存放數(shù)據(jù)解幽。
不過(guò)贴见，幸運(yùn)的是，遞歸的操作都是重復(fù)的躲株，我們只要將數(shù)據(jù)統(tǒng)一片部，并根據(jù)數(shù)據(jù)進(jìn)行相對(duì)應(yīng)操作即可。
在樹(shù)的遞歸遍歷中霜定，其實(shí)只有一個(gè)操作档悠，那就是輸出結(jié)點(diǎn)數(shù)據(jù)，而剩余函數(shù)只是個(gè)入棧的過(guò)程望浩。
以中序遞歸遍歷為例：
依次將右孩子（第二個(gè)子函數(shù)）辖所、根結(jié)點(diǎn)（輸出數(shù)據(jù)操作）、左孩子（第一個(gè)子函數(shù)）入棧磨德。
然后檢測(cè)棧頂過(guò)程中缘回，遇到不為空的左/右孩子，則重復(fù)上述入棧操作典挑；遇到根結(jié)點(diǎn)則輸出數(shù)據(jù)酥宴；棧頂指針為空則出棧。
但是您觉，如何判斷是孩子拙寡、還是根結(jié)點(diǎn)呢？我認(rèn)為可以有兩種方法：
（1）設(shè)計(jì)一個(gè)結(jié)構(gòu)體作為椆擞蹋基本單位倒庵。該結(jié)構(gòu)體有兩個(gè)值：一個(gè)用來(lái)判斷是根結(jié)點(diǎn)（根結(jié)點(diǎn)則輸出數(shù)據(jù)）還是孩子（孩子則右-根-左入棧）的標(biāo)志位，另一個(gè)是指向樹(shù)的指針：
// 中序遍歷炫刷，非遞歸第一種方法
typedef struct {
bool flag; // 用來(lái)判斷是根結(jié)點(diǎn)(true)還是孩子(false)
BiTree bTree; // 樹(shù)指針
}Node;
void inOrderTraverse1(BiTree bTree) {
if (!bTree) {
cout<<"該樹(shù)為空擎宝！";
return;
}
cout<<"非遞歸中序遍歷：";
stack<Node> s;
Node temp, top;
temp.flag = false;
temp.bTree = bTree;
s.push(temp);
while (!s.empty()) {
top = s.top();
s.pop();
// 如果棧頂樹(shù)指針為空，則不操作
if (top.bTree == NULL) continue;
// 如果是根結(jié)點(diǎn)
if (top.flag) {
cout << top.bTree->data;
}
// 如果是孩子
else {
temp.flag = false;
temp.bTree = top.bTree->rchild;
s.push(temp);
temp.flag = true;
temp.bTree = top.bTree;
s.push(temp);
temp.flag = false;
temp.bTree = top.bTree->lchild;
s.push(temp);
}
}
cout << endl;
}
（2）將樹(shù)結(jié)點(diǎn)作為棧的基本單位浑玛。設(shè)置一種數(shù)據(jù)結(jié)點(diǎn)绍申，只存放數(shù)據(jù)，而左右孩子為空。每次檢測(cè)棧頂結(jié)點(diǎn)极阅，若左右孩子為空則輸出胃碾，否則依次將不為空的右孩子、根結(jié)點(diǎn)的數(shù)據(jù)結(jié)點(diǎn)筋搏、不為空的左孩子入棧：
// 中序非遞歸遍歷仆百，第二種算法
void inOrderTraverse2(BiTree bTree) {
if (!bTree) {
cout<<"該樹(shù)為空！";
return;
}
cout<<"非遞歸中序遍歷：";
stack<BTNode> s;
s.push(*bTree);
BTNode temp, dataBTNode;
dataBTNode.lchild = dataBTNode.rchild = NULL;
while (!s.empty()) {
temp = s.top();
s.pop();
if (!temp.lchild && !temp.rchild) cout<<temp.data;
else {
dataBTNode.data = temp.data;
if (temp.rchild) s.push(*temp.rchild);
s.push(dataBTNode);
if (temp.lchild) s.push(*temp.lchild);
}
}
cout<<endl;
}
3. 后話
實(shí)際上奔脐，遞歸并非我們想象中那么拖慢效率俄周。在不至于遞歸棧爆的情況下，我們還是可以放心地使用遞歸的髓迎。
