数据结构-二叉树的遍历与其结点的计算-课程设计-实验报告

数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构_二叉树的遍历与其结点的计算_课程设计_实验报告设计题目：二叉树的遍历及其相关结点的计算课题名称二叉树的遍历及相关结点数的计算院系年级专业学号姓名成绩课题设计目的与设计意义1、课题设计目的：（1）：掌握数据结构分析设计思想及其存储表示方法和技术。（2）：掌握基于特定数据结构的基本运实现方法和设计。（3）：掌握工程化程序设计方法、技术及过程。2、课题设计意义：（1）：学会怎样团队协作去解决问题，增强自身的自信心、主动性思考能力以及自主学习的能力。（2）：对课程设计这门课有更深的了解，通过这次的课题设计来提升对编程的兴趣，更加努力的学习这门课。（3）：通过课程设计的实践，在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统的严格训练。指导教师：年月日目录第一章课程与设计的目的与意义..................................................................................................11.1课题设计目的......................................................................................................................11.2课题设计意义......................................................................................................................1第二章需求分析...............................................................................................................................12.1课程设计题目、任务及要求.............................................................................................12.2课程设计思想......................................................................................................................1第三章二叉树的基本概述...............................................................................................................13.1二叉树相关概念.................................................................................................................13.2二叉树的性质......................................................................................................................23.3二叉树的存储.....................................................................................................................2第四章：系统的概要设计.................................................................................................................34.1二叉树的生成过程.............................................................................................................34.2主要功能模块设计.............................................................................................................3第五章：系统详细设计.....................................................................................................................45.1主函数菜单模块.................................................................................................................45.2二叉树的生成.....................................................................................................................65.3层次遍历模块.....................................................................................................................85.4求其相关结点的总数.......................................................................................................10第六章测试结果.............................................................................................................................12第七章总结.....................................................................................................................................14第八章参考文献.............................................................................................................................151第一章课程与设计的目的与意义1.1课题设计目的：（1）：掌握数据结构分析设计思想及其存储表示方法和技术。（2）：掌握基于特定数据结构的基本运实现方法和设计。（3）：掌握工程化程序设计方法、技术及过程。1.2课题设计意义：（1）：学会怎样团队协作去解决问题，增强自身的自信心、主动性思考能力以及自主学习的能力。（2）：对课程设计这门课有更深的了解，通过这次的课题设计来提升对编程的兴趣，更加努力的学习这门课。（3）：通过课程设计的实践，在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统的严格训练。第二章需求分析2.1课程设计题目、任务及要求（1）对二叉树作各种遍历,输出结果；（2）求得二叉树结点的总数和叶子结点的数目；（3）要求二叉树的操作结果完整的输出2.2课程设计思想（1）建立二叉树采用一个一个输入的方式。（2）对二叉树分别实现多种遍历的方式。（3）编写算法实现求结点和其叶子的数目。第三章二叉树的基本概述3.1二叉树相关概念定义：二叉树是n（=0）个借点的有限集，它或者是空集（n=0），或者由一个根结点及两颗互不相交的、分别称作这个根的左子树和右子树的二叉树组成。2这也是一个递归定义。二叉树可以是空集，因此，根可以有空的左子树或右子树，或者左、右子树皆为空。因此，二叉树有五种基本形态，如下图1所示：图3.1二叉树的五种基本形态满二叉树：一颗深度为k且有2^k-1个结点的二叉树称为满二叉树。完全二叉树：若一颗二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。3.2二叉树的性质二叉树具有以下重要性质：性质1二叉树第i层上的结点数目最多为2^（i-1）（i=1）。性质2深度为k的二叉树至多有2^k-1（k=1）个结点。性质3在任意一颗二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。性质4具有n个结点的完全二叉树的深度为└log2n┘+1（或┌log2（n+1）┐）。3.3二叉树的存储1.顺序存储结构该方法是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。因此，必须把结点安排成一个适当的线性序列，使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。2.链式存储结构从上面的介绍可知：顺序方式存储一般二叉树将浪费存储空间，并且若在树中需要经常插入和删除结点时，由于大量地移动结点，顺序存储变的不可取。因此，存储树的最自然的方法是链接的方法。二叉树的每个结点最多有两个孩子，用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子，相应的类型说明为：typedefchardatatype;typedefstructnode3{datatypedata;structnode*lchild,*rchild;}bitree;第四章：系统的概要设计4.1二叉树的生成过程二叉树的生成，采用逐个建立的方式，如图：否否图4.1二叉树的生成过程4.2主要功能模块设计程序主要设计了五个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：退出，三种遍历，计算结点总数和叶子结点数目。初始化数组插入头结点空树添加左子树添加右子树插入插入插入否否是是4主函数流程如下：三种遍历Switch()Switch()退出图4.2主函数流程图第五章：系统详细设计5.1主函数菜单模块该模块功能主要是给用户提供清晰的可操作界面，易于人机操作，并能很好的调用其他各模块，使程序更加优化，丝路更加清晰，结构更加明了，提高了程序的实用性。其算法如下：voidmain(){inti,j,m,n;bitreet,*s;while(j)否否否否否是创建二叉排序树Switch()Switch(0)退出求叶子结点default求结点的总数是是是5{printf(\t\t输入1创建二叉树\n\t\t输入2前序遍历\n\t\t输入3中序遍历\n\t\t输入4后序遍历\n\t\t输入5求结点总数\n\t\t输入6求叶子结点数\n);scanf(%d,&i);switch(i){case1:s=creatbitree(&t);break;case2:printf(前序遍历结果为:);preorder(s);printf(\n);break;case3:printf(中序遍历结果为:);inorder(s);printf(\n);break;case4:printf(后序遍历结果为:);postorder(s);printf(\n);break;case5:m=sum(s)