我好不容易写了二叉树的递归遍历算法,然后写非递归的
结果发现不知道为什么PUSH跟POP函数在非递归中起不了作用,结果我用数组暂时替代了。。。请问我的PUSH跟POP应该怎么去修改呢?
还有后序遍历的非递归算法应该怎么写?
#include<stdio.h>
typedef struct bitree
{char data;
struct bitree *lchild;
struct bitree *rchild;
}bit;
typedef struct node
{
bit data;
struct node *next;
}stack;
main()
{ bit *a;stack *s; init(s);
a=CreateBiTree(a);
/*printf(" inorder:");
inorder(a);
printf("\n proorder:");
preorder(a);
printf("\n postorder:");
postorder(a);*/
peroder1(a);
printf("\n");
inorder2(a) ;
printf(" inorder:"); inorder(a);
printf("\n postorder:");
/*postorder(a);
printf("\n");
postorder2(a) ;*/
getch();
}
CreateBiTree(bit *T)
{
char ch;
/*scanf("%c",&ch);*/;
ch=getchar();
if(ch=='0')
{T=0;}
else
{
T=(bit*)malloc(sizeof(bit));
T->data=ch;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}return T;
}
visit(char a)
{
printf("%c",a);
}
inorder(bit *t)
{
if(t)
{inorder(t->lchild);
printf("%c ",t->data);
inorder(t->rchild);
}
}
preorder(bit *t)
{
if(t)
{printf("%c ",t->data);
inorder(t->lchild);
inorder(t->rchild);
}
}
postorder(bit *t)
{
if(t)
{inorder(t->lchild);
inorder(t->rchild);
printf("%c ",t->data);
}
}
init(stack *st)
{
st=0;
}
push(stack *st,bit x){
stack *p;
p=(stack*)malloc(sizeof(stack));
p->data=x;p->next=0;
if(st==0)
{
st=p;
}
else
{p->next=st;
st=p;
}
}
stackempty(stack *st){
if(st==0)return 0;
else return 1;
}
pop(stack *st,bit x)
{
stack *p=st;
if(st==0)
return 0;
else{x=st->data;
st=st->next;
free(p);
}
}
/*feidigui(bit *a){
stack *s;bit *p=a;
init(s);
while(p||stackempty(s))
{if(p){push(s,p);p=p->lchild;}
else{pop(s,p);printf("%c",p->data);}
p=p->rchild;
}
}*/
peroder1(bit *b)
{
int top;
bit *st[20],*p;
if(b)
{
top=1;
st[top]=b;
while(top>0)
{ p=st[top];
top--;
printf("%c",p->data);
if(p->rchild!=0)
{top++;st[top]=p->rchild;}
if(p->lchild!=0)
{top++;st[top]=p->lchild;}
}
}
}
inorder2(bit *b)
{int top;bit *stack[20],*p;
if(b)
{top=1;stack[top]=b;p=b->lchild;
while(top>0||p)
{if(p){top++;stack[top]=p;p=p->lchild;}
else{p=stack[top];top--;printf("%c ",p->data);p=p->rchild;}
}
}
}
/*postorder2(bit *b)
{int top;bit *stack[20],*p;int f=0;
if(b)
{top=1;stack[top]=b;p=b->lchild;
while(top>0)
{if(p){top++;stack[top]=p;p=p->lchild;}
else{p=stack[top];top--;if(f){printf("%c",p->data);f=0;}p=p->rchild;f=1;}
}
}
}
*/