建立二叉树,并对树进行操作数据结构课程设

课题名:建立二叉树,并对树进行操作

系别:信息与计算科学系

年级:2009级

专业:数学与应用数学

班级:一班

学号:2009031116、2009031112、2009123123、2009031102、2009031110

姓名:唐永桥、杨文升、李兵、陈丕权、范庆勇

指导老师:李学勇

2011-5-10

目录

摘 要..........................................................................................错误！未定义书签。 1、引言........................................................................................错误！未定义书签。

1.1设计目标........................................................................................................... 4 1.2 相关知识.......................................................................................................... 4 2、总体设计.................................................................................................................. 9

2.1主要数据存储结构设计................................................................................... 9 2.2模块的划分及其功能....................................................................................... 9 3、详细设计................................................................................................................ 10

3.1存储结构的建立由scanf（）函数实现 ....................................................... 10 3.2重要函数......................................................................................................... 11 3.3程序相关分析................................................................................................. 11 3.4结构体和全局变量定义................................................................................. 11 3.5程序清单......................................................................................................... 12 4、测试数据及结果分析............................................................................................ 18 5、总结........................................................................................错误！未定义书签。 6、参考文献................................................................................................................ 21 ［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2003．................... 21

1、 运行环境、开发工具

运行环境：VC++ 6.0

开发工具：电脑

2、需求分析

2.1设计目标

二叉树是形象的说既树中每个节点最多只有两个分支，它是一个重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表。

二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历。以及能够从输入的数据中得知二叉树的叶子节点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。

2.2 相关知识

1、 status CreateBiTree(BiTree *T) {// 先序创建二叉树 TelemType ch; scanf("%c",&ch);

if(ch==ENDFLAG) *T=NULL; else {

if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) {

printf("\nOut of space."); getch(); exit(0); }

(*T)->data=ch; //生成根结点

CreateBiTree(&((*T)->lchild));//左子树 CreateBiTree(&((*T)->rchild));//右子树 }

return OK; }

TelemType的作用是输入n各任意的字符，而且在输入n个字符后，必须输入N=1 个0，才能够得到本程序所有能够实现的功能。T=Null是将二叉树置为空。

if(!(*T=(BiTNode *)malloc(sizeof(BiTNode))))//采用动态申请结点的方式，不仅实现起来方便，而且还节省大量的存储空间。

(*T)->data=ch; //生成根结点

CreateBiTree(&((*T)->lchild));//左子树 CreateBiTree(&((*T)->rchild));//右子树

2、前序遍历：先访问根结点，再访问左子树，最后访问右子树。 具体实现如下：

status PreOrderTraverse(BiTree T) { if(T) {

printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); }

return OK; }

3、求叶子结点的个数：用m变量表示叶子结点的总个数。 当树为空是此时讨论叶子结点个数无意义；

当树非空时分为：一、左右子树都不存在时，m自加1，m的值就为1，即叶子结点的个数为1；

二、左右子树存在，就用分别访问出左右子树中叶子结点的个数，两者相加就为二叉树叶子结点的个数。 具体实现如下：

//求二叉树的叶结点个数 status NumberLeaves(BiTree T) {//先序遍历得到叶结点的数目 //m=0; if(T) {

if(T->lchild==NULL&&T->rchild==NULL) m++; NumberLeaves(T->lchild); NumberLeaves(T->rchild); }

return OK; }

4、中序遍历：先访问左子树，再访问根结点，最后访问右子树。 具体实现如下：

status InOrderTraverse(BiTree T) { if(T) {

InOrderTraverse(T->lchild); printf("%c",T->data);

InOrderTraverse(T->rchild); }

return OK; }

5、后序遍历：先访问左子树，再访问右子树，最后访问根结点。 具体实现如下：

status PostOrderTraverse(BiTree T) { if(T) {

PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c",T->data); }

return OK; ｝

6、求二叉树的深度：

先定义2个整形变量m，n，并将其初值设为0。如果树为空，则深度0； 否则，先分别访问出左右子树的深度，再进行比较，将较大的+1的结果就是所求二叉树的深度。 具体实现如下：

status Max(int m, int n) //一个比较函数 {

if (m > n)

return m; else

return n; }

//获取二叉树的高度

status HighBitree(BiTree t) {

if (t == NULL)

return 0; else

return HighBitree(t->rchild)); }

5、 主函数

包括：BiTree T，reateBiTree(&T)，NumberLeaves(T)，printf("%d",HighBitree(T))，PreOrderTraverse(T)，InOrderTraverse(T)，PostOrderTraverse(T)，ArrangementTraverse(T) //主函数 void main() {

BiTree T;

printf("请创建二叉树：\n"); CreateBiTree(&T); NumberLeaves(T); printf("叶节点个数为："); printf("%d",m);

printf("\n二叉树的高度为:"); printf("%d",HighBitree(T)); printf("\n先序遍历:\n"); …… 此处隐藏：3896字，全部文档内容请下载后查看。喜欢就下载吧 ……