《建立二叉树并对树进行操作数据结构课程设》由会员分享，可在线阅读，更多相关《建立二叉树并对树进行操作数据结构课程设（29页珍藏版）》请在金锄头文库上搜索。
1、 . . 课题名:建立二叉树,并对树进行操作系别:信息与计算科学系年级:2009级专业:数学与应用数学班级:一班学号:2009031116、2009031112、2009123123、2009031102、2009031110:唐永桥、文升、兵、丕权、庆勇指导老师:学勇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、总
2、结216、参考文献221数据结构（C语言版），严蔚敏，清华大学，2003221、 运行环境、开发工具运行环境：VC+ 6.0开发工具：电脑23 / 232、需求分析2.1设计目标二叉树是形象的说既树中每个节点最多只有两个分支，它是一个重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以与各种事物的分类和各种机构的职位图表。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历。以与能够从输入的数据中得知二叉树的叶子节点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。2.2 相关知识1、status CreateBiTree(Bi
3、Tree *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，才
4、能够得到本程序所有能够实现的功能。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); PreOrderTraver
5、se(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+; Numb
6、erLeaves(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) PostOrderT
7、raverse(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;
8、 else return 1 + Max(HighBitree(t-lchild), 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);
9、 printf(叶节点个数为：); printf(%d,m);printf(n二叉树的高度为:); printf(%d,HighBitree(T); printf(n先序遍历:n); PreOrderTraverse(T); /* printf(n中序遍历:n); InOrderTraverse(T); printf(n后序遍历:n); PostOrderTraverse(T);*/printf(n层次遍历n); ArrangementTraverse(T); printf(n);2程序设计2、概要设计2.1主要数据存储结构设计本设计中，对二叉树采用链式存储结构，其结构定义如下：typedef
10、 struct BiTNodeTelemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;每个结点中设置三个域，即值域data，左指针域*lchild和右指针域*child。2.2模块的划分与其功能 本程序分为：6大模块。二叉树的建立链式存储结构，前序遍历，求叶子结点的个数计算，中序遍历，后序遍历，深度求解。1）二叉树的建立：定义二叉树的链式存储结构，输入数据生成二叉树。二叉树的前序遍历：利用二叉链表作为存储结构的前序遍历；先访问根结点，再依次访问左右子树。2） 二叉树的求叶子结点的个数计算：先分别求的左右子树中各叶子结点的个数，
11、再计算出两者之和即为二叉树的叶子结点数。3） 二叉树的中序遍历：利用二叉链表作为存储结构的中序遍历；先访问左子树，再访问根结点，最后访问右子树。4） 二叉树的后序遍历：利用二叉链表作为存储结构的前序遍历；先访问左右子树，再访问根结点5） 求二叉树的深度：首先判断二叉树是否为空，若为空则此二叉树的深度为0.否则，就先求出左右子树的深度并进行比较，求较大的+1就为二叉树的深度。6） 主函数。核心算法的设计：二叉树是n各结点的有穷个集合，它或者是空集（n=0）,或者同时满足以下两个条件：（1）：有且仅有一个称为根的节点：（2）：其余节点分为两个互为相交的集合T1,T2，并且T1，T2都是二叉树，分别
12、称为根的左子树和右子树。3、详细设计开 始 建立二叉树中序遍历求叶子结点数先序遍历后序遍历求树的深度 主函数3.1存储结构的建立由scanf（）函数实现 一、首先输入的是根结点； 二、然后输入的是根结点的左孩子； 三、再者输入的是根结点的右孩子； 四、接着输入的是根结点左孩子的左孩子； 五、输入的是根结点的左孩子的； 六、输入的是根结点的右孩子的左孩子； 七、输入的是根结点的右孩子的左孩子； 八、最后输入的是根结点的右孩子的右孩子。依次输入数据。3.2重要函数主函数 void main()输入函数 printf()输出函数 scanf() 二叉树的先序建立函数 CreateBiTree（） 二叉树的先序遍历函数 PreOrderTraverse（） 二叉树的中序遍历函数 InOrderTraverse（） 二叉树的后序遍历函数 PostOrderTraverse（） 二叉树的层序遍历函数 ArrangementTraverse（） 求叶子节点函数 NumberLeaves（） 求深度函数 HighBitree（） 比较函数 Max（）3.3程序相关分析
