# B 树的抽象数据类型实现
## 环境及工具
环境:C
工具:AnyivewCL
## B 定义
一棵 m 阶 B 树(Balance Tree of order m), 或为空树,或满足下列的特性的 m 叉树:(本次实验采用链式存储结构)
(1)树中每个结点最多含有 m 棵子树。
(2)若根结点是非终端结点,则至少有 2 棵子树
(3)除根结点之外的所有非终端结点至少有「m/2 棵子树。
(4)每个非终端结点中包含信息:(n,A,K1,A1,K2,A2,…,Kn,An)。其中:
①K(1≤i≤n)为关键字,且关键字按升序推入指针。
②A(0≤≤n)指向子树的根结点,A(i-1)指向子树中所有结点的关键字均小于 Ki,且大于 K(i-1)。
③ 关键字的个数 n 必须满足「m/2-1≤n≤m-1。
(5)所有叶子结点都出现在同一层,叶子结点不包含任何信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空。实际上,B 树的结点还应包含 n 个指向每个关键字相应记录的指针。这与应用相关,从略。
存储结构定义和宏定义
```c++
# define M 4 //B树的阶,本次实验设置为4
# define MAX M – 1 //每个节点存储的最多关键字的数目
# define MIN M/2 //每个节点存储的最少关键字的数目
# define N 14 //选取14个关键字的树作为例子
# define ERROR 0
# define SUCCESS 1
# define TRUE 1
# define UNSUCCESS 0
# define OVERFLOW -1
# define FALSE -1
typedef int Status;
typedef int KeyType;//关键字类型为整形
typedef struct BTNode {
int keynum; //当前节点的关键字数目
KeyType key[M + 1]; //关键字数组,key[0]未用
struct BTNode parent; //双亲结点指针
struct BTNode ptr[M + 1]; //孩子节点指针数组
//Record recptr[M + 1]; //记录指针向量,0号单元未用
} BTNode, BTree; //B树的节点及指针类型
//B树查找的结果类型
typedef struct {
int tag; //1:查找成功,0:查找失败
BTree pt; //指向找到的结果类型
int index; //1 <= index <= M 在节点中的关键字位序
} Result;
```
本次实验的基本功能的接口定义:
```java
void InitBTree(BTree &t)
操作结果:构造空的B树t
int MakeBTree(BTree &t, KeyType keyType[], int n)
操作结果:创建一棵B树
Status DestroyBTree(BTree &t)
初始条件:树t存在
操作结果:销毁B树t
int Depth1(BTree t):
初始条件:树t存在
操作结果:返回树t的深度(不包括叶子结点层)
int Depth2(BTree t):
初始条件:树t存在
操作结果:返回t的深度(包括叶子结点层)
int SearchIndex(BTree p, int k)
初始条件:树t存在
操作结果:在p节点上查找关键字的位置
void SearchBTree(BTree t, KeyType k, Result &r)
初始条件:树t存在
操作结果:在M阶B树t上查找关键字k, 用r返回(pt, index, tag)
若是查找成功,则tag = 1, 指针pt指向的节点中第index个关键字等于k,否则 tag = 0, 若要插入关键字k, 则应该位于pt节点中第 index-1 个和第 index 个之间
Status NewRoot(BTree &t, BTree p, int x, BTree ap)
初始条件:t是即将生成的新的根节点,x是新的根节点的关键字的值,
p和ap是分裂开的两个节点,其双亲结点都要设为是t。
操作结果:生成新的根节点
。
Status Split(BTree &q, int s, BTree &ap)
初始条件:q节点关键字数目等于m时,进行分裂,s是分裂的位置。
操作结果:将q结点分裂成两个结点, 前一半保留在原来的节点,后一 半移入ap
void Insert(BTree &q, int index, int x, BTree ap)
操作结果:是下面的插入函数的辅助函数,关键字x 和新节点指针 ap 分别插入q->key[index] 和 q->ptr[index]
void InsertBTree(BTree &t, int k, BTree q, int index)
初始条件:树t存在,从SearchBTree中找到了插入节点q和插入位置index
操作结果:在B树t中 q结点的key[index-1]和 key[index] 中插入关键k
void Traverse(BTree t)
初始条件:树t存在
操作结果:分解成根节点和若干个孩子节点,递归遍历B树
void KeysNum(BTree t, int &sum)
初始条件:树t存在
操作结果:求所有关键字个数sum
BTNode FindPre(BTNode ptr)
初始条件:ptr节点存在
操作结果:找到ptr的前驱节点,为删除操作做的准备
BTNode FindNext(BTNode ptr)
初始条件:ptr节点存在
操作结果:找到ptr的后继节点,为删除操作做的准备
void FindPreKey(BTree t, int key, Result &result)
初始条件:key所造的t树中的节点不是最底层的非终端节点
操作结果:找到key的前驱关键字
void FindNextKey(BTree t, int key, Result &result)
初始条件:key所造的t树中的节点不是最底层的非终端节点
操作结果:找到key的后继关键字
void RightRotate(BTree &leftbro, BTree &ptr, BTree &parent, int pos)
操作结果:右旋转(双亲结点借一个关键字给ptr,然后左兄弟给回一个最小的关键字给双亲结点)
void LeftRotate(BTree &rightbro, BTree &ptr, BTree &parent, int pos)
操作结果:左旋转(双亲结点借一个关键字给ptr,然后右兄弟给回一个最小的关键字给双亲结点)
void LeftMerge(BTree &leftbro, BTree &ptr, BTree &parent, int pos)
初始条件:删除关键字后少于关键字少于MIN,兄弟节点也没有多余的节点
操作结果:左合并
void RightMerge(BTree &ptr, BTree &rightbro, BTree &parent, int pos)
初始条件:删除关键字后少于关键字少于MIN,兄弟节点也没有多余的节点
操作结果:右合并
BTree Adjus(BTree &ptr)
初始条件:出现小于MIN的情况的调整函数
操作结果:调整为符合B树的情况
void DelMostBottomKey(BTree &ptr, int pos)
初始条件:删除的关键字位于最下层的非终端结点
操作结果:删除ptr节点中的pos位置的关键字,为下面的Remove函数所用
void ReMove(BTree &root, KeyType e)
初始条件:根为root的B树存在,e为要删除的关键字
操作结果:从B树中删除e关键字
```
```java
4.算法设计
//初始化一棵B树
void InitBTree(BTree &t) {
t = NULL;
printf("初始化成功\n");
}
//在p节点上查找关键字的位置
int SearchIndex(BTree p, int k) {
int index = 1;
while (index <= p->keynum && k > p->key[index]) {
index++;
}
return index;
}
/
在M阶B树t上查找关键字k, 用r返回(pt, index, tag)
若是查找成功,则tag = 1, 指针pt指向的节点中第i个关键字等于k
否则 tag = 0, 若要插入关键字k, 则应该位于pt节点中第 index-1 个和第 index 个之间
/
void SearchBTree(BTree t, KeyType k, Result &r) {
int index = 0, found = 0;
BTree p = t, q = NULL; //初始, p指向根节点; p将用于指向待查节点, q指向其双亲结点
while (p != NULL && 0 == found) {
index = SearchIndex(p, k);
if (index <= p->keynum && p->key[index] == k)
found = 1; //找到待查关键字
else {
q = p;
p = p->ptr[index - 1];//指针下移
}
}
if (1 == found) { //查找成功,返回k的位置 p 和 index
r.pt = p;
r.index = index;
r.tag = 1;
} else { //查找不成功,返回k的插入位置q及index
r.pt = q;
r.index = index;
r.tag = 0;
}
}
//生成新的根节点
Status NewRoot(BTree &t, BTree p, int x, BTree ap) {
t = (BTNode ) malloc(sizeof(BTNode));
if (t == NULL)
return ERROR;
t->keynum = 1;
t->ptr[0] = p;
t->ptr[1] = ap;
t->key[1] = x;
if (p != NULL)
p->parent = t;
if (ap != NULL)
ap->parent = t;
t->parent = NULL; //新根的双亲是空指针
return SUCCESS;
}
//销毁B树
Status DestroyBTree(BTree &t) {
if (NULL == t) re
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
一棵 m 阶 B 树(Balance Tree of order m), 或为空树,或满足下列的特性的 m 叉树:(本次实验采用链式存储结构) (1)树中每个结点最多含有 m 棵子树。 (2)若根结点是非终端结点,则至少有 2 棵子树 (3)除根结点之外的所有非终端结点至少有「m/2 棵子树。 (4)每个非终端结点中包含信息:(n,A,K1,A1,K2,A2,…,Kn,An)。其中: ①K(1≤i≤n)为关键字,且关键字按升序推入指针。 ②A(0≤≤n)指向子树的根结点,A(i-1)指向子树中所有结点的关键字均小于 Ki,且大于 K(i-1)。 ③ 关键字的个数 n 必须满足「m/2-1≤n≤m-1。 (5)所有叶子结点都出现在同一层,叶子结点不包含任何信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空。实际上,B 树的结点还应包含 n 个指向每个关键字相应记录的指针。这与应用相关,从略。
资源推荐
资源详情
资源评论
收起资源包目录
100012938-基于C语言实现的B树的抽象数据类型.zip (4个子文件)
btree
LICENSE 1KB
陈智超B树实验报告.doc 1.46MB
BTree.cpp 21KB
README.md 29KB
共 4 条
- 1
资源评论
神仙别闹
- 粉丝: 2674
- 资源: 7640
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功