二叉树的建立及其应用
按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。
设计摘要
二叉树是树形结构的一个重要的类型，二叉树是n（n>=0）个结点的有限集，它或者是空集（n=0），或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
二叉树的存储结构和算法比较简单，特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。
现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。
目 录
二叉树的建立及其应用 .............................................................................................................................................................. 1 一 数据结构课程设计题目及概要设计 .............................................................................................................................. 2
&1.1 数据结构课程设计题目 ................................................................................................. 2
&1.2 题目概要设计 ................................................................................................................. 2
二 需求分析 ............................................................................................................................................................................ 3 &2.1 程序设计的目的 ............................................................................................................. 3
&2.2 程序设计的基本要求 ..................................................................................................... 3
1
三 程序设计的内容及详细设计 .......................................................................................................................................... 3
&3.1算法设计的思想 .............................................................................................................. 3
&3.2 程序设计流程图 ............................................................................................................. 5 &3.3.程序数据类型 .................................................................................................................. 6 &3.4程序模块分析 .................................................................................................................. 7 &3.5主要的算法源代码 ........................................................................................................ 14 &3.6程序设计的结果 ............................................................................................................ 24
四 程序设计的优缺点及遇到问题 ...................................................................................................................................... 27 &4.1程序设计的优缺点 ........................................................................................................ 27
&4.2程序设计遇到的问题 .................................................................................................... 27
五 程序设计的心得体会 .......................................................................................................................................................... 27 &5.1心得体会 ........................................................................................................................ 27 第六章 参考文献 ...................................................................................................................................................................... 28
一 数据结构课程设计题目及概要设计
&1.1 数据结构课程设计题目
题目：二叉树的建立及其应用
[问题描述]
按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。
&1.2 题目概要设计
通过这个程序主要掌握三种遍历方案，包括前序遍历、中序遍历、后序遍历，以及怎么求二叉树的高度、总结点数、叶子总个数。并会将理论与现实结合在一起。
2
二 需求分析
&2.1 程序设计的目的
掌握二叉树的概念和性质、任意二叉树存储结构和任意二叉树的基本操作，并会求二叉树的高度、二叉树总结点个数、二叉树叶子结点，以及熟练掌握三种遍历，包括前序遍历、中序遍历、后序遍历。
&2.2 程序设计的基本要求
在设计程序时，一定要简单明了，程序设计的思想要完善，算法要清晰，能给其他读者一目了然的感觉。实现二叉树的建立；前序、中序和后序遍历；高度、总结点数、叶子结点数。
三 程序设计的内容及详细设计
&3.1算法设计的思想
二叉树的建立基本思想是：依次输入的结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直至输入“00”时为止。可设置一个指针类型的数组队列，保存已输入结点的地址。由于是按层次自左至右输入结点的，所以先输入的结点的孩子必定比后输入结点的孩子先进入队列，因此可利用对头指针指向当前必须与其孩子结点必定建立链接的双亲结点，利用队尾指针指向当前的结点，即是当前必须与其双亲建立链接的双亲结点。若队尾指针为偶数，则表示当前输入的结点编号是偶数，队尾指针所指向的结
3
点应作为左孩子与其双亲链接；否则队尾指针所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点或孩子结点为虚结点，则无须链接。若双亲结点与其两个孩子链接完毕，则做出队操作，使队头指针指向下一个等待链接的双亲结点。
遍历二叉树是二叉树的一种重要的运算，所谓遍历是指沿某条搜索路径周游二叉树，对数中每个结点访问一次且仅访问一次。二叉树的定义是递归的，所以主要由三种遍历方案：
1. 前序遍历二叉树
若二叉树非空，则依次进行如下操作：
（1） 访问根结点；
（2） 前序遍历左子数；
（3） 前序遍历右子树。
2. 中序遍历二叉树
若二叉树非空，则依次进行如下操作：
（1） 中序遍历左子树；
（2） 访问根结点；
4
（3） 中序遍历右子树。
3. 后序遍历二叉树
若二叉树非空，则依次进行如下操作：
（1） 后序遍历左子树；
（2） 后序遍历右子树；
（3） 访问根结点。
一个结点的子树个数称为该结点的度。一颗树的度是该树中结点的最大度数。度为零的结点称为叶子，二叉树结点的层数是从根开始算起的，树中结点的最大层数称为树的高度或深度。
&3.2 程序设计流程图
5
&3.3.程序数据类型
typedef int datatype; /* datatype可以为任何类型，这里假设为int*/
# define max 60 /*二叉树可能的最大长度，这里假设为60*/
typedef struct node
{ /*结构体*/
char data; /*数据域*/
struct node *lchild,*rchild; /*左右孩子指针*/
6
}bitree;
&3.4程序模块分析
（1） 二叉树的建立
bitree *creat() /*二叉树的建立*/
{
int i,j;
bitree *root,*s,*Q[max];
char ch;
printf(\"请输入要建立的树的下标和数值：\");
scanf(\"%d%c\
while(i!=0&&ch!='0')
{
s=(bitree *)malloc(sizeof(bitree));
7
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
Q[i]=s;
if(i==1) root=s;
else
{
j=i/2;
if(i%2==0) Q[j]->lchild=s;
else Q[j]->rchild=s;
}
scanf(\"%d%c\
}
8
return root;
}
（2）二叉树的三种遍历
void preorder(bitree *t) {
if(t)
{
printf(\"%c\
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(bitree *t)
/*前序遍历*/
/*中序遍历*/
9
{
if(t)
{
inorder(t->lchild);
printf(\"%c\
inorder(t->rchild);
}
}
void postorder(bitree *t) {
if(t)
{
postorder(t->lchild);
/*后序遍历*/
10
postorder(t->rchild);
printf(\"%c\
}
}
（3）求二叉树的高度
int high(bitree *t) {
int l,r;
if(t==NULL) return 0;
else
{
l=high(t->lchild);
r=high(t->rchild);
/*求二叉树的高度*/
11
return (l>r?l:r)+1;
}
}
（4）求二叉树的总结点数
int nodes(bitree *a) {
int num1,num2;
if(a==NULL) return 0;
else
{
num1=nodes(a->lchild);
num2=nodes(a->rchild);
return num1+num2+1;
/*求总结点数*/
12
}
}
（5）求叶子结点数
int leafs(bitree *b) /*求叶子结点数*/
{
int n,m;
if(b==NULL) return 0;
else
if(b->lchild==NULL&&b->rchild==NULL) return 1;
else
{
n=leafs(b->lchild);
m=leafs(b->rchild);
13
return n+m;
}
（6）主函数 main(),功能是给出测试数据值，建立测试数据值的顺序表，调用creat函数、preorder函数、inorder函数、postorder函数high、函数nodes函数、leafs函数实现问题要求。
&3.5主要的算法源代码
# include\"stdio.h\" /*头文件*/
# include typedef int datatype; # define max 60 typedef struct node { /*结构体*/ char data; struct node *lchild,*rchild; 14 }bitree; bitree *creat() /*二叉树的建立*/ { int i,j; bitree *root,*s,*Q[max]; char ch; printf(\" 请输入要建立的树的下标和数值：\"); scanf(\"%d%c\ while(i!=0&&ch!='0') { s=(bitree *)malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; 15 s->rchild=NULL; Q[i]=s; if(i==1) root=s; else { j=i/2; if(i%2==0) Q[j]->lchild=s; else Q[j]->rchild=s; } scanf(\"%d%c\ } return root; } 16 void preorder(bitree *t) /*前序遍历*/ { if(t) { printf(\"%c\ preorder(t->lchild); preorder(t->rchild); } } void inorder(bitree *t) { if(t) { /*中序遍历*/ 17 inorder(t->lchild); printf(\"%c\ inorder(t->rchild); } } void postorder(bitree *t) { if(t) { postorder(t->lchild); postorder(t->rchild); printf(\"%c\ } /*后序遍历*/ 18 } int high(bitree *t) /*求二叉树的高度*/ { int l,r; if(t==NULL) return 0; else { l=high(t->lchild); r=high(t->rchild); return (l>r?l:r)+1; } } int nodes(bitree *a) /*求总结点数*/ 19 { int num1,num2; if(a==NULL) return 0; else { num1=nodes(a->lchild); num2=nodes(a->rchild); return num1+num2+1; } } int leafs(bitree *b) { int n,m; /*求叶子结点数*/ 20 if(b==NULL) return 0; else if(b->lchild==NULL&&b->rchild==NULL) return 1; else { n=leafs(b->lchild); m=leafs(b->rchild); return n+m; } } void main() { int a,j,h,g; 21 bitree *b; b=creat(); while(1) { printf(\" 选择 1 前序遍历\\n 选择 2 中序遍历\\n选择 3 后序遍历\\n 选择 4 求高度\\n 选择 5 求总结点数\\n 选择 6 求叶子结点个数\\n 选择 0 退出: \"); scanf(\"%d\ switch(a) { case 1:printf(\" 该二叉树的前序遍历是：\"); preorder(b); printf(\"\\n\"); break; 22 case 2:printf(\" 该二叉树的中序遍历是：\"); inorder(b); printf(\"\\n\"); break; case 3:printf(\" 该二叉树的后序遍历是：\"); postorder(b); printf(\"\\n\"); break; case 4:printf(\" 该二叉树的高度j=%d\\n\ j=high(b); break; case 5:h=nodes(b); printf(\" 该二叉树的总结点数h=%d\\n\ 23 break; case 6:g=leafs(b); printf(\" 该二叉树的叶子结点个数g=%d\\n\ break; case 0: return ; } } } &3.6程序设计的结果 1. 建立二叉树如下图： 2. 测试提示：输入数据1A 2B 3C 4D 5E 7J 10F 11G 14K 15L 22H 23I 00 2.前序遍历功能运行结果如下图： 24 3.中序遍历功能运行结果如下图： 4.后序遍历功能运行结果如下图： 5.求高度功能运行结果如下图： 25 6.求总结点数功能运行结果如下图： 7.求叶子结点个数功能运行结果如下图： 8.程序运行结束如下图： 26 四 程序设计的优缺点及遇到问题 &4.1程序设计的优缺点 这个程序设计的算法清晰，思想明了，能清楚的实现二叉树的建立、三种遍历、高度、总结点数以及叶子结点数的运算。但是这个程序在设计过程时有些麻烦，而且三种遍历的算法自己不是太清楚，不能很清楚的描述三种遍历。 &4.2程序设计遇到的问题 在设计时主要三种遍历不是很清楚，所以还是很模糊，刚开始不能很准确的把三种遍历的算法写出来，所以在这个问题上还要继续思考。在写菜单时不是很了解，后来在同学的帮助下把程序的菜单写出来了，自己还要加强这方面的练习。 五 程序设计的心得体会 &5.1心得体会 通过这次做数据结构的课程设计，我发现真正掌握一个知识点并不只是要从书上看， 27 还要查一些相关资料，并且理论与现实结合在一起。这次做的是关于二叉树的课程设计，刚开始以为并不是很难，但真正做的时候才发现这一节的知识点很多，也有一些比较混淆的难点，比如二叉树的遍历就有三种情况，包括前序遍历、中序遍历、后序遍历。 另外通过这次设计，我感到团队协作真的非常重要，当一个程序出现错误时，一个人找半天也找不出来，但通过讨论，上网查资料，大家的观点结合在一块，通过分析就找了出来。当程序调试通过时，感到非常高兴，有一种小成就感，这就是合作的乐趣吧。通过这次合作，感到时间过得很充实，对这门课的兴趣也大大提高了。 当然这次在做课程设计的时候也遇到一些问题，不过还好得到了同学们的无私帮助，问题得以解决，从而成功的完成了本次的课程设计。 第六章 参考文献 【1】 耿国华.数据结构—C语言描述。2005年7月第1版.高等教育出版社。 【2】 何钦铭 颜晖 ，C语言程序设计。2008年1月第1版。高等教育出版社。 28 因篇幅问题不能全部显示，请点此查看更多更全内容