二叉樹非遞歸演算法
『壹』 二叉樹非遞歸遍歷的演算法
以下為先序，中序，後序三種遞歸演算法
#include
#define MAX 30
typedef struct TreeNode
{
char a;
TreeNode *left;
TreeNode *right;
}TreeNode,*BinTree;
typedef struct
{
TreeNode* data[MAX];
int top;
}SeqStack;
void InitStack(SeqStack &S)
{
S.top=0;
}
int StackEmpty(SeqStack S)
{
if(S.top==0)
return 1;
else return 0;
}
int StackFull(SeqStack S)
{
if(S.top==MAX) return 1;
else return 0;
}
void Push(SeqStack &S,TreeNode *node)
{
if(!StackFull(S))
{
S.data[S.top]=node;
S.top++;
}
else cout<<"Stack is full!\n";
}
void Pop(SeqStack &S,TreeNode* &e)
{
if(!StackEmpty(S))
{
S.top--;
e=S.data[S.top];
}
else cout<<"Stack is empty!";
}
TreeNode* GetTop(SeqStack S)
{
if(!StackEmpty(S))
{
TreeNode *node;
node=S.data[S.top-1];
return node;
}
else cout<<"Stack is empty!";
}
void CreateBinTree(BinTree &T)
{
char b;
cin>>b;
if(b=='0')T=NULL;
else
{
T=new TreeNode;
T->a=b;
CreateBinTree(T->left);
CreateBinTree(T->right);
}
}
void Inorder(BinTree T)
{
TreeNode * p;
SeqStack S;
p=T;
InitStack(S);
while(!StackEmpty(S)||p)
{
while(p)
{
Push(S,p);
p=p->left;
}
if(!StackEmpty(S))
{
Pop(S,p);
cout cout<<"\nA----------二叉樹的建立\n";
cout<<"\nB----------非遞歸先序遍歷\n";
cout<<"\nC----------非遞歸中序遍歷\n";
cout<<"\nD----------非遞歸後序遍歷\n";
cout<<"\nX----------退出\n";
}
void main()
{
BinTree T;
char ch='\0';
bool flag=true;
while(flag)
{
info();
cin>>ch;
switch(ch)
{
case'a':
case'A':
cout<<"請按先序次序輸入結點，空結點用'0'表示:\n";
CreateBinTree(T);
cout<<"二叉樹建立成功!\n";
break;
case'b':
case'B':
cout<<"先序遍歷的結果為:\n";
Preorder(T);
break;
case'c':
case'C':
cout<<"中序遍歷的結果為:\n";
Inorder(T);
break;
case'd':
case'D':
cout<<"後序遍歷的結果為:\n";
Postorder(T);
break;
case'x':
case'X':
flag=false;
break;
default:
cout<<"輸入無效,請重新輸入!\n";
}
}
}
『貳』 《數據結構》遍歷二叉樹的非遞歸演算法的疑問。
首先敬仰一下樓主的勤奮！
我主要針對第二個演算法說，我覺得上面這段話也是在講第二個演算法。其實兩個演算法差不太多。
1. 棧頂記錄中的指針其實就是指棧頂，每次push()進去或者pop()出來的那個p。他代表的是正在訪問的節點得下一個節點。比如，訪問一個樹t的左子樹t->lchild時，棧頂就是t；訪問t->lchild->lchild時，棧頂就是t->lchild。訪問t->rchild時，棧頂為NULL；訪問t->lchild->rchild時，棧頂為t；訪問t->rchild->lchild時，棧頂也是t；訪問t->rchild->rcchild時，棧頂仍為NULL。他的意義就是，在訪問完了當前的子樹之後，就會去訪問棧頂記錄的指針對應的節點的數據。
2. 關於「工作記錄」那個詞，我覺得還是別深究了。那段話意思是要仿照編譯器把遞歸編譯成迭代的思路來自己寫迭代演算法，可是實際上後面給出的演算法里根本沒有嚴格執行上述思路，寫出來的演算法並不是嚴格意義上的可以一般性替換遞歸的迭代演算法。所以追究那個詞也沒意義，明白迭代遍歷的演算法怎麼用就夠了。等以後對遞歸有了更深刻的認識，自然就明白了。其實就是函數遞歸調用自身之前像中斷那樣保存自己的工作環境和進度。
3. （2）句並不矛盾。他說「指針為空時」和「指針指向的xxx」中間不是有句「退回上一層」么，那就表示pop()，於是原來那個在棧頂的空指針彈出去了，原來在第二位的指針現在到了棧頂。於是後面那句指的是對這個指針進行操作。
『叄』 二叉樹中序非遞歸遍歷演算法
對的，實際上如果p=0，是往左探索到頭的意思。先要往左探索到頭，只有到頭了之後才退棧，看右子樹。
探索的過程一直是p=p->lchild，如果p左邊沒有節點了，p->lchild=nullptr了，就說明到頭了，開始執行if的第二個分支：
pop(s,p)實際上是恢復了p上一個狀態，也就是那個葉子節點；
visit(p)，中序訪問就是每pop一個緊接著就訪問一個就是了；
p=p->rchild，訪問右邊，當然，如果右邊還沒有，下次pop的就是p的上上個狀態了，這相當於是從一個葉子節點離開。以此類推。
不明白的可以繼續問。
中序