后序遍历的递归算法思想

‘壹’ 后序遍历的递归算法和非递归算法

随便手写一下

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(" ");}}