2019数据结构实习报告二叉树

《2019数据结构实习报告二叉树》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实习报告二叉树　　数据结构课程设计　　实习报告　　题　　目：学　　号：姓　　名：年　　级：学　　院：专　　业：完成日期：授课教师：　　B树的建立，插入与　　删除1110685李建男大二　　信息技术科学学院计算机科学与技术专业　　辛运帷　　数据结构第二次作业实习报告1110685　　1.题目　　2.B树的表示及基本操作的实现。3.1．掌握B树的存贮结构。　　4.2．实现B树中关键字值的插入及删除操作。5.3．练习屏幕图形化的显示。　　2.要求　　a)参考书中的示例代码，以整数表示每个记录的关键字。为简单起见，每个记录可以只包

2、含一个　　关键字。　　b)从空树开始，依次输入各关键字，建立相应的B树。c)并实现B树中关键字的插入及删除。　　d)同时将树型显示在屏幕上。全部关键字插入完毕时显示树型，之后每完成一次插入或删除操作　　后也显示当前的树型。　　e)假设B树中不存在重复的关键字。f)　　程序运行时，当要输入数据时必须在屏幕上给出输入的格式要求。当有输出显示时，也需要将输出的内容做必要的解释。　　3.程序实现　　程序运行及编译环境　　VisualStudio20XX　　程序描述　　该程序支持用户进行以下三种操作：　　1、新建B树：从键盘输入新建B树的阶

3、数和关键字个数，新建B树。　　2、插入关键字：既支持单个关键字的插入，也支持多个关键字的插入。3、删除关键字：既支持单个关键字的删除，也支持多个关键字的删除。　　特别说明：程序编写时参考了《算法导论》中的内容，对B树的规定与老师课上所讲略有出入，采用了如下规则：对m阶B树：　　关键字个数：Least：m-1；Most：2*m-1　　1　　数据结构第二次作业实习报告1110685　　孩子个数：Least：m；Most：2*m　　实现功能　　介绍该程序应具有的功能，可采用IPO图的形式。说明：如果该程序只有单一功能时可以直接描述其输入

4、项、输出项等等各个部分，否则按照各个子功能模块分别介绍。　　子功能模块1——新建B树&插入关键字　　说明：因新建和插入用到的算法相同，故合并为一个模块　　根据用户输入的B树阶数，关键字个数及关键字，新建B树。　　用户：输入B树阶数degree，待输入关键字个数key_num。2　　数据结构第二次作业实习报告1110685　　　　输入项　　输入项一：B树阶数degree和带插入关键字个数key_num名称：B树阶数标识：degree数据类型：int有效范围：整型变量输入方式：用户从键盘输入　　名称：待插入关键字个数标识：key_nu

5、m数据类型：int有效范围：整型变量　　3　　根据degree，初始化B树：MyBTreeBTree；用户：依次输入关键字调用Insert函数，将输入的关键字依次插入到B树中，完成B树的创建。数据结构第二次作业实习报告1110685　　输入方式：用户从键盘输入输入项二：名称：关键字标识：key数据类型：int有效范围：整型变量　　存储方式：动态数组newint[key_num]输入方式：用户从键盘输入　　输出项　　输出为B树树形，采用两种输出方式：屏幕图形化输出；层遍历输出所有关键字、具体输出方式同子模块1，不再赘述。　　数据结构

6、的定义　　全局数据结构　　函数bool*erase(intkey)——用来实现B树关键字的插入　　局部数据结构　　函数voidsplite_child(node*pnode,inti)——用来实现当结点满时结点的分裂　　算法及程序说明　　采取的算法：1、树的创建：　　B树类classb_trees。包含两个私有数据变量：结点类node*root，和表示树阶数的变量intdegree。node类包含三个成员变量——关键字队列dequekeys、指向孩子的指针队列dequechildren、判断是否是叶节点的布尔变量boolleaf。

7、B树的构造函数如下：　　explicitb_trees(intdeg=10):root(newnode),degree(deg){};　　4　　数据结构第二次作业实习报告1110685　　用户从键盘输入degree后，用degree初始化b树。　　结点定义代码：　　2、关键字的插入：　　在B树中插入关键字：　　沿树下降查找新关键字的插入位置时，分裂沿途遇到的每个满结点。B树中结点的分裂：　　调用函数voidsplite_child(node*pnode,inti)。表示分裂pnode结点下标为i的子结点。a)满根的分裂：让原根成为

8、一个新根的孩子，再调用splite_child分裂原根。b)满非根结点的分裂：分裂过程如下：　　1）动态分配一个新结点new_node　　2）新结点的leaf与待分裂结点的leaf具有相同的真值　　3）迭代：将原结点下标为degree到最大下标的所