二叉樹非遞歸遍歷演算法
A. 怎樣實現二叉樹的前序遍歷的非遞歸演算法
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此時棧已空，就有問題
}
pBiNode = pBiNode->rchild;
}
return 0;
}
B. 求一個二叉樹的後序遍歷非遞歸演算法
// 中序遍歷偽代碼：非遞歸版本，用棧實現，版本2
void InOrder2(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);
}
node->bPushed = true; // 根節點標志位為true
S.push(node);
if ( node->left != NULL )
{
node->left->bPushed = false;
S.push(node->left);
}
}
}
}
對比先序遍歷，這個演算法需要額外的增加O(n)的標志位空間。另外，棧空間也擴大，因為每次壓棧的時候都壓入根節點與左右節點，因此棧空間為O(n)。時間復雜度方面，每個節點壓棧兩次，作為子節點壓棧一次，作為根節點壓棧一次，彈棧也是兩次。因此無論從哪個方面講，這個方法效率都不及InOrder1。
後序
void postOrder(TreeNode<T> *root)
{
stack<TreeNode<T>*> st;
TreeNode<T> *p = root;
TreeNode<T> *pre = NULL;//pre表示最近一次訪問的結點
while(p || st.size()!=0)
{
//沿著左孩子方向走到最左下 。
while(p)
{
st.push(p);
p = p->left;
}
//get the top element of the stack
p = st.top();
//如果p沒有右孩子或者其右孩子剛剛被訪問過
if(p->right == NULL || p->right == pre)
{
/ isit this element and then pop it
cout << "visit: " << p->data << endl;
st.pop();
pre = p;
p = NULL;
}
else
{
p = p->right;
}
}//end of while(p || st.size()!=0)
}
C. c語言二叉樹非遞歸遍歷
我們今天講了一點
我寫了下函數部分。。其實我也不太懂！
void PreOrderTraverse(struct tree *p) /*進行先序遍歷*/
{ top=0;
bool;
do
{
while(p)
{
s[top]=p;
top++;
p=p->lch;
top--;
if(top==0)
bool=0;
else{
top--;
p=s[top];
printf(p->data);
p=p->rch;
}
}while(bool)
}
void InOrderTraverse(struct tree *p) /*進行中序遍歷*/
{
top=0;
bool;
do
{
while(p)
{
s[top]=p;
top++;
p=p->lch;
if(top==0)
bool=0;
else{
top--;
p=s[top];
printf(p->data);
p=p->rch;
}
}while(bool)
}
後序遍歷我也不怎麼會寫！不過我可以給你說一下原理：
先是一個p->data入棧，入棧的時候給它標記下，用i=1記一下，
然後是他的左子樹，p=p->lch;p->data要出棧，這時候做一次判斷。看P的標記i是多少，是1的話就不讓他出來，返回去並且i+1，變成2；然後繼續前面的動作!等到第二次出棧時做同樣的判斷，i=2，就出棧！並輸出！！希望對你有所幫助！
D. 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此時棧已空，就有問題
}
pBiNode = pBiNode->rchild;
}
return 0;
}
E. 二叉樹的非遞歸遍歷
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
typedef struct BiTNode
{
int data;
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
void visit(int e)
{
printf("->%d",e);
}
void InitBiTree(BiTree &T)// 操作結果：構造空二叉樹T
{
T=NULL;
}
void CreateBiTree(BiTree &T)
//按先序次序輸入二叉樹中結點的值,構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。
{
int number;
scanf("%d",&number); // 輸入結點的值
if(number==0) // 結點的值為空
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}
void DestroyBiTree(BiTree &T)// 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
{
if(T) // 非空樹
{
DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
//二叉樹T存在，Visit是對結點操作的應用函數,先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
{
if(T) //T不為空時遍歷
{
Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
//二叉樹T存在，Visit是對結點操作的應用函數，中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
{
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
// 二叉樹T存在，Visit是對結點操作的應用函數，後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
{
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}
void main()
{
char m;
BiTree T;
InitBiTree(T); // 初始化二叉樹T
do{
printf("\n");
printf("##################二叉樹的基本操作###########################\n");
printf("×××××××××1.二叉樹的創建××××××××××××××\n");
printf("×××××××××2.先序遞歸遍歷二叉樹×××××××××××\n");
printf("×××××××××3.中序遞歸遍歷二叉樹×××××××××××\n");
printf("×××××××××4.後序遞歸遍歷二叉樹×××××××××××\n");
printf("×××××××××5.退出程序××××××××××××××××\n");
printf("#############################################################\n");
printf("請輸入你的選擇:");
scanf("%c",&m);
switch(m) {
case '1':
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，如：（1 2 3 0 0 4 5 0 6 0 0 7 0 0 0）\n");
printf("\n請按先序次序輸入二叉樹中結點的值：");
CreateBiTree(T); // 建立二叉樹T
break;
case '2':
printf("先序遞歸遍歷二叉樹： ");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
break;
case '3':
printf("\n中序遞歸遍歷二叉樹： ");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
break;
case '4':
printf(" \n後序遞歸遍歷二叉樹：");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
break;
case '5':break;
default:
printf("輸入的字元不對，請重新輸入!");
break;
}
getchar();
}while(m!='5');
}
F. 二叉樹後序遍歷非遞歸演算法程序跪求解釋
一，大循環中的第一個循環，當前節點一直往左走一直走到頭，並且把走過的節點壓棧，這個循環遍歷完成後，棧裡面都是左邊走過但是右邊還沒有走過的節點
二，從最左邊那個沒有更左的那個節點，它位於棧頂，因為這時棧頂不是一個右節點，第二個循環跳過，然後把棧頂結點的右節點標記為r並以此作為根節點重復之前的操作
回溯：
因為一直往下層走，總會遇到既沒有左節點有沒有右節點的節點，就是葉子節點，就開始往回退 取他的右節點，取之前會把該節點標記為r，但是他沒有右節點，為null，就會跳過第一個循環，來到第二個，那麼這個葉子就從棧中pop掉，新的棧頂結點是那個葉子的父節點，如果沒有右節點，那他就成了葉子，更簡單，如果有右節點，那麼繼續二
一步一步推就是這樣子，需要考慮所有情況，會把問題想復雜，但是利用遞歸的思想就好想了
參考遞歸演算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一個函數就是第一個小循環，只走左邊，然後把新得到的節點作為根節點，繼續調用第一個函數，得到左節點，然後再作為根節點，直到左節點為空；
第二個函數就是最後一個if，非遞歸演算法中是從棧頂取，就是左邊走過了的節點，相當於遞歸中，第一個函數執行完已經返回，然後取他的右節點作為根節點，繼續遞歸
G. 二叉樹中序遍歷的非遞歸演算法
推薦這篇文章，把二叉樹的前序、中序和後續的遞歸和非遞歸演算法都講了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html
H. 二叉樹非遞歸遍歷演算法c語言
給你個離散數學中的演算法:
先序:
1. 將根節點放入棧中
2.while 棧不空
do
3. 從棧中取出一個節點,並visit
4. 將這個節點右孩子,左孩子(如果存在)分別放入棧中
endwhile
中序:
1.將根節點放入棧中
2.while 棧不空
do
3. 從棧中取出一個節點
4. if 節點被標記
5. then visit 該節點 並將右孩子放入棧(如果存在)
else
6. 將該節點標記並入棧
7. 將該節點的左孩子入棧(如果存在)
endif
endwhile
後序:
1.將根節點放入棧中
2.while 棧不空
do
3. 從棧頂取一節點
4. if 節點被標記
5. then visit 該節點
else
6. 將該節點標記並入棧
7. 將該節點的右孩子,左孩子分別入棧(如果存在)
endif
endwhile
I. 二叉樹中序非遞歸遍歷演算法
對的，實際上如果p=0，是往左探索到頭的意思。先要往左探索到頭，只有到頭了之後才退棧，看右子樹。
探索的過程一直是p=p->lchild，如果p左邊沒有節點了，p->lchild=nullptr了，就說明到頭了，開始執行if的第二個分支：
pop(s,p)實際上是恢復了p上一個狀態，也就是那個葉子節點；
visit(p)，中序訪問就是每pop一個緊接著就訪問一個就是了；
p=p->rchild，訪問右邊，當然，如果右邊還沒有，下次pop的就是p的上上個狀態了，這相當於是從一個葉子節點離開。以此類推。
不明白的可以繼續問。
中序
J. 先序遍歷二叉樹的非遞歸演算法
InitStack(S);//初始化棧
p=T;//取棧頂
while(P||!StackEmpty(S)){ //P存在或者棧非空
if(p) { //p非空，即左子樹或者右子樹存在
Push(S,p); //將左子樹入棧
p=p->lchild; //取下一個左子樹
}
else{
Pop(S,p); //出棧，相當於先序遍歷了，因為左子樹都TMD入棧了，現在反向輸出
p=p->rchild; //彈出一個左子樹，就同時取其右子樹右子樹，然後又跳到這個if的最開頭那裡，p存在的那個分支。接下來再取右子樹的左子樹
}
}
//其實，用遞歸也許你更能理解一些。但是，遞歸本質上也是壓棧，只不過是程序壓棧，還不如這個效率高