二叉树的遍历问题
#include<stdio.h>#include<stdlib.h>
#include<malloc.h>
#include<Status.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 100
typedef struct BiTNode
{
int data;
struct BiTNode * lchild, * rchild;
}BiTNode,* BiTree;
typedef struct
{
BiTree * base;
BiTree * top;
int stacksize;
} SqStack;
void main()
{
void InitStack(SqStack *s);
int StackEmpty(SqStack *s);
void PreOrderTraverse(SqStack *s,BiTree p);
int Push(SqStack *s, BiTree e);
BiTree GetTop(SqStack *s);
BiTree Pop(SqStack *s);
BiTree CreateBiTree(BiTree T);
SqStack s;
BiTree T=0,p;
InitStack(&s);
printf("请输入二叉树的根节点：");
T=CreateBiTree(T);
printf("先根序遍历二叉树结果为：");
PreOrderTraverse(&s,T);
printf("\n");
}
void PreOrderTraverse(SqStack *s,BiTree p)
{
Push(s,p);
while(!StackEmpty(s))
{
printf("%d",Pop(s)->data);
if(p->rchild!=NULL)
Push(s,p->rchild);
if(p->lchild!=NULL)
Push(s,p->lchild);
getchar();
}
}
void InitStack(SqStack *s)
{
s->base = (BiTree *)malloc(sizeof(BiTree) * STACK_INIT_SIZE);
s->top = s->base;
s->stacksize = STACK_INIT_SIZE;
}
int StackEmpty(SqStack *s)
{
int len;
len=s->top-s->base;
if(len==0)
return OK;
else
return ERROR;
}
BiTree CreateBiTree(BiTree T)
{
int m;
scanf("%d",&m);
if(m==0)
T=NULL;
else
{
if(!( T= (BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data = m;
printf("请输入%d的左孩子:",T->data);
T->lchild=CreateBiTree(T->lchild);
printf("请输入%d的右孩子:",T->data);
T->rchild=CreateBiTree(T->rchild);
}
return T;
}
BiTree GetTop(SqStack *s)
{
if (!(s->top - s->base))
return 0;
return *(s->top-1 );
}
int Push(SqStack *s, BiTree e)
{
if (s->top - s->base >= s->stacksize)
{
s->base = (BiTree *)realloc(s->base,sizeof(BiTree) * (s->stacksize + STACKINCREMENT));
if (!s->base)
return ERROR;
s->top=s->base;
s->stacksize+=STACKINCREMENT;
}
*(s->top) = e;
(s->top)++;
return OK;
}
BiTree Pop(SqStack *s)
{
return *(--s->top);
}
这是一个二叉树的前序非递归遍历的问题，但是那个循环怎么也出不去啊，就是这个： while(!StackEmpty(s))
结果是这样的
请输入二叉树的根节点：1
请输入1的左孩子:2
请输入2的左孩子:0
请输入2的右孩子:0
请输入1的右孩子:3
请输入3的左孩子:0
请输入3的右孩子:0
先根序遍历二叉树结果为：12
2
2
2
2
2
2
2
2
2
2
2
2
2
