数据结构课程设计
题 目： 二叉树的应用与操作
院 （系）： 成教院
专 业： 计算机科学与技术
学生姓名： 谭俊忠
班 级： 20070199311
学 号： 2007019931107
分 数：
2008 年 12 月 26 日
一. 前言
计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，
它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数
据处理、过程控制以及对文件的存储和检索及数据库技术等计算机应用领域中，
都是对数据进行加工处理的过程。因此，要设计出一个结构好效率高的程序，
必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特
性和关系设计出相应的算法和程序。数据结构是计算机科学与技术专业的专业
基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到
各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握
几种计算机程序设计语言是难以应付众多复杂的课题的。要想有效地使用计算
机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好
“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系
统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。
二. 程序内容
二叉树是一种十分重要的树型结构。它的特点是，树中的每个结点最多只有两
棵子树，即树中任何结点的度数不得大于２。二叉树的子树有左右之分，而且，
子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树
还是右子树。为了更好的体现二叉树的结构与特点，以下编写了简单的程序来
实现，功能如下：
1. 创建一个二叉树
2. 先序，中序，后序遍历二叉树
3. 在二叉树中的指定位置插入一个新节点
4. 删除二叉树中的指定节点
5. 统计二叉树的层数
6. 统计结点总数
7. 统计叶子结点数目
三. 设计用的计算机环境
1. PC 兼容机一台
2. Microsoft Visual C++ 6.0
四. 程序操作
1. 二叉树创建
首先输入数字创建一个二叉树，以输入数字 0 为空树，当输入：
1230400056700800900 时，程序会在创建二叉树时调用函数：void
creat( bitree &p )做递归创建，其中创建二叉树的关键代码如下：
p = ( bitree )malloc( sizeof ( bintree ) );
p->data = i;
creat( p->lchild );
creat( p->rchild );
当输入完成上面的数后会得到一个二叉树，此二叉树存储结构图如下：
先序遍历：1 2 3 4 5 6 7 8 9
中序遍历：3 4 2 1 7 6 8 5 9
后序遍历：4 3 2 7 8 6 9 5 1
2. 插入节点
首先需输入插入位置，程序会先调用：void SearchRoot( bitree T, int root , bitree
&p )函数进行查找到指定节点，代码片断如下：
if( T )
{
if( T->data == root ) //判断二叉树中的值是否与指定值相同
{
p=T;
return;
}
SearchRoot( T->lchild , root , p );
SearchRoot( T->rchild , root , p );
}
如遇该节点有左孩子和右孩子时，程序会提示" 插入失败！该节点和左节点和
1
2 5
3 6 9
4 7 8
右节点 "，当该节点没有左孩子或右孩子时，程序却会调用：void insert ( bitree
T , int root )插入一个空的节点，代码片断如下：
s=( bitree )malloc( sizeof ( bitree ));
s->data = i;
s->lchild = s->rchild = NULL;
if( p->lchild == NULL )
p->lchild = s; //插入左树
else
if ( p->rchild == NULL )
p->rchild = s; //插入右树
3. 删除节点
首先输入要删除的节点，程序会先调用 SearchRoot( T , root , p );找到该节点，如
果该节点有左孩子和右孩子，程序会显示"删除失败！该节点有左节点和右节
点"，当该节点的左孩子或右孩子为 NULL 的时候，程序却会调用
SearchRoot1( T , p );找到该节点的父节点，然后对节点进行删除操作，代码片断
如下：
s = p->lchild;
p->lchild = s->lchild;
free ( s );
4. 其它操作
程序自动的进行统计二叉树的层数，统计结点总数，统计叶子结点数目的操作。
五. 总结
在本次设计中，由于对二叉树的不熟悉，导致了多数程序运行的结果不正确，
最后还是通过翻阅资料与多次的调试才得以解决，最后，经过这次的设计，本
人总结出了自己在学习数据结构中的不足，并且为其他类似语言打下了良好的
基础。
六. 源代码
#include <stdio.h>
