Question

求C语言非递归建立二叉树和非递归非递归先序遍历的完整代码

Answer 1

给你编了个，先序递归建树的。
#include
<stdio.h>
#include
<stdlib.h>
#define
STACK_INIT_SIZE
100
#define
STACKINCREMENT
10
typedef
struct
BiTNode
{
char
data;
struct
BiTNode
*lchild,*rchild;
}
BiTNode,*BiTree;//树类型
typedef
struct
SqStack
{
BiTNode
*base;
BiTNode
*top;
int
stacksize;
}
SqStack;//栈类型
void
InitStack(SqStack
*S)//创建
{
S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void
Push(SqStack
*S,BiTNode
e)//进栈
{
if(S->top-S->base>=S->stacksize)
{
S->base=(BiTNode*)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
S->top++;
}
BiTNode
Pop(SqStack
*S)//出栈
{
S->top
--;
return
*S->top;
}
int
StackEmpty(SqStack
*S)//判断栈是否非空
{
if(S->top
==
S->base
)
return
1;
else
return
0;
}
BiTree
CreateBiTree()//创建树（先序递归）
{
char
p;BiTree
T;
scanf("%c",&p);
if(p=='
')
T=NULL;
else
{
T=(BiTNode
*)malloc(sizeof(BiTNode));
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return
(T);
}
void
PreOrder(BiTree
T)//先序
{
SqStack
S;
BiTree
p=T;
InitStack(&S);
if(p)
Push(&S,*p);
while(!StackEmpty(&S))
{
p=(BiTNode
*)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
if(p->rchild)
Push(&S,*p->rchild);
if(p->lchild)
Push(&S,*p->lchild);
}
}
void
InOrder(BiTree
T)//中序
{
SqStack
S;
BiTree
p=T;
InitStack(&S);
while(p||!StackEmpty(&S))
{
if(p)
{
Push(&S,*p);
p=p->lchild;
}
else
{
p=(BiTNode
*)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
p=p->rchild;
}
}
}
void
main()
{
BiTree
Ta;
printf("请创建树");
Ta=CreateBiTree();
printf("先序遍历:");
printf("\n");
PreOrder(Ta);
printf("\n");
printf("中序遍历:");
printf("\n");
InOrder(Ta);
}