前言
在數(shù)據(jù)結(jié)構(gòu)教材中的中序遍歷非遞歸形式過程中發(fā)現(xiàn)每次遍歷到葉子結(jié)點(diǎn)的時候鸯隅，都會把NULL空結(jié)點(diǎn)放入棧中澜建。
從而讓我思考這個空結(jié)點(diǎn)是否有必要放入棧中？
為了順理成章引出該問題蝌以。文章的前半部分講述中序遍歷的基本過程炕舵。
不想看的同學(xué)直接看最后一部分。想要加深對二叉樹遍歷的印象的同學(xué)推薦還是瀏覽一遍跟畅。
中序遍歷
遞歸形式
要求形式一：不加入空結(jié)點(diǎn)
① 先遍歷左結(jié)點(diǎn)
② 遍歷完中結(jié)點(diǎn)后咽筋，假如有右節(jié)點(diǎn)就遍歷右節(jié)點(diǎn)；沒有則返回上級徊件。
按照要求可以寫出這樣的遞歸形式
InOrderTraverse(BiTree* tree)
{
if(tree->lchild)//滿足要求①
InOrderTraverse(tree->lchlid);
Visit(tree->data);
if(tree->rchild)//滿足要求②奸攻，其中一部分
InOrderTraverse(tree->rchild);
//在函數(shù)結(jié)束后就會返回至上級調(diào)用該函數(shù)的地方
}
也可以這樣理解中序遍歷
要求形式二：加入空結(jié)點(diǎn)
① 如果該節(jié)點(diǎn)存在，就按要求遍歷左中右虱痕；不存在就返回睹耐。
InOrderTraverse(BiTree* tree)
{
if(tree)
{
InOrderTraverse(tree->lchild);
Visit(tree->data);
InOrderTraverse(tree->rchild);
}
}
非遞歸形式
依照遞歸形式的執(zhí)行過程中遞歸工作棧的狀態(tài)變化模擬出非遞歸形式。
為了引出不加空結(jié)點(diǎn)的方法部翘，先按照 要求二：加入空結(jié)點(diǎn) 的理解疏橄。
1、這里需要一個堆棧s略就，用來模擬每次遞歸過程中的工作棧捎迫。
2、用一個最外層的while循環(huán)表示每一個新結(jié)點(diǎn)的調(diào)用與返回表牢。
因此代碼會是這樣
bool InOrderTraverse(BiTree* tree, TreeVisiter visit)
{
std::stack<BiTree*> s;
s.push(tree);
//繼續(xù)分析 要求二方式的遞歸 中棧里面存的是什么的過程中窄绒，
//會發(fā)現(xiàn)棧中存入的是每一個未被訪問過的結(jié)點(diǎn)和空結(jié)點(diǎn)。
//所以棧未空時崔兴，表示樹遍歷結(jié)束
while(!s.empty())
{
//...
}
return true;
}
步驟1彰导、獲取棧頂結(jié)點(diǎn)蛔翅，如果結(jié)點(diǎn)存在，就先遍歷左結(jié)點(diǎn)位谋。
tree = s.top();
if(tree)
{
s.push(tree->lchild);//注意這里可以會把空結(jié)點(diǎn)存入棧中山析。
continue;//開始下一個循環(huán)，因?yàn)閷⑼鈱觲hile循環(huán)定義為訪問每個新結(jié)點(diǎn)
}
步驟2掏父、如果結(jié)點(diǎn)不存在笋轨，則先退出空節(jié)點(diǎn)，再訪問該結(jié)點(diǎn)赊淑。最后訪問右孩子爵政。
s.pop();
tree = s.top();//c++中top()是獲取棧頂，不退棧
s.pop();
if(!visit(tree->data)) return false;
s.push(tree->rchild);//這里的右孩子可能是空結(jié)點(diǎn)
結(jié)合后代碼就會變?yōu)槿缦?/p>
bool InOrderTraverse(BiTree* tree, TreeVisiter visit)
{
std::stack<BiTree*> s;
s.push(tree);
while(!s.empty())
{
//------------------------------
//可優(yōu)化處
tree = s.top();
if(tree)
{
s.push(tree->lchild);//注意這里可以會把空結(jié)點(diǎn)存入棧中陶缺。
continue;//開始下一個循環(huán)
}
//------------------------------
s.pop();
if(!s.empty())
{
tree = s.top();
s.pop();
if(!visit(tree->data)) return false;
s.push(tree->rchild);
}
}
return true;
}
考慮整個while循環(huán)過程中钾挟，會發(fā)現(xiàn)在 可優(yōu)化處 的地方可以用一個while稍微優(yōu)化一下。
//訪問空結(jié)點(diǎn)代碼
bool InOrderTraverse(BiTree* tree, TreeVisiter visit)
{
std::stack<BiTree*> s;
s.push(tree);
while(!s.empty())//外層while循環(huán)
{
//------------------------------
while((tree = s.top()) && tree)
s.push(tree->lchild);
//------------------------------
s.pop();//彈出空結(jié)點(diǎn)
if(!s.empty())
{
tree = s.top();
s.pop();
if(!visit(tree->data)) return false;
s.push(tree->rchild);
}
}
return true;
}
假如優(yōu)化成這樣的話饱岸，那么對外層while循環(huán)的定義也就和前邊的不一樣了掺出。
不再是 “用一個最外層的while循環(huán)表示每一個新結(jié)點(diǎn)的調(diào)用與返回∩环眩”（也許你可能忘了）
就變成兩個定義了：
外層while循環(huán)新定義1：如果該結(jié)點(diǎn)存在汤锨，訪問當(dāng)前結(jié)點(diǎn)的最左結(jié)點(diǎn)，再右移一位黍衙。
外層while循環(huán)新定義2：如果該結(jié)點(diǎn)為空結(jié)點(diǎn)，則返回至兄弟結(jié)點(diǎn)荠诬。（如果一直都是NULL琅翻，那么就一直返回）
定義1 如下圖的 紅線 部分
定義2 如下圖的 藍(lán)線 部分
空結(jié)點(diǎn)是否有必要放入棧中？
問題1：為什么要彈出空結(jié)點(diǎn)柑贞？
看到代碼方椎，給我的第一個反應(yīng)是：很簡單呀，因?yàn)橥鈱拥膚hile循環(huán)多放了一個空結(jié)點(diǎn)钧嘶。
這是第一個原因棠众。
當(dāng)我嘗試在外層的while循環(huán)中加入空結(jié)點(diǎn)判斷，不加入空結(jié)點(diǎn)時有决，發(fā)現(xiàn)代碼就會陷入死循環(huán)闸拿。
因?yàn)樵撎帍棾隹战Y(jié)點(diǎn)并不僅僅是為了彈出外層的while循環(huán)中的空結(jié)點(diǎn)。
還為了右結(jié)點(diǎn)為空時返回至兄弟結(jié)點(diǎn)书幕。
問題2：如果在每次入棧之前判斷一次是否為空結(jié)點(diǎn)會怎么樣新荤？會不會減少入棧次數(shù)的同時減少判斷次數(shù)？
從圖像上看台汇，遍歷的過程少了一些苛骨。主要是少了葉子個數(shù)的循環(huán)次數(shù)篱瞎。看來 可能 是有效果的痒芝。
如果遵循上圖的訪問規(guī)則俐筋，外層while循環(huán)的定義很明顯地就不一樣了。
外層while循環(huán)在不訪問NULL結(jié)點(diǎn)的新定義：
訪問當(dāng)前結(jié)點(diǎn)的最左結(jié)點(diǎn)严衬，然后尋找下一個存在的合適結(jié)點(diǎn)（右孩子澄者，否則是右兄弟，否則是右叔叔瞳步，否則是右爺爺闷哆，否則是右祖父，否則是......）
于是改寫了一下代碼单起。
//不訪問空結(jié)點(diǎn)代碼
bool InOrderTraverse_non_recursive_1(BiTree* tree, TreeVisiter visit)
{
std::stack<BiTree*> s;
s.push(tree);
while(!s.empty())
{
tree = s.top();
while(tree->lchild)
{
tree = tree->lchild;
s.push(tree);
}
s.pop();
if(!visit(tree->data)) return false;
tree = tree->rchild;
//尋找下一個存在的合適結(jié)點(diǎn)
while(!tree)
{
if(s.empty())//在尋找的過程中可能是最后一個結(jié)點(diǎn)了
return true;
tree = s.top();
s.pop();
if(!visit(tree->data)) return false;
tree = tree->rchild;
}
s.push(tree);
}
return true;
}
總結(jié)：
在加入棧之前判斷下該結(jié)點(diǎn)是否為空抱怔，只加入不為空的結(jié)點(diǎn)，在效率上較加入空結(jié)點(diǎn)會有一點(diǎn)點(diǎn)的改進(jìn)嘀倒。只是代碼長度可能會多那么幾行屈留。
