後序遍歷的遞歸演算法思想

『壹』 後序遍歷的遞歸演算法和非遞歸演算法

隨便手寫一下

struct node_s { data_t data; size_t nchildren; struct node_s *children[MAX]; };

// recursive traverse
// given callback function _access_ with arbitary data _ctx_
void traverse_r( struct node_s *root, void (*access)( struct node_s *node, void *ctx ), void *ctx ) {
int i;
if ( !root ) return;
for ( i=0; i<root->nchildren; i++ )
traverse_r( root->children[i], access, ctx );
access( root, ctx );
}

// needed stack operations
#define stackdef(s,sz) struct elem_s s#_base[sz]; size_t s#_top = 0
#define empty(s) (s##_top==0)
#define push(s,p,i) do{\
struct elem_s *s##_cur = &s##_base[s##_top++];\
s##_cur->node = (p), s##_cur->inext = (i);\
}while(0)
#define pop(s,pp,pi) do{\
struct elem_s *s##_cur = &s##_base[--s##_top];\
*(pp) = s##_cur->node, *(pi) = s##_cur->inext;\
}while(0)
// and data type.
struct elem_s { struct node_s *node; size_t inext; };

// non-recursive traverse
// given callback function _access_ with arbitary data _ctx_
void traverse_s( struct node_s *root, void (*access)( struct node_s *node, void *ctx ), void *ctx ) {
stackdef( s, MAXDEPTH );
struct node_s *cursor; size_t index;
push( s, root, 0 );

while ( ! empty( s ) ) {
pop( s, &cursor, &index );
if ( !cursor ) continue;
if ( cursor->nchildren <= index )
access( cursor, ctx );
else {
push( s, cursor, index + 1 );
push( s, cursor->children[0], 0 );
}
}
}

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

我們的數據結構實驗也是這題，需要我把我的實驗報告給你參考下么！
我這里就只發這部分的代碼。
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網上有許多產品團購,便宜有口碑

『叄』 什麼是先、中、後根遍歷什麼是左子樹、右子樹和二叉樹

1、先根遍歷一般是先序遍歷(Pre-order)，按照根左右的順序沿一定路徑經過路徑上所有的結點。在二叉樹中，先根後左再右。巧記：根左右。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的先根遍歷結果是：ABDECF

6、二叉樹

在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。

『肆』 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(4)後序遍歷的遞歸演算法思想擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。

『伍』 後序遍歷是什麼

對於題圖為後序遍歷為：DECBA。

後序遍歷（LRD）是二叉樹遍歷的一種，也叫做後根遍歷、後序周遊，可記做左右根。後序遍歷有遞歸演算法和非遞歸演算法兩種。

後序遍歷首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。即：

若二叉樹為空則結束返回，

否則：

（1）後序遍歷左子樹

（2）後序遍歷右子樹（3）訪問根結點

如右圖所示二叉樹

後序遍歷結果：DEBFCA

已知前序遍歷和中序遍歷，就能確定後序遍歷。

『陸』 二叉樹遍歷

......1
..../....\
..2.......3
./....../...\
4......5.....6
........\
.........7

根結點為1,則左為42,右5736,再看先根序列24 3576;
左邊42在先根序列中以2為先,則1的下一層為2,再看中根序列42,所以4在2的右邊;
右邊5736在先根序列中以3為先,則3的左邊是57,右邊是6;
在先根序列中5先於7,在中根序列中7在5的右邊;

據此可作上圖

再由上圖寫出後根序列:4275631

答案為:B

『柒』 後序遍歷的遞歸演算法

首先要搞清楚先序、中序、後序的非遞歸演算法共同之處：用棧來保存先前走過的路徑，以便可以在訪問完子樹後,可以利用棧中的信息,回退到當前節點的雙親節點,進行下一步操作。
後序遍歷的非遞歸演算法是三種順序中最復雜的，原因在於，後序遍歷是先訪問左、右子樹,再訪問根節點，而在非遞歸演算法中，利用棧回退到時，並不知道是從左子樹回退到根節點，還是從右子樹回退到根節點，如果從左子樹回退到根節點，此時就應該去訪問右子樹，而如果從右子樹回退到根節點，此時就應該訪問根節點。所以相比前序和後序，必須得在壓棧時添加信息，以便在退棧時可以知道是從左子樹返回，還是從右子樹返回進而決定下一步的操作。 voidpostrav1(structbtnode*bt){structbtnode*p;struct{structbtnode*pt;inttag;}st[MaxSize];inttop=-1;top++;st[top].pt=bt;st[top].tag=1;while(top>-1)/*棧不為空*/{if(st[top].tag==1)/*不能直接訪問的情況*/{p=st[top].pt;top--;if(p!=NULL){top++;/*根結點*/st[top].pt=p;st[top].tag=0;top++;/*右孩子結點*/st[top].pt=p->p->rchild;st[top].tag=1;top++;/*左孩子結點*/st[top].pt=p->lchild;st[top].tag=1;}}}if(st[top].tag==0)/*直接訪問的情況*/{printf("%d",st[top].pt->d);top--;}}演算法2 voidpostrav2(structbtnode*bt){structbtnode*st[MaxSize],*p;intflag,top=-1;if(bt!=NULL){do{while(bt!=NULL){top++;st[top]=bt;bt=bt->lchild;}p=NULL;flag=1;while(top!=-1&&flag){bt=st[top];if(bt->rchild==p){printf("%d",bt->d);top--;p=bt;}else{bt=bt->rchild;flag=0;}}}while(top!=-1)printf(" ");}}