数据结构B树及关键字的插入删除和按层次遍历Read.docx

数据结构B树及关键字的插入删除和按层次遍历Read.docx

《数据结构B树及关键字的插入删除和按层次遍历Read.docx》由会员分享，可在线阅读，更多相关《数据结构B树及关键字的插入删除和按层次遍历Read.docx（10页珍藏版）》请在冰点文库上搜索。

数据结构B树及关键字的插入删除和按层次遍历Read

数据结构实验：

B树及关键字的插入，删除和按层次遍历

054217黄威靖

[实验目的]

实现B树的相关算法：

关键字的插入，删除，查找和B树的按层次遍历。

具体到本实验中，是5阶B树的创建，从文件读入测试数据，1、3、5、7、9、……97、99（也可以是其他的测试数据）依次插入B树中，然后可以执行插入，删除，查找关键字，按层次遍历的操作。

[程序使用说明]

该程序可以从“测试文件.txt”读入数据，也可以手动输入数据（即向树中插入关键字），可以删除，查找关键字。

要检查运行结果，可以选择遍历B树。

根据屏幕提示，可以完成这些操作。

需要说明的是，显示的结果已经将B树分层，但没有显示树状关系

根据，B树的定义我们可以画出这个结果对应的树状关系图：

[算法简要说明]

用structNode来存放结点的信息，其中存放关键字的data[]长度是阶数，指向下层结点的指针数组branch[]长度是阶数+1。

这样，多出来的部分可以临时贮存关键字和指针，便于实现插入和删除的算法。

查找关键字的算法：

1．从根结点查起

2．查找要找的关键字是否在该结点中。

具体的做法是，拿要找的target和结点中的关键字从小到大依次比较，如果target不比该关键字大，则比较停止。

这时有两种可能：

target恰和该关键字一样大，表示查找成功；如果target比该关键字小，说明target可能存在在该关键字的“左孩子”中，继续3。

这两种情况都要返回当前关键字所在的结点的指针和在结点中的位置

3．得到2返回的关键字所在结点的指针current和在结点中的位置position，则target只能存在于current->b[position]对应的结点或该结点的“子孙”结点中。

重复2步骤查找这个结点

4．如果找到了叶子结点仍然没有找到这个关键字，则认定这棵树中没有这个关键字

插入关键字的算法：

1．1判断根结点是否为空，如果为空直接插入关键字

1．2根结点不为空，利用已经有的查找关键字的算法找要插入关键字是否在树中存在，如果存在则给出相应的信息；如果不存在，则找到应该插入的结点和位置

1．3因为普通结点（非根结点）关键字个数应该是ceil（order/2）-1~order-1,而Node中已经预留了order个的位置来存放关键字。

因此可以在1.2的基础上直接插入关键字。

如果此时该结点关键字个数超过上限，则调整该结点。

应用到调整的算法（2部分）

2．调整关键字溢出的结点

2．1当前结点中居中（定义一个median=ceil（order/2）-1）的关键字插入双亲结点中

2．2当前结点分裂变成left_brother和right_brother，其中right_brother是用new方法得到的一个新结点，将原来结点中右半部分关键字和指针分给right_brother

2．3调整双亲结点中的指针

2．4判断双亲结点中关键字个数是否溢出，如果溢出则继续调整。

否则调整结束

另：

如果涉及到根结点分裂，则双亲结点是用new办法得到的，算法和上述的基本相同，不再复述

删除关键字的算法：

1．1查找要删除关键字target的所在结点和位置

1．2

Case1如果是在叶子结点，直接删除关键字

Case2如果是在非叶子结点，则从“子孙结点”中找到比target大的最小关键字，把它提到当前结点中覆盖target。

并在叶子结点中删除这个提上来的关键字

1．3调整B树

2．调整B树的算法：

2．1遍历B树，如果有一个结点关键字个数小于下限，则调整这个结点

2．2检查该结点的右兄弟关键字个数是否等于下限，如果不等于，则向右兄弟借一个关键字

2．3否则，检查左兄弟关键字个数是否等于下限，如果不等于，则向左兄弟借一个关键字

2．4否则，合并结点

2．5回到2.1,直至B树不需要调整

3．向右兄弟借一个关键字的图例：

5．向左兄弟借一个关键字（类似于3.向右兄弟借，不复述）

6．合并结点

6．1调整左兄弟，将双亲结点中相应的关键字复制到左兄弟中，将右兄弟中关键字和指针都复制到左兄弟中

6．2调整右兄弟，只需将右兄弟的关键字个数置为0

6．3调整双亲结点，将下移的关键字删除，将指向右兄弟的指针置为NULL或用后面的指针覆盖它

按层次遍历B树：

1．将根结点指针入队列

2．当队列不为空时，做以下操作

3．让一个临时指针取队头的指针，然后队头指针出队列

4．从小到大输出临时指针中的关键字

5．当临时指针指向的不是叶子结点时，将临时指针指向的结点中的指向下一层结点的指针入队列

6．回到3，直到队列为空

[程序编写心得]

这是一个比较复杂的数据结构，但这种结构在数据仓储中应用的非常广泛，数据库实验课程中也是用的这种结构。

因此必须要将这个B树实现好。

起初，感觉这个结构复杂，无从下手。

后来用了分而治之的想法，把程序分为几个大块，一个个实现。

应用先创建好的B树，对每个功能测试。

只有当一个功能没问题时才进行下一个。

先写好了按层次遍历，觉得有了信心，写完了其余的。

在编写过程中体会到了文档的作用，先写文档，事先想好每一步干什么，有助于写代码时保持思路清晰，目标明确。

最后还遗留了一个问题。

将阶数作为BTree的私有成员，能够使该程序功能更强大。

但是structNode不接受阶数，认为无法访问私有成员。

这个问题现在还没解决好。

不得已，只能将阶数定义为宏。