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

1、作业名称：创建二叉树和操作树:信息计算机科学部年级：2009级专业：数学和应用数学班： 1班学号：名字3360唐英教，杨文胜，李兵，陈天权，范庆龙导师：理学用2011-5-10目录内容31，引言51.1设计目标51.2相关知识52、整体设计102.1主要数据存储结构设计102.2模块分区和功能103，详细设计113.1存储结构的构建通过scanf()函数实现113.2重要功能123.3与方案相关的分析123.4结构和全局变量定义123.5程序清单134、测试数据和结果分析195、汇总216、参考文献221 数据结构 (C语言版)，严郁敏，清华大学出版社，2003.221、生产环境、开发工具操作

2、环境：VC 6.0开发工具：计算机2、需求分析2.1设计目标二进制树是重要的数据类型，树中的每个节点最多只有两个分支的图像。家谱，公司所有职员的职位，也可以用来制作各种事物的分类及各种机关的职位图表。二叉树构建了链式存储结构，实现了前序遍历、中间序遍历和后序遍历。您可以从输入的数据中知道二叉树的叶节点数，二叉树的深度。其中，二叉树中的每个节点必须包含值字段、左指针字段和右指针字段。2.2相关知识1、status CreateBiTree(BiTree *T)/首先创建二叉树TelemType chScanf(%c ，ch)；if(ch=end flag)* T=NULL；Else If(！(*

3、 t=(bitnode *)malloc(size of(bitnode)Printf(nOut of space . )；getch()；退出(0)；(* t)-数据=ch/创建根节点create bitree(* T)-lchild)；/左侧子树create bitree(* T)-rchild)；/右侧子树Return OKTelemType用于输入N个字符中的任意字符，输入N个字符后必须输入N=1只有为零，才能得到这个程序能实现的所有功能。T=Null是将二进制树留空。If(！(* t=(bitnode *)malloc(size of(bitnode)/节点动态请求方法不仅易于实施，

4、还可以节省大量存储空间。(* t)-数据=ch/创建根节点create bitree(* T)-lchild)；/左侧子树create bitree(* T)-rchild)；/右侧子树2、顺序遍历：首先访问根节点，然后访问左侧子树，最后访问右侧子树。具体实施包括：状态PreOrderTraverse(BiTree T)If(T)printf(“% c”，T-data)；preorder traverse(T-lchild)；preorder traverse(T-rchild)；Return OK3、查找叶节点数：使用M变量指示叶节点总数。树空的时候讨论叶节点数没有意义。树非空时1、左、左、

5、左、左、左、右、左、左、右、左、右、左、右、右、左、左、右、右、右、左其次，如果左侧和右侧子树存在，则分别访问左侧和右侧子树的叶节点数，然后将两者相加，得到二进制树叶节点数。具体实施包括：/查找二进制树的叶节点数状态NumberLeaves(BiTree T)/首先遍历叶节点数/m=0；If(T)if(t-lchild=nullt-rchild=null)m；number leaves(T-lchild)；number leaves(T-rchild)；Return OK4、中间顺序遍历：首先访问左侧子树，然后访问根节点，最后访问右侧子树。具体实施包括：Status InOrderTraver

6、se(BiTree T)If(T)inorder traverse(T-lchild)；printf(“% c”，T-data)；inorder traverse(T-rchild)；Return OK5，后续遍历：首先访问左侧子树，然后访问右侧子树，最后访问根节点。具体实施包括：状态postorder转换器(bitree t)If(T)postor der traverse(T-lchild)；postor der traverse(T-rchild)；printf(“% c”，T-data)；Return OK6、找出二叉树的深度：首先，定义两个成型变数m、n，并将初始值设定为0。如果树是

7、空的，则深度为零。否则，分别访问左侧和右侧子树的深度，然后进行比较，大1的结果就是二进制树的深度。具体实施包括：Status Max(int m，int n) /一个比较函数If (m n)return m；Elsereturn n；/获取二进制树的高度Status HighBitree(BiTree t)If (t=NULL)return 0；ElseReturn 1 max (highbitree (t-lchild)，high bitree(t-rchild)；5、主要函数包含：BiTree T、reateBiTree(T)、NumberLeaves(T)、printf(“% d”、Hi

8、ghBitree(T)、preoot/主函数Void main()BiTree T；Printf(“创建二进制树： n”)；create bitree(T)；number leaves(T)；Printf(“叶节点数：”)；printf(“% d”，m)；Printf(n二进制树的高度为： )；printf(“% d”，high bitree(T)；printf(“ n首先3360 n”)；PreOrderTraverse(T):/* printf(“ n : n”)；inorder traverse(T)；printf(“ n : n”)；PostOrderTraverse(T) : */P

9、rintf(n遍历层次 n )；arrangement traverse(T)；printf(“ n”)；2编程2、大纲设计2.1主要数据存储结构设计在此设计中，二叉树的链存储结构定义如下：Typedef struct BiTNodeTelemType dataStruct BiTNode *lchild，* rchildBiTNode，* BiTree在每个节点上设置三个字段：值域数据、左指针字段*lchild和右指针字段*child。2.2模块分区和功能这个程序分为6个大模块。构建二叉树链存储结构，遍历以前的顺序，计算叶节点数，遍历中间顺序，遍历后顺序，解释深度。1)建立模具树：定义模具树

10、的链储存结构，然后输入输入资料以产生模具树。遍历二进制树的前一顺序：使用二级链表作为存储结构的前一顺序遍历。首先访问根节点，然后依次访问左侧和右侧的子树。2)计算二进制树的叶节点数：首先分别求出的左、右子树的每个叶节点数，其和是二进制树的叶节点数。3)二进制树的中间顺序遍历：使用二级链表作为存储结构的中间顺序遍历。首先访问左侧的子树、根节点，最后访问右侧的子树。4)二进制树的后循环：使用二级链表作为存储结构的前循环。首先访问左侧和右侧子树，然后访问根节点5)找到二叉树的深度。首先确定二进制树是否为空，如果为空，则此二进制树的深度为零。否则，首先获取左、右子树的深度，进行比较，然后获取大1，这将

11、成为二进制树的深度。6)主函数。核心算法的设计：二叉树具有一个名为N节点、空集合(n=0)或同时满足这两个条件的N节点(1):根的节点。(2):剩馀节点被分为两个徐璐相交的集合T1、T2和T1。3，详细设计开始创建二叉树中间顺序遍历求树叶节点数先巡回后巡回求树的深度主函数3.1存储结构的构建由scanf()函数完成首先，第一个输入是根节点。其次，输入根节点的左孩子。第三，还输入根节点的右孩子。第四，然后输入根节点左边孩子的左边孩子。第五，输入根节点的左孩子；第六，输入根节点右侧孩子的左侧孩子；第七，输入根节点右边孩子的左边孩子。八，最后输入的是根节点右边孩子的右边孩子。依次输入数据。3.2重要

12、功能主函数void main()输入函数printf()输出函数scanf()二进制树的顺序创建函数CreateBiTree()二进制树的第一个遍历函数PreOrderTraverse()二叉树的中间顺序遍历函数InOrderTraverse()二叉树的后续遍历函数PostOrderTraverse()二进制树的序列遍历函数ArrangementTraverse()查找叶节点函数NumberLeaves()寻找深度函数。HighBitree()比较函数Max()3.3与计划相关的分析#include /*定义标准I/o函数*/#include /*定义文字和字符串函数*/#include /*

13、用于数据输入和数据输出的控制台函数*/#include /*定义一般数学函数*/(此程式包含字串的许多函数。要使用该函数，必须先定义它。）3.4定义结构和全局变量#define OK 1#define ERROR -1#define ENDFLAG #/*表示节点没有左边的孩子或右边的孩子。*/Typedef char TelemType/*宏定义char类型*/Typedef int status/*宏定义int类型*/Typedef struct BiTNodeTelemType dataStruct BiTNode *lchild，* rchildBiTNode，* BiTree/*二叉树存储结构*/int m=0；/*表示叶数的全局变量*/3.5程序清单/头文件# include“stdio . h”# include“conio . h”# include“stdlib . h”/预先定义的巨集常数#define OK 1#define ERROR -1#define ENDFLAG #Typedef char TelemTypeTypedef in