多路查找树：树的每一个节点的孩子数可以多于两个，而且每一个节点处可以存储多个元素。
概念介绍
2-3树：是多路查找树的一种，其中每一个节点都具有两个孩子（2节点）或三个孩子（3节点）。
2节点：一个2节点包含一个元素和两个孩子（或没有孩子）。与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。和二叉排序树的区别在于，要么2节点的两个孩子都存在，要么这两个孩子都不存在，不会出现只有一个孩子的情况。
3节点：一个3节点包含一个元素和三个孩子（或没有孩子）。与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素，中间子树包含介于左右子树之间的元素。和二叉排序树的区别在于，要么3节点的三个孩子都存在，要么这三个孩子都不存在，不会出现只有一、两个孩子的情况。
// 多路查找树（B树）
#include <stdio.h>
#include <malloc.h>
#define TRUE 1 // 返回值为真
#define FALSE 0 // 返回值为假
#define m 3 // B树的阶，暂时设置为3
#define N 17 // 数据元素个数
typedef int Status; // 函数返回结果类型
// B树结构
typedef struct BTNode {
int keynum; // 节点中关键字个数（节点可存储多个元素的值）
struct BTNode *parent; // 指向双亲节点的指针
struct Node { // 节点结构
int key; // 关键字向量
struct BTNode *ptr; // 子树指针向量
int recptr; // 记录指针向量
} node[m + 1];
} BTNode, *BTree;
// B树查找结果结构
typedef struct {
BTNode *pt; // 指向找到的节点
int i; // 1..m，在节点中的关键字序号
int tag; // 是否找到标记，1表示查找成功，2表示查找失败
} Result;
/**
* 在树中节点查找最接近但小于关键字K的元素的下标
* 在p->node[1..keynum].key中查找i，使得p->node[i].key < K < p->node[i+1].key
* @param p B树
* @param K 关键字
* @return 最接近但小于关键字K的元素的下标
*/
int Search(BTree p, int K) {
int i = 0; // 用来记录最接近但小于关键字K的元素的下标
int j; // 用来遍历元素
// 遍历树中的所有元素，找到最接近但小于关键字K的元素的下标
for (j = 1; j <= p->keynum; j++) {
// 如果该节点的值小于关键字K
if (p->node[j].key <= K) {
i = j; // 记录该元素的下标
}
}
return i; // 返回最接近但小于关键字K的元素的下标
}
/**
* 在m阶B树T上查找关键字K，返回Result结果(pt, i, tag)
* 若查找成功，则Result中tag=1，指针pt所指节点中第i个关键字等于K，
* 查找不成功，Result中tag=0，等于K的关键字应插入在指针pt所值节点中第i和第i+1个关键字之间
* @param T B树
* @param K 关键字
* @return B树查找结果
*/
Result SearchBTree(BTree T, int K) {
BTree p = T; // B树p指向T
BTree q = NULL; // B树q
Status found = FALSE; // 是否找到元素
int i = 0; // 用于记录找到元素的下标
Result r; // B树查找结果
// 未遍历完树T，且未找到值等于关键字K的元素
while (p && !found) {
// 在树中节点查找最接近但小于关键字K的元素的下标
i = Search(p, K);
// 查找到的元素的下标大于0，并且元素的值等于关键字K
if (i > 0 && p->node[i].key == K) {
found = TRUE; // 标记找到元素
} else { // 未找到值等于K的元素
q = p; // q指向当前树节点p
p = p->node[i].ptr; // p指向下一个节点
}
}
r.i = i; // 返回结果的在节点中的关键字序号设置为i
if (found) { // 查找成功
r.pt = p; // pt指向节点中第i个关键字等于K元素
r.tag = 1; // tag=1表示查找成功
} else { // 查找失败
r.pt = q; // pt指向q表示指向将进行插入的位置
r.tag = 0; // tag=0表示查找失败
}
return r;
}
/**
* 将r->key、r和ap分别插入到q->key[i+1]、q->recptr[i+1]和q->ptr[i+1]中
* @param q B树
* @param i 插入位置下标
* @param key 插入的值
* @param ap 新插入节点指向的下一个节点
*/
void Insert(BTree *q, int i, int key, BTree ap) {
int j; // 用来遍历元素
// 将插入位置的元素向后移动一位，空出(*q)->node[i+1]的位置
for (j = (*q)->keynum; j > i; j--) {
(*q)->node[j + 1] = (*q)->node[j];
}
(*q)->node[i + 1].key = key; // 设置新插入节点的值
(*q)->node[i + 1].ptr = ap; // 设置新插入节点指向的的子树节点
(*q)->node[i + 1].recptr = key; // 设置新插入节点的记录的指针向量
(*q)->keynum++; // 树中节点个数增加
}
/**
* 将节点q分拆成两个节点，前一半保留，后一遍移入新生节点ap
* @param q 原节点，前一半的值保留在此节点
* @param aq 新节点，后一半的值移动到此节点
*/
void split(BTree *q, BTree *ap) {
int i, s = (m + 1) / 2; // 用来遍历元素，s是节点个数的一半
*ap = (BTree) malloc(sizeof(BTNode)); // 为新节点分配存储空间
(*ap)->node[0].ptr = (*q)->node[s].ptr; // 新节点ap指向原节点的下一个元素
// 将后一般的元素移动到新节点
for (i = s + 1; i <= m; i++) {
(*ap)->node[i - s] = (*q)->node[i]; // 将后一半的元素值设置到新节点
if ((*ap)->node[i - s].ptr) { // 若新节点的子树指针有值
(*ap)->node[i - s].ptr->parent = *ap; // 将元素的父节点指针指向ap
}
}
(*ap)->keynum = m - s; // qp树节点个数等于
(*ap)->parent = (*q)->parent;
(*q)->keynum = s - 1; // q树节点个数减1
}
/**
* 生成新的根节点
* @param T
* @param key 节点值
* @param ap
*/
void NewRoot(BTree *T, int key, BTree ap) {
BTree p; // 新的根节点
p = (BTree) malloc(sizeof(BTNode)); // 为新的根节点分配存储空间
p->node[0].ptr = *T; // 根节点的第0个元素指向原来的T节点（成为新的根节点的子元素）
*T = p; // T节点指向新的根节点
// 如果新节点第0个元素的指向的值非空
if ((*T)->node[0].ptr) {
// 让新节点第0个元素的指向的值的父节点为T
(*T)->node[0].ptr->parent = *T;
}
(*T)->parent = NULL; // 设置新的根节点无双亲
(*T)->keynum = 1; // 设置根节点的元素数量为1
(*T)->node[1].key = key; // 设置根节点元素的值
(*T)->node[1].recptr = key; // 设置记录指针向量为key
(*T)->node[1].ptr = ap; // 设置根节点第1个元素指向ap节点
// 如果新节点第1个元素的指向的值非空
if ((*T)->node[1].ptr) {
// 让新节点第1个元素的指向的值的父节点为T
(*T)->node[1].ptr->parent = *T;
}
}
/**
* 在m阶B上T上节点*q的key[i]与key[i+1]之间插入关键字K的指针r
* 若引起节点过大，则沿双亲链进行必要的节点分拆调整，使T仍是m阶B树
* @param T B树
* @param key 关键字
* @param q
* @param i
*/
void InsertBTree(BTree *T, int key, BTree q, int i) {
BTree ap = NULL; //
Status finished = FALSE; // 是否插入完成的标记
int s; // 用来获取节点中间位置的下标
int rx; // 用于 获取中间位置的记录数
rx = key; // 设置记录数等于关键字
// 当q节点非空，插入未完成
while (q && !finished) {
// 将值为rx的元素插入到树qe的第i个位置
Insert(&q, i, rx, ap);
// 若插入后B树q的节点数小于阶数
if (q->keynum < m) {
finished = TRUE; // 插入完成
} else { // B树q的节点数大于等于m，将分拆该节点
s = (m + 1) / 2; // 获取中间节点下标
rx = q->node[s].recptr; // 获取中间位置的记录数
split(&q, &ap); // 对节点进行分拆
q = q->parent; // q指向自己的双亲节点
if (q) {
i = Search(q, key); // 在双亲节点*q中查找rx->key的插入位置
}
}
}
// 当插入未完成
if (!finished) {
NewRoot(T, rx, ap); // 创建新的根节点
}
}
/**
* 打印B树中第i个节点的值
* @param p B树
* @param i 节点下标
*/
void print(BTNode p, int i) {
printf("(%d)", p.node[i].key);
}
int main() {
int r[N] = {22, 16, 41, 58, 8, 11, 12, 16, 17, 22, 23, 31, 41, 52, 58, 59, 61};
BTree T = NULL; // B树
Result result; // B树查找结果结构
int i; // 用来遍历元素
for (i = 0; i < N; i++) {
// 在B树T中搜索数组r中下标为i的元素，并返回搜索结果
result = SearchBTree(T, r[i]);
// 如果r中下标为i的元素在B中T中不存在，将该元素插入B中T中
if (!result.tag) {
InsertBTree(&T, r[i], result.pt, result.i);
}
}
printf("\n请输入待查找记录的关键字：");
scanf("%d", &i);
result = SearchBTree(T, i); // 在B树中搜索该关键字，并获取结果
// 如果该结果标记为已找到
if (result.tag) {
print(*(result.pt), result.i); // 打印B树中第i个节点的值
} else {
printf("未找到该关键字");
}
return 0;
}
运行结果1
运行结果2
网友评论