层序遍历二叉树

#include
#include
#define m 100
typedef char etype;
typedef struct bitnode
{
etype data;
struct bitnode *lch,*rch;
}bitnode,*bitree;
bitree que[m];
int front=0,rear=0;
bitnode *creat_bt1();
bitnode *creat_bt2();
void preorder(bitnode *p);
void inorder(bitnode *p);
void postorder(bitnode *p);
void enqueue(bitree);
bitree delqueue();
void levorder(bitree);
int treedepth(bitree);
void prtbtree(bitree,int);
void exchange(bitree);
int leafcount(bitree);
void paintleaf(bitree);
bitnode *t;
int count=0;
void main()
{
char ch;int k;
do{
printf("\n\n\n");
printf("\n==========主菜单==============");
printf("\n 1.建立二叉树方法 1");
printf("\n 2.建立二叉树方法 2");
printf("\n 3.先序递归遍历二叉树");
printf("\n 4.中序递归遍历二叉树");
printf("\n 5.后序递归遍历二叉树");
printf("\n 6.层次遍历二叉树");
printf("\n 7.计算二叉树的高度");
printf("\n 8.计算二叉树中叶结点个数");
printf("\n 9.交换二叉树的左右子树");
printf("\n 10.打印二叉树");
printf("\n 0.结束程序运行");
printf("\n===============================");
printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");
scanf("%d",&k);
switch(k)
{case 1:t=creat_bt1();break;
case 2:printf("\n请输入二叉树各节点的值：");fflush(stdin);
t=creat_bt2();break;
case 3:if(t)
{printf("先序遍历二叉树：");
preorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 4:if(t)
{printf("中序遍历二叉树：");
inorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 5:if(t)
{printf("后序遍历二叉树：");
postorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 6:if(t)
{printf("层次遍历二叉树：");
levorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 7:if(t)
{printf("二叉树的高度为：%d",treedepth(t));
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 8:if(t)
{printf("二叉树的叶子结点数为：%d\n",leafcount(t));
printf("二叉树的叶结点数为：");paintleaf(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 9:if(t)
{printf("二叉树的左右子树：\n");
exchange(t);
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 10:if(t)
{printf("逆时针旋转90度输出的二叉树：\n");
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 0:exit(0);
}
}while(k>=1&&k<=10);
printf("\n再见! 按回车键，返回…\n");
ch=getchar();
}
bitnode *creat_bt1()
{
bitnode *t,*p,*v[20];int i,j;etype e;
printf("\n请输入二叉树各结点的编号和对应的值(如：1，a):");
scanf("%d,%c",&i,&e);
while(i!=0&&e!='#')
{
p=(bitnode *)malloc(sizeof(bitnode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else
{j=i/2;
if(i%2==0) v[j]->lch=p;
else
v[j]->rch=p;
}
printf("\n 请继续输入二叉树各结点的编号和对应的值：");
scanf("%d,%c",&i,&e);
}
return(t);
}
bitnode *creat_bt2()
{
bitnode *t;etype e;
scanf("%c",&e);
if(e=='#')
t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
t->data=e;
t->lch=creat_bt2();
t->rch=creat_bt2();
}
return(t);
}
void preorder(bitnode *p){
if(p)
{
printf("%3c",p->data);
preorder(p->lch);
preorder(p->rch);
}
}
void inorder(bitnode *p)
{
if(p){

inorder(p->lch);
printf("%3c",p->data);
inorder(p->rch);
}
}
void postorder(bitnode *p)
{
if(p)
{
postorder(p->lch);
postorder(p->rch);
printf("%3c",p->data);
}
}
void enqueue(bitree T)
{
if(front!=(rear+1)%m)
{rear=(rear+1)%m;
que[rear]=T;}
}
bitree delqueue()
{
if(front==rear)return NULL;
front=(front+1)%m;
return(que[front]);
}
void levorder(bitree T)
{
bitree p;
if(T)
{
enqueue(T);
while(front!=rear)
{
p=delqueue();
printf("%3c",p->data);
if(p->lch!=NULL)enqueue(p->lch);
if(p->rch!=NULL)enqueue(p->rch);
}
}
}
int treedepth(bitree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->lch);
hr=treedepth(bt->rch);
max=(hl>hr)? hl:hr;
return(max+1);
}
else
return(0);
}
void prtbtree(bitree bt,int level)
{
int j;
if(bt){
prtbtree(bt->rch,level+1);
for(j=0;j<=6*level+1;j++)printf(" ");
printf("%c\n",bt->data);
prtbtree(bt->lch,level+1);
}
}
void exchange(bitree bt)
{
bitree p;
if(bt)
{p=bt->lch;bt->lch=bt->rch;bt->rch=p;
exchange(bt->lch);exchange(bt->rch);
}
}
int leafcount(bitree bt)
{
if(bt!=NULL)
{
leafcount(bt->lch);
leafcount(bt->rch);
if((bt->lch==NULL)&&(bt->rch==NULL))
count++;
}
return(count);
}
void paintleaf(bitree bt)
{
if(bt!=NULL)
{
if(bt->lch==NULL&&bt->rch==NULL)
printf("%3c",bt->data);
paintleaf(bt->lch);
paintleaf(bt->rch);
}
}