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

Question

void PostOrder(BiTree T)//后序遍历非递归算法 { SqStack S; InitStack(S); ////建立栈 BiTree P; P=T; BiTree lastvist = NULL; while (NULL!=T||!StackEmpty(S)) { while (P!=NULL) { Push(S,P); //压栈 P= P->lchild; } GetTop(S,P); //返回栈顶元素 if (NULL==P->rchild||lastvist==P->rchild) { printf("%c",P->data); Pop(S,lastvist); //弹出栈 P = P->rchild; } } } 这是C语言数据结构的算法 大家看下我这个哪里错了 编译的时候没错 但就是运行到这个程序的时候就不能运行后面的算法 程序就中断了 后面这是我的主程序 运行只能显示到后序非递归 ··· void main() //主函数 { printf("请输入先序建立二叉树所需要的数据，空树以0输入："); BiTree t; CreateBiTree(t); printf("前序非递归算法输出为："); Preorder(t); printf("\ "); printf("中序非递归算法输出为："); InOrderTraverse(t); printf("\ "); printf("后序非递归算法输出为："); PostOrder(t); printf("\ "); printf("前序递归算法输出为："); PreOrderT(t); printf("\ "); printf("中序递归算法输出为："); InOrderT(t); printf("\ "); printf("后序递归算法输出为："); PostOrderT(t); printf("\ ");

Answer 1

#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.baidu.com/huifeng00/blog/item/2ca470f56694f62e730eec39.html