数据结构第二次作业实习报告 1110685
用户从键盘输入degree后，用degree初始化b树。
结点定义代码：
2、 关键字的插入：
在B树中插入关键字：
沿树下降查找新关键字的插入位置时，分裂沿途遇到的每个满结点。 B树中结点的分裂：
调用函数voidsplite_child(node* pnode, inti)。表示分裂pnode结点下标为i的子结点。 a) 满根的分裂：让原根成为一个新根的孩子，再调用splite_child（root，0）分裂原根。 b) 满非根结点的分裂：分裂过程如下：
1） 动态分配一个新结点new_node
2） 新结点的leaf与待分裂结点的leaf具有相同的真值
3） 迭代：将原结点下标为degree到最大下标的所有关键字插入到新结点的关键字队列中 4） 将原结点中下标为degree-1的关键字提升到父节点pnode下标为i的关键字处 5） 删除原结点中下标为degree-1到最大下标的关键字 6） 判断：待分裂结点是否为叶节点：
若不是：
迭代：将原结点中下标为degree到最大下标的孩子结点插入到新结点的孩子队列中； 删除原结点中对应孩子结点
7） 新结点成为原结点第i+1个孩子结点。
对B树用单程下行遍历树方式插入关键字：
a) 判断跟是否为满根。若是，分裂根，树高加1；
b) 递归沿树下降查找合适的插入位置，与满结点即分裂，直至查找到叶节点；
5
数据结构第二次作业实习报告 1110685
c) 将关键字插入到叶结点的合适位置。
3、 树的打印
a) 屏幕图形化输出：
1） 函数voidprint_B_tree(node* current,CDC* pDC,CPointpoint,intedge)
Current->当前待打印结点；
pDC->绘图封装类对象，用于在客户区绘制图形； point->当前结点关键字矩形的中间位置； edge->point与屏幕边界的距离
设置静态全局变量static one_sqare=25,表示一个矩形的边长 2） 点temp记录首个关键字矩形左上角的位置 3） 迭代，从temp依次打印关键字矩形和关键字 4） 迭代，打印current的孩子结点。
判断孩子指针是否为空： 若不为空:
计算孩子结点关键字矩形的中间位置subtemp，计算孩子结点与屏幕边界的距离startpoint 画线，连接指针矩形与孩子结点的中间位置
递归调用print_B_tree（current->children[i]，pDC，subtemp，startpoint）
b) 按层打印：
1） 定义队列，根节点入队列 2） 迭代（判断条件：队列非空）
首元素出队列； 打印该结点所有关键字； 该节点所有孩子结点入队列
3.3.1.5接口设计
1、用户输入树阶数degree和待输入关键字树key_num，定义B树类成员bTree，用degree初始化bTree
6
数据结构第二次作业实习报告 1110685
2、用户输入关键字，调用insert函数建
3.3.2子功能模块2——删除关键字
3.3.1.1 输入项
输入项一：删除命令（“d”or“md”） 名称：删除命令 标识：str 数据类型：string
有效范围：z字符串变量变量 输入方式：用户从键盘输入
输入项二：待删除关键字 名称：待删除关键字 标识：val 数据类型：int 有效范围：整型变量 输入方式：用户从键盘输入
3.3.1.2输出项
输出为B树树形，采用两种输出方式：屏幕图形化输出（采用MFC实现）；层遍历输出所有关键字
7
用户：输入命令（d->单关键字删除；md->多关键字删除：关键字间用“，”分隔，“#”记录结束） 调用Erase函数，将输入的关键字依次从B树中删除。若输入关键字树中不存在，弹出错误信息提示。 数据结构第二次作业实习报告 1110685
名称：B树结点 标识：btree->node 数据类型：int 有效范围：整型变量
输出方式1：同插入操作，不再赘述。
3.3.2.3数据结构的定义
3.3.1全局数据结构
函数node* insert(intkey)——用来实现B树关键字的插入
3.3.2 局部数据结构
函数node* grow_keys(node* pnode, inti)——用来实现关键字的扩展
函数node* merge_node(node* pnode, inti)——用来实现结点的合并
函数node*inter_erase(node* pnode, inti)——用来实现内结点关键字的删除
3.3.2.4算法及程序说明
采取的算法： 关键字的删除算法：
a)递归找到待删除关键字所在的结点；（判断条件：结点不是叶节点）
b)在下溯过程中，如果当前节点的孩子结点关键个数达下界，调用grow_keys函数，拓展该节点； c)找到关键字所在结点后，判断结点是否为叶节点，若不是，调用inter_erase函数，删除内结点中关键字
d)若关键字所在结点为叶节点，直接从叶节点中删除 结点扩展算法：
a） 函数node* merge_node(node* pnode, inti)表示扩展结点pnode位置为i的孩子结点 b） 判断：如果孩子结点的左兄弟有富余关键字，向左兄弟借：
将父节点pnode位置为i的关键字插入到待扩展结点的首元素位置 左兄弟最后一个元素出队列，插入到父节点中位置i
若孩子结点不是叶节点，将左兄弟最后一个孩子挂接到扩展结点的第一个孩子的位置
8
数据结构第二次作业实习报告 1110685
c） 若左兄弟没有富余元素，向右兄弟借，算法同上 d） 若左右兄弟都没有富余元素，合并两结点 结点合并算法:
a) node* merge_node(node* pnode, inti),表示合并pnode中下标为i的关键字的左右两结点 b) 新建结点，存储左孩子
c) 将pnode下标为i的关键字下降到新建结点中 d) 将右孩子所有关键字插入到新建结点后面
e) 如果左右孩子不是叶结点，将右孩子指针挂接到新建结点后 f) 将下标为i的关键字从父节点中删除 g) 将下标为i+1的孩子从父节点中删除
h) 判断：若父节点为根节点，且下降后父节点为空，删除根节点，并将合并后结点作为新的根节点 内结点关键字删除算法：
a) 函数node*inter_erase(node* pnode, inti)表示删除结点pnode中下标为i的关键字
b) 若左孩子关键字富余，递归下降到左孩子，左孩子的最后一个关键字代替父节点的待删除关键字 c) 若左孩子没有富余，下降到右孩子
d) 左右孩子关键字都不富余，合并i的左右结点，合并后待删除节点在合并结点的正中间 e) 删除合并结点中下标为degree-1的关键字
3.4运行结果
1、按层打印结果 A）功能一——新建B树
9