Question

数据结构（C语言版）问题？求大神帮忙解答

写出非递归后序遍历二叉树算法

Answer 1

typedef struct ErChaNode{
ErChaNode * pZuo;
ErChaNode * pYou;
char data;
}*PErChaNode,**PPErChaNode,*PStackData;

void PostorderWhileStack(PErChaNode pShugen){
if (pShugen==NULL) return;
PStack se=createStack();
PErChaNode pNode = pShugen;
while (pNode)
{
push(&se,pNode);
if (pNode->pZuo) pNode = pNode->pZuo;
else pNode = pNode->pYou;
}
while (!stackEmpty(se))
{
PErChaNode pNode = top_stack(se);
pop(&se);
printf("%c ",pNode->data);
if (!stackEmpty(se) && pNode == top_stack(se)->pZuo)
{
pNode = top_stack(se)->pYou;
while (pNode)
{
push(&se,pNode);
if (pNode->pZuo)pNode = pNode->pZuo;
else pNode = pNode->pYou;
}
}
}
}

Answer 2

#include<stdio.h>

#include<malloc.h>

typedef struct st{

char data;

struct st *r;

struct st *l;

}*link,ll;

char s[20]="ABC##DE##F##G##";//二叉树序列 

int i=0;

void create_tree(link &tree)//先序递归建树 

{

if(s[i]=='#') 

tree=NULL,i++;

else

{

tree=(link)malloc(sizeof(ll)); 

tree->data=s[i],i++;

create_tree(tree->l);

create_tree(tree->r);

}

}

void behind_1(link tree)//递归后序遍历 

{

if(tree)

{

behind_1(tree->l);

behind_1(tree->r);

printf("%c ",tree->data);

}

}

void behind_2(link tree)//非递归后序遍历 

{

     link T;

     link s[20];//人工栈 

int flag[20];//标记结点

    int top=0;

     T=tree;

     while(top!=0||T){

         while(T)

         {

             s[top++]=T;

             flag[top-1]=0;

             T=T->l;

          } 

          while(top!=0&&flag[top-1]==1){

              T=s[--top];

              printf("%c ",T->data);

          }

          if(top!=0){

              flag[top-1]=1;

              T=s[top-1];

              T=T->r;

          }

          else   break;

     }

}

int main()

{

link T=NULL; 

create_tree(T);//建树 

printf("递归后序遍历二叉树\n"); 

behind_1(T);//递归后序遍历 

printf("\n非递归后序遍历二叉树\n"); 

behind_2(T);//非递归后序遍历 

return 0;

}