二叉樹後序非遞歸演算法
❶ c語言實現二叉樹的先序,中序,後序的遞歸和非遞歸演算法和層次遍歷演算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣
typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
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是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷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()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}
❷ 《數據結構》遍歷二叉樹的非遞歸演算法的疑問。
首先敬仰一下樓主的勤奮！
我主要針對第二個演算法說，我覺得上面這段話也是在講第二個演算法。其實兩個演算法差不太多。
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()，於是原來那個在棧頂的空指針彈出去了，原來在第二位的指針現在到了棧頂。於是後面那句指的是對這個指針進行操作。
❸ 二叉樹後序遍歷非遞歸演算法
#include
<stdio.h>
#include
<stdlib.h>
struct
tree
{
char
data;
struct
tree
*lchild;
struct
tree
*rchild;
};
typedef
struct
tree
*
treptr;
treptr
build(treptr
t)//先序建樹
{
char
c;
c=getchar();
if(c=='#')
{
t=NULL;
}
else
{
t=(treptr)malloc(sizeof(struct
tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return
t;
}
void
postdorder(treptr
root)//這是遞歸實現
{
if
(root!=NULL)
{
postdorder(root->lchild);
postdorder(root->rchild);
printf("%c",root->data);
}
}
struct
stack
{
treptr
*top,*base;
};
typedef
struct
stack
*stackptr;
void
init
(stackptr
s)//初始化棧
{
s->base=(treptr*)malloc(sizeof(treptr)*100);
s->top=s->base;
}
void
push(stackptr
s,treptr
t)//入棧
{
*(s->top++)=t;
}
treptr
pop(stackptr
s)//彈出棧頂元素
{
treptr
t;
t=*(--(s->top));
return
t;
}
treptr
gettop(stackptr
s)//取棧頂元素
{
treptr
*l=s->top-1;
return
*(l);
}
void
postorder(treptr
t)//這是非遞歸後序實現
{
stackptr
s=(stackptr)malloc(sizeof(struct
stack));
treptr
temp=t;
treptr
p;
treptr
lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist)
{
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
int
main()
{
treptr
t=NULL;
t=build(t);
postdorder(t);
printf("非遞歸後序遍歷\
");
postorder(t);
printf("\
");
return
0;
}
程序如上，可以運行。
我空間中有中序遍歷的非遞歸實現。
不過給你寫的是後序遍歷的遞歸實現和非遞歸實現，它兩個輸出的結果是一致的。
輸入
234##5#6##7##回車
就可以看到結果。
中序遍歷及其對應樹可以參考我空間中的文章
http://hi..com/huifeng00/blog/item/2ca470f56694f62e730eec39.html
❹ 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
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;
}
❺ 如何用非遞歸演算法求二叉樹的高度
if（T＝＝null）
return0；
intfront＝－1，
rear＝－1；
／／front出隊指針
rear入隊指針intlast＝0，
level＝0；
／／last每一層的最右指針
（front＝＝last時候一層遍歷結束level＋＋）BiTreeQ［Maxsize］；
／／模擬隊列Q［＋＋rear］＝T；
BiTreep；
while(front<rear){
p＝Q［＋＋front］；／／開始出隊
因為front要趕到lash
實現level＋＋
if(p->lchild)
Q[++rear] = p->lchild;
if(p->rchild)
Q[++rear] = p->rchild;
if（front＝＝last）｛
level＋＋；
last＝rear；／／last指向下層節點｝
｝
(5)二叉樹後序非遞歸演算法擴展閱讀
非遞歸演算法思想：
（1）設置一個棧S存放所經過的根結點（指針）信息；初始化S；
（2）第一次訪問到根結點並不訪問，而是入棧；
（3）中序遍歷它的左子樹，左子樹遍歷結束後，第二次遇到根結點，就將根結點（指針）退棧，並且訪問根結點；然後中序遍歷它的右子樹。
（4）當需要退棧時，如果棧為空則結束。