二叉树基本操作+数据结构+实验报告

《二叉树基本操作+数据结构+实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8页共8页郑州轻工业学院数据结构实验报告题目学生姓名学号专业班级完成时间2016年月日8第8页共8页目录一、系统功能介绍…………………………………2二、需求分析………………………………………2三、概要设计………………………………………2四、详细设计………………………………………5五、调试分析………………………………………8六、使用说明………………………………………8七、测试结果………………………………………9八、心得体会………………………………………10九、附录（程序代码）……………………………118第8页共8页一、系统功能介绍该系统主要功能是实现二叉树的定义和基本操作，包括定义二叉树的结构

2、类型以及各个操作的具体函数的定义和主函数的定义。各操作主要包括：初始化二叉树、按先序次序建立二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九个对树的操作。二、需求分析本系统通过函数调用实现二叉树初始化，建立二叉树，检查树空与否，用前序、中序、后序遍历二叉树，求树的深度，求树的结点数目，清空二叉树等功能。1）输出的形式和输出值的范围：在选择操作中，都以整型（数字）选择操作，插入和输出的数值都是char类型的字符；2）输出的形式：在每次操作后，都会提示操作是否成功或者操作的结果；3）程序达到的功能：完成初始化、检查是否为空、请空、遍历、求树的深度

3、、求树的结点数目等功能；4)测试数据设计：A,按先序次序建立二叉树。依次输入a,b,c,d,e,f,g.建立二叉树。B,分别按先序，中序和后序遍历输出二叉树中的结点元素。C,求树的高度和结点数。三、概要分析为了实现上述功能，定义二叉树的抽象数据类型。ADTBinTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若D=￠，称BinTree为空二叉树若D≠￠,则R={H},H是如下的二元关系；（1）在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；（2）若D-{root}≠￠，则存在D-{root}={D1,Dr},且D1∩Dr=￠；（3）若D≠￠，则中存在唯一的元素

4、x1,∈H,，且存在D1上的关系H1H;若则中存在唯一的元素且存在上的饿关系（4）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。基本操作P：8第8页共8页BinTreeBinTreeInit(){操作结果：构造空的二叉树初始条件：给出二叉树的定义}BinTreeBinTreeCreat(BinTree&BT){操作结果：用先序序列创建一个二叉树初始条件：构造了空的二叉树}intBinTreeEmpty(){操作结果：返回0或1，即树的空与否初始条件：二叉树存在}voidPreBinTraverse(BinTreeBT){操作结果：按先序序

5、列遍历输出二叉树初始条件：二叉树存在}voidInBinTraverse(BinTreeBT){操作结果：按中序序列遍历输出二叉树初始条件：二叉树存在}voidPastBinTraverse(BinTreeBT){操作结果：按后序序列遍历输出二叉树初始条件：二叉树存在}intBinTreeDepth(BinTreeBT){操作结果：返回二叉树的深度初始条件：二叉树存在}intBinTreeCount(BinTreeBT){操作结果：返回二叉树的结点个数初始条件：二叉树存在}voidBinTreeClear(BinTree&BT){操作结果：清空释放二叉树的结点初始条件：二叉树存在8第8页共8页

6、}}四、详细设计流程图实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。typedefintDataType;树节点类型定义typedefstructBitNode{intdata;structBitNode*lchild,*rchild;}BitNode,*BitTree;1.初始化二叉树，即把树根指针置空1.二叉树初始化(算法)2.按先序次序建立一个二叉树(算法)8第8页共8页3.检查二叉树是否为空(算法)4.前序遍历(算法)5.中序遍历(算法)6.后序遍历(算法)7.求二叉树的深度(算法)8.求二叉树中所有结点数(算法)8第8页共8页9.

7、清除二叉树，使之变为空树五．调试分析六．结果测试操作界面为。选择1后：。选择2：，分别输入1，2，3，0，0，4，5，0，0，0，0，建立一棵树。选择3：选择4：8第8页共8页选择5：选择6：选择7：选择8：选择9：选择0：七．心得体会八．可执行的完整源代码8