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;
}
}
}
}本回答被提问者采纳
#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;
}
