一直想要寫的 二叉樹 中序 先序 後序遍歷算法
當年學習DS最虛的就是這個，因為非遞歸算法復雜，測試數據不好弄，只能一個一個手動插入。感覺明顯比圖的難，雖然大家都覺得圖更難。。。。。
遞歸的太簡單了，就不寫了。關鍵是非遞歸版本。
二叉樹的常見問題及其解決程序 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
先序：
我自己的版本：
void RootPreTraverse(Node* p)
{
Stack S;
while(S not empty)
{
p=S.top();
S.pop();
Show(p);
if(p->right!=null)
S.push(p->right);
if(p->left!=null)
S.push(p->left);
}
}
後來發現和層序遍歷有點相似，區別就在於 用了棧而不是隊列，而且入的順序換一換，否則到時出棧就錯了。
感覺有點微妙，雖然比較容易寫出來，但是還是有點懸乎，隊列換棧差異這麼大！
這個版本(感覺不好寫) http://www.linuxidc.com/Linux/2014-06/102935p2.htm
void BT_PreOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
visit(root);
s.push(root);
root = root->left;
}
else //該版本代碼相比於下面比較清sang,
{
root = s.top();
s.pop();
root = root->right;
}
}
}
下面這個和上面是一個思路 http://www.linuxidc.com/Linux/2014-06/102935p3.htm
void preorder_dev(bintree t){
seqstack s;
s.top = -1; //因為top在這裡表示了數組中的位置，所以空為-1
if(!t){
printf("the tree is empty\n");
}else{
while(t || s.stop != -1){
while(t){ //只要結點不為空就應該入棧保存，與其左右結點無關
printf("%c ",t->data);
push(&s,t);
t= t->lchild;
} //令有一個版本 http://www.linuxidc.com/Linux/2014-06/102935p4.htm ，這裡加了判斷if(S not empty()), 感覺有點畫蛇添足。因為此處如果棧為空則說明上面while 一定沒執行，t為空,同時S empty()那麼上一次外層while已經退出了，遍歷結束了。可見，此處棧必不空，上面url樓主加了一個永真判斷
t=pop(&s);
t=t->rchild;
}
}
}
中序：http://www.linuxidc.com/Linux/2014-06/102935p2.htm
01.void BT_InOrderNoRec(pTreeT root)
02.{
03. stack<treeT *> s;
04. while ((NULL != root) || !s.empty())
05. {
06. if (NULL != root)
07. {
08. s.push(root);
09. root = root->left;
10. }
11. else
12. {
13. root = s.top();
14. visit(root);
15. s.pop();
16. root = root->right;
17. }
18. }
19.}
//和上面preorder_dev 幾乎如出一轍，從一個show 的地方就可以看出本質區別，贊博主
void midorder(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!\n");
}else{
while(t ||s.top != -1){
while(t){
push(&s,t);
t= t->lchild;
}
t=pop(&s);
printf("%c ",t->data);
t=t->rchild;
}
}
}
後序由於有點復雜，先擱置，集中力量打擊主要部分。
從邏輯上看，兩人其實是一樣的，如果t不空，執行if,到while 因此次數if 等價於裡面執行while，如果t空，則執行else,與另一個代碼一致
另外看這裡 http://www.linuxidc.com/Linux/2014-06/102934.htm
遞歸轉非遞歸的模式其實不大general。。所以這個還得暫時沒有通用方法。。。
後序
//用一個標志位記錄是否 左右孩子是否已經被壓過棧，如果壓過棧了，如果沒壓棧，會先壓站，然後再把該節點壓站，因為後面
還要訪問(後序)，此外還需要把標志位
void PostOrder(TNode* root)
{
Stack S;
if( root != NULL )
{
S.push(root);
}
while ( !S.empty() )
{
TNode* node = S.pop();
if ( node->bPushed )
{ // 如果標識位為true,則表示其左右子樹都已經入棧，那麼現在就需要訪問該節點了
Visit(node);
}
else
{ // 左右子樹尚未入棧，則依次將 右節點,左節點,根節點 入棧
if ( node->right != NULL )
{
node->right->bPushed = false; // 左右子樹均設置為false
S.push(node->right);
}
if ( node->left != NULL )
{
node->left->bPushed = false;
S.push(node->left);
}
node->bPushed = true; // 根節點標志位為true
S.push(node);
}
}
}
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-06/102935p2.htm