1=僧瞳二叉妁
补输出二夏树餡深虞’节点数及叶子数
3=层次遍历二叉矿
4,打甲二叉树
0：
邁由
•><些甌耳1<1|~些竺耳斗列耳if-if■其■«-*!
<
屮pw*mh**h*wgelect
节点数及叶子数
1=创建二民树
3=层次遍历二叉櫛
4=打印二叉树
«：
邁由
A.创建新的二叉树•并输出深度，节点数，叶子数；运行结果如下:
B.层次遍历新二叉树，并打印二叉树，运行结果如下:
打印二叉树
JKKJaJtKJCXJitMM：
SeleCtJOCKJOfXJCXJCMKJC1:
创建二叉树
辰次遍历序列：
ABCDEFGHI
JtJCJCJtB[:
>tMKS号leCt誉-MHMTHCM：
M：
ItJtMM：
JC
I：
仓腱二X林
鉄输出二叉哋琨聡节点数及叶子数3=层我殖历二夏轿4：
打用二支树
0=退由
（七）.不足之处
在windows控制台上打印二叉树时，是按中序遍历打印的，打印的树形结构（右子数在上，左子数在下，根在最左边）要通过旋转90度才能看到我们平日看到的树形二叉树（根在上，左右子数在下）。
（八）.设计体会
经过了两个周的学习，通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法。
把死板的课本知识变得生动有趣，激发了学习的积极性。
把学过的c语言知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。
加深了对c语言和数据结构的巩固，在学习中不仅仅是局限于课本知识，更要懂得查阅资料，不论基础有多扎实，都要查阅相关书
籍，查阅资料，找到更好的解决方法。
四.参考文献
《数据结构课程设计案例精编》李建学等主编清华大学出版社2007《c程序设计》谭浩强主编清华大学出版社2005
《数据结构c语言版》严蔚敏主编清华大学出版社2009
五．附录（源程序）
#include"stdio.h"#include"malloc.h"#include"stdlib.h"
#include"stddef.h"
#defineMax20/*结点的最大个数*/
typedefintdatatype;
typedefstructnode{datatypedata;
intnum;
structnode*lchild,*rchild;
}BinTNode;/*自定义二叉树的结点类型*/
BinTNode*q[Max];
typedefBinTNode*BinTree;/*定义二叉树的指针*/intNodeNum,leaf;/*NodeNum为结点数，leaf为叶子数*/inta=0;
BinTNode*creatree（）
{charch;
intfront,rear;
BinTNode*s,*root;
root=NULL;
front=1;
rear=0;
printf（"虚节点用@表示，以#结束\n"）;
printf（"请输入一棵二叉树序列!
\n"）;ch=getchar（）;
while（ch!
='#'）
{s=NULL;
if（ch!
='@'）
{s=malloc（sizeof（BinTNode））;
s->data=ch;s->lchild=s->rchild=NULL;
}
rear++;
q[rear]=s;
if（rear==1）
root=s;
else
{if（s&&q[front]）
if（rear%2==0）
q[front]->lchild=s;
else
q[front]->rchild=s;
if（rear%2==1）
front++;
}
ch=getchar（）;
}
returnroot;
}
/*=====采用后序遍历求二叉树的深度、叶子结点数及数的递归算法========*/
intTreeDepth（BinTreeT）
{
inthl,hr,max;
if（T）{
hl=TreeDepth（T->lchild）;/*求左深度*/
hr=TreeDepth（T->rchild）;/*求右深度*/
max=hl>hr?
hl:
hr;/*取左右深度的最大值*/NodeNum=NodeNum+1;/*求结点数*/
*/
return（max+1）;
}elsereturn（0）;
}
/*====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========*/voidLevelorder（BinTreeT）
{intfront=0,rear=1;
BinTNode*cq[Max],*p;/*定义结点的指针数组cq*/cq[1]=T;/*根入队*/
while（front!
=rear）
{front=（front+1）%NodeNum;
p=cq[front];/*出队*/printf（"%c",p->data）;/*出队，输出结点的值*/
if（p->lchild!
=NULL）{
rear=（rear+1）%NodeNum;
cq[rear]=p->lchild;/*左子树入队（指针替换）*/
}
if（p->rchild!
=NULL）{rear=（rear+1）%NodeNum;
cq[rear]=p->rchild;/*右子树入队*/
}}}
voidprint_btree（BinTreeT,intlevel）
{inti=0;
if（T==NULL）return;print_btree（T->rchild,level+1）;
//缩进level*2个字符for（i=0;i//假设你的二叉树的结点存放的是一个字符printf（"%c\n",T->data）;
print_btree（T->lchild,level+1）;
}//打印二叉树
voidprint（BinTreeT）
{
print_btree（T,0）;
}
/*==========主函数=================*/
main（）
{
BinTreeroot;
inti,j=0,depth,nLayer;
root=NULL;
printf（"\n"）;
root=creatree（）;/*创建二叉树，返回根结点*/
do{/*从菜单中选择遍历方式，输入序号。
*/
printf（"\t1:
创建二叉树\n"）;
printf（"\t2:
输出二叉树的深度，节点数及叶子数\n"）;
printf（"\t3:
层次遍历二叉树\n"）;/*按层次遍历之前，先选择
printf（"\t**********select
************
\n"）;
4，求出该树的结点数*/
printf（"\t4:
打印二叉树\n"）;
printf（"\t0:
退出\n"）;
scanf（"%d",&i）;/*输入菜单序号（0-5）*/
getchar（）;
switch（i）{
case1:
printf（"创建二叉树:
"）;
printf（"\n"）;root=creatree（）;
break;
case2:
NodeNum=0;leaf=0;depth=TreeDepth（root）;/*求树的深
度及叶子数*/
printf（"二叉树深度=%d节点数=%d",depth,NodeNum）;
printf（"叶子数=%d",leaf）;
break;
case3:
printf（"层次遍历序列:
"）;
Levelorder（root）;/*
按层次遍历*/
break;
case4:
printf（"打印二叉树:
\n"）;print（root）;
break;
case0:
break;
default:
puts（"again"）;
}
printf（"\n"）;
}
while（i!
=0）;
}
升级会员 