【问题描述】
非递归方式实现二叉树的先序遍历、中序遍历、后序遍历和层序遍历。
提示:(1)利用先序建立二叉树序列;(2)求四种遍历结果。
【输入形式】
(1)先序建立二叉树序列
(2)非递归方式遍历
【输出形式】
四种遍历结果
【样例输入】
ABD#G###CE##FH###
【样例输出】
PreOrder:ABDGCEFH
InOrder:DGBAECHF
PostOrder:GDBEHFCA
CcOrder:ABCDEFGH
【评分标准】:四种遍历必须以非递归方式实现。
#include
#include
#define MAX 20typedef struct BitNode
{
char data;
struct BitNode *lchild,*rchild;
}BitNode,*BiTree;typedef struct SqQueue
{
int data[MAX];
int rear,front;
}SqQueue;void Creat (BiTree *t)
{
char s;
BiTree p;
scanf("%c",&s);
if(s=='#')
{
*t=0;
return;
}
p=(BiTree)malloc(sizeof(BitNode));
p->data=s;
*t=p;
Creat(&p->lchild);
Creat(&p->rchild);
}void Pre_n(BiTree p)
{
BiTree stack[MAX],q;
int top=0,i;
for(i=0;istack[i]=0;
q=p;
while(q)
{
printf("%c",q->data);
if(q->rchild)
stack[top++]=q->rchild;
if(q->lchild)
q=q->lchild;
else if(top>0)
q=stack[--top];
else
q=0;
}
}void In_n(BiTree t)
{
BiTree stack[MAX],p;
int top=0;
p=t;
if(p)
{
while(p||top>0)
{
while(p)
{
stack[top++]=p;
p=p->lchild;
}
if(top>0)
{
p=stack[--top];
printf("%c",p->data);
p=p->rchild;
}
}
}
}void Post_n(BiTree t)
{
BiTree stack[MAX],p;
int i,top=0,flag[MAX];
for(i=0;i{
stack[i]=0;
flag[i]=0;
}
if(!t)
return;
p=t;
while(p||top>0)
{
if(p)
{
stack[top]=p;
flag[top++]=1;
p=p->lchild;
}
else
{
p=stack[top-1];
if(flag[top-1]==1)
{
flag[top-1]=2;
p=p->rchild;
}
else
{
printf("%c",p->data);
top--;
p=0;
}
}
}
}void CcOrder (BiTree t)
{
BiTree p;
SqQueue qlist,*q;
q=&qlist;
q->rear=0;
q->front=0;
p=t;
if(p)
{
printf("%c",p->data);
q->data[q->rear]=p;
q->rear=(q->rear+1)%MAX;
while(q->front!=q->rear)
{
p=q->data[q->front];
q->front=(q->front+1)%MAX;
if(p->lchild)
{
printf("%c",p->lchild->data);
q->data[q->rear]=p->lchild;
q->rear=(q->rear+1)%MAX;
}
if(p->rchild)
{
printf("%c",p->rchild->data);
q->data[q->rear]=p->rchild;
q->rear=(q->rear+1)%MAX;
}
}
}
}
int main()
{
BiTree t=0;
Creat(&t);
if(!t)
printf("");
else
{
printf("PreOrder:");
Pre_n(t);
printf("\n");
printf("InOrder:");
In_n(t);
printf("\n");
printf("PostOrder:");
Post_n(t);
printf("\n");
printf("CcOrder:");
CcOrder(t);
printf("\n");
return 0;
}
}