後序遍歷的非遞歸演算法

❶ 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
}

❷ 求一個二叉樹的後序遍歷非遞歸演算法

// 中序遍歷偽代碼：非遞歸版本，用棧實現，版本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)

}

❸ 求二叉樹的前序遍歷和後序遍歷的演算法（非遞歸）

網路一下就可以知道答案了。直接搜」二叉樹的前序遍歷和後序遍歷的演算法「

第一條就是：

http://blog.csdn.net/sky04/article/details/4510266

我只解釋一下先序遍歷非遞歸演算法，其他的自學一下吧！：

//先序遍歷非遞歸演算法

voidPreOrderUnrec(Bitree*t)
{
Stacks;
StackInit(s);//初始化
Bitree*p=t;//二叉樹根節點

while(p!=NULL||!StackEmpty(s))
{
while(p!=NULL)//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;//lchild左子樹
}

if(!StackEmpty(s))//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;//rchild右子樹
}//endif

}//endwhile
}

/*Stacks；創建堆棧。這也是堆棧的一個應用。既然你已經學到了二叉樹，就應該知道堆棧，可以把以前編寫的堆棧程序拿來用。
POP，PUSH堆棧的彈出，壓棧。
按照該程序步驟，來演示s和指針p的內容：（完全二叉樹為例）
前序遍歷次序為：ABCDEFG
1.第一次執行while語句後
棧s[底部，ABC]p=NULL訪問了：ABC節點
2.第一次執行if
棧s[底部，AB]p=NULL訪問了：ABC節點由於c的右子樹為空，所以p=NULL
3.第二次跳過了while
4.第二次執行if
棧s[底部，A]p指向了D訪問了：ABC節點
5.第三次執行while語句後
棧s[底部，AD]p=NULL訪問了：ABCD節點，本次while循環，只訪問了D
。
。
。
剩下步驟的自己來吧!
實際上，遞歸也是在操作堆棧。
一般的書上應該有這么類似的話：
「利用一個輔助堆棧，可以將遞歸演算法轉化為等價的分遞歸演算法」

*/

❹ 後序遍歷非遞歸演算法

#include<stdio.h>
#include <stdlib.h>
#define maxsize 50
typedef struct Bnode //聲明二叉樹的數據結構
{
char data;
struct Bnode *lchild,*rchild;
}bnode,*btree;
typedef struct type
{
btree node;
int flag;
}datatype,*pdatatype;
typedef struct{ //聲明棧的數據結構
datatype data[maxsize];//pdatatype data[maxsize]; //類型改為datatype
int top;
}seqstack,*pseqstack;
int i=0;
btree creatbtree(char *s) //創建二叉樹
{
btree t;
if(s[i]=='#')
{t=NULL;i++;}
else
{
t=(btree)malloc(sizeof(bnode));
t->data=s[i];i++;
t->lchild=creatbtree(s);
t->rchild=creatbtree(s);
}
return t;
}
void postorder(btree t) //二叉樹的後序遍歷(非遞歸)
{
int cout;
pseqstack p;
//pdatatype sq;
//sq=(pdatatype)malloc(sizeof(datatype));
p=(pseqstack)malloc(sizeof(seqstack));
p->top=0;
while(t||!(p->top==0))
{
if(t)
{
//sq->flag=0;
//sq->node=t;
//p->data[p->top]=sq;
p->data[p->top].node = t;
p->data[p->top].flag = 0;
(p->top)++;
t=t->lchild;
}
else
{
//sq=p->data[(p->top)-1];
//t=sq->node;
if(p->data[p->top-1].flag==0)
{
p->data[p->top-1].flag=1;
//sq->node=t;
//p->data[p->top]=sq;
//(p->top)++;
t = p->data[p->top-1].node->rchild;//t=t->rchild;
}
else
{
printf("%c",p->data[p->top-1].node->data); //printf("%c",t->data);
(p->top)--;

//printf("%c",t->data);
//t=NULL;

}
}
}
}

main()
{
btree t;
char *s;
s="abd#g###ce##fh###";
t=creatbtree(s);
printf("\n後序遍歷：");
postorder(t);

}

❺ 二叉樹後序遍歷（非遞歸）

一，大循環中的第一個循環，當前節點一直往左走一直走到頭，並且把走過的節點壓棧，這個循環遍歷完成後，棧裡面都是左邊走過但是右邊還沒有走過的節點

二，從最左邊那個沒有更左的那個節點，它位於棧頂，因為這時棧頂不是一個右節點，第二個循環跳過，然後把棧頂結點的右節點標記為r並以此作為根節點重復之前的操作

回溯：
因為一直往下層走，總會遇到既沒有左節點有沒有右節點的節點，就是葉子節點，就開始往回退 取他的右節點，取之前會把該節點標記為r，但是他沒有右節點，為null，就會跳過第一個循環，來到第二個，那麼這個葉子就從棧中pop掉，新的棧頂結點是那個葉子的父節點，如果沒有右節點，那他就成了葉子，更簡單，如果有右節點，那麼繼續二

一步一步推就是這樣子，需要考慮所有情況，會把問題想復雜，但是利用遞歸的思想就好想了
參考遞歸演算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一個函數就是第一個小循環，只走左邊，然後把新得到的節點作為根節點，繼續調用第一個函數，得到左節點，然後再作為根節點，直到左節點為空；
第二個函數就是最後一個if，非遞歸演算法中是從棧頂取，就是左邊走過了的節點，相當於遞歸中，第一個函數執行完已經返回，然後取他的右節點作為根節點，繼續遞歸
以上回答你滿意么？

❻ 二叉樹的遍歷演算法

這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
1.先序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{

Bitree
Elem[maxsize];

int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//訪問根結點
p=p->rchild;
//通過下一次循環實現右子樹遍歷
}//endif
}//endwhile
}//InOrderUnrec
3.後序遍歷非遞歸演算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍歷左子樹
{
x.ptr
=
p;
x.tag
=
L;
//標記為左子樹
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag為R，表示右子樹訪問完畢，故訪問根結點
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec

❼ 二叉樹後序遍歷非遞歸演算法

#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

❽ 後序遍歷的非遞歸演算法是什麼

對於樹的遍歷我們最常用的三種遍歷方法分別是前序遍歷、中序遍歷和後序遍歷，使用的方法是深度優先遍歷樹的每一個節點，這些遍歷方法都是使用遞歸函數來進行實現的。

在數據量大的情況下是比較低效的，原因在於系統幫助我們調用了一個棧並且做了諸如保護現場和恢復現場等復雜的操作。

才使得遍歷可以使用非常簡單的代碼來實現，所以我們可以模仿系統中調用的棧自己可以來寫一下棧，模仿其中的過程就可以完成對於三種遍歷演算法的實現，使用自定義的棧來代替系統棧可以得到效率上的提升，下面是對於後序遍歷的非遞歸演算法的實現。

簡介

從逆後序遍歷與先序遍歷的關系中我們可以知道逆後序遍歷序列為先序遍歷交換左右子樹的遍歷順序得到的。

所以我們得到了逆後序序列之後然後逆序就可以得到後序遍歷的序列了，所以需要兩個棧，第一個棧用來存儲先序遍歷交換左右子樹的遍歷的中介結果。

❾ 下面是後序遍歷二叉樹的非遞歸演算法的實現，別人寫的，但看不太明白，求詳細解釋！

先明白後序遍歷的原理，再看程序就容易了。後序遍歷先訪問左子樹，再訪問右子樹，最後訪問根。但你的程序從根開始查找，所以先把查找過的根放入棧中（後進先出），然後訪問左子樹，在根據棧頂的根節點訪問右子樹（右子樹依然要從根判斷），最後訪問根，訪問完後，可以彈出根節點了。那麼上一層的根節點就處於棧頂了。這個沒人能給你講清楚。你看懂了，編程和樹的遍歷也就都懂了。

❿ 後序遍歷（ 用遞歸和非遞歸的方法一起都要）

我們的數據結構實驗也是這題，需要我把我的實驗報告給你參考下么！
我這里就只發這部分的代碼。
Status PreOrderTraverse(BiTree T)
{
//先序遍歷二叉樹T的遞歸演算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status PreOrder(BiTree T)
{
//先序遍歷二叉樹T的非遞歸演算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍歷二叉樹T的遞歸演算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍歷二叉樹T的非遞歸演算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//後序遍歷二叉樹T的遞歸演算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//後序遍歷二叉樹T的遞歸演算法
unsigned sign;//記錄結點從棧中彈出的次數
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到結點T時壓入其指針
push(1);//置標志為1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走過T的左子樹
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子樹都已走過
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}
另外,團IDC網上有許多產品團購,便宜有口碑