B 树全代码实现与超超详细思路解读.pdf
免费下载
B 树全代码实现与超超详细思路解读
—— 目录 ——
B 树全代码实现与思路解读
① 结构体与宏定义
② 查询操作
③ 打印操作
④ 插入操作
⑤ 删除操作
B 树全代码实现与思路解读
接下来就正式进入主题啦（嘛，可能前面废话有点多）
① 结构体与宏定义
需要提前定义以下常量，方便后续的使用
/* B 树阶数 */
#define M 4
/* B 树关键最大最小值以及中间值 */
#define MAX_KEY (M-1)
#define MIN_KEY ((M-1)/2)
#define MID_KEY ((M+1)/2)
注意点 1：
对于三个 KEY 值的解释
MAX_KEY 应该很好理解，M 接 B 树就是该树最多有 M 棵子树，那 M-1 个关键字自然就
会留出 M 个子树的位置啦
MIN_KEY 的话，按照定义应该是 M/2 向上取整为子树数量，但是整型除法默认是向下取整
呀，所以我们需要调整成 (M+1)/2，这样相当于被 2 除的向上取整了，然后对应的关键字
数量自然就是 (M+1)/2 - 1 即 (M-1)/2 啦
MID_KEY 作为分裂时需要移动到上层的记录的位置，注意这个值和前面的最大最小值有明
显的区别哦，前边的表示数量，而该值表示的是“位置”。右应为 KEY 的第一个位置不存
值，位置应该从 1 开始数，所以本来中间位置应该是 M/2 的，在第一个位置不使用之后，
自然就变成了 (M+1)/2 啦
然后准备以下 3 个结构体
/* 记录类型 */
typedef struct Rcd {
int key; // 记录的键
int data; // 记录的值
} Rcd, *Record;
/* B 树结构体 */
typedef struct BTNode {
int keyNum; // 结点中关键字个数，即结点的大小
KeyType key[M + 1]; // 关键字数组，0 号单元未用
Record rcd[M + 1]; // 记录指针数组，0 号单元未用
struct BTNode* parent; // 指向双亲结点
struct BTNode* child[M + 1];// 子树指针数组，0 号有使用
} BTNode, *BTree;
/* 结果类型 */
typedef struct Result {
int i; // 在结点中的关键字位序
int tag; // 是否找到了
BTree data; // 找到的数据
} Result;
然后是所有的接口
/* 通用辅助接口 */
Record getRecord(int key, int data); // 获得一个记录值
Result getResult(int i, int tag, BTree data); // 获得一个结果值
/* B 树接口 */
Status InitBTree(BTree& tree, Record data); // 初始化 B 树
BTree MakeBTree(const int treeData[][2], int num); // 构建 B 树
void TraverseBTree(BTree tree); // 打印 B 树
Result SearchBTree(BTree tree, KeyType key); // 对 B 树执行查找操作
Status InsertBTree(BTree& tree, Record data); // 对 B 树执行插入操作
Status DeleteBTree(BTree tree, KeyType key); // 对 B 树执行删除操作
Status UpdateBTree(BTree tree, KeyType key, Record data); // 将 B 树中关键字为 key 的结点
记录更换成新的记录
/* B 树辅助接口 */
int Search(BTree node, KeyType key); // 寻找 key 在 node 所在结点中的位置
void InsertBTNode(BTree& node, int i, Record rcd, BTree newNode); // 将新记 录 rcd 插入到
结点 node 的第 i 个位置，同时将新子节点 newNode 作为后继孩子
Status SplitBTNode(BTree& node, BTree& newNode); // 将 node 结点从中间分裂成两部分，
前半部分留在原位，后半部分进入 newNode 并指向原结点的双亲
Status newRoot(BTree& root, Record rcd, BTree child1, BTree child2); // 生成一个新根
int CountKeyNum(BTree tree); // 计算出整棵树上记录条数的总和
void Successor(BTree& node, int& i); // 找到前驱结点，并进行关键字的替换
Status InsertRecord(BTree& node, int i, Record rcd); // 将 rcd 插入到指定结点的第 i 个位
置
Status RemoveRecord(BTree& node, int i); // 将指定结点中第 i 个记录移除
void RestoreBTree(BTree& node, int pi); // 针对某个结点调整一颗 B 树
of 18
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论