原 B树C语言代码实现
在这里实现的是在主存中的操作，没有进行文件的存储和修改。
头文件btree.h：
#ifndef _BTREE_H
#define _BTREE_H
#define MIN_T 3
#define MAX_T (MIN_T * 2)
typedef struct BTreeNodedata BTreeNodedata;
typedef struct BTreeNodedata *BTreeNode;
typedef struct BTreedata BTreedata;
typedef struct BTreedata *BTree;
/*
* B树结点结构体
*/
struct BTreeNodedata
{
int n; //关键字个数
int leaf; 是否是叶子结点，1为叶子结点，0反之
int key[MAX_T - 1]; //关键字，这里的关键字为了简便编程设为int
BTreeNode child[MAX_T]; //子结点
};
/*
* B树的结构体
*/
struct BTreedata
{
BTreeNode root; //B树的根结点
};
#define BTREE_NODE_SIZE sizeof(BTreeNodedata)
#define BTREE_SIZE sizeof(BTreedata)
BTreeNode allocate_node(); //为结点分配空间
void btree_create(BTree tree); //初始化树
void btree_search(BTreeNode node, int key); //寻找关键字位置
void btree_split_child(BTreeNode node, int location); //分裂子结点
void btree_insert_nonfull(BTreeNode node, int key); //向未满结点插入关键字
void btree_insert(BTree tree, int key); //向树插入关键字
void display_node(BTreeNode *node_first, int n); //显示以结点node_first为父结点的树
void display_btree(BTree tree); //显示整棵树
BTreeNode btree_minimum(BTreeNode node); //以node为根结点，寻找最小关键字
BTreeNode btree_maximum(BTreeNode node); //以node为根结点，寻找最大关键字
void btree_min(BTree tree); //在整棵树中寻找最小关键字
void btree_max(BTree tree); //在整棵树中寻找最大关键字
void btree_left(BTreeNode parent, BTreeNode node, BTreeNode othernode, int location); //将父结点、右兄弟、该结点的关键字调整
void btree_right(BTreeNode parent, BTreeNode node, BTreeNode othernode, int location); //将父结点、左兄弟、该结点的关键字调整
int btree_merge_child(BTreeNode parent, int location); //合并子结点，并返回下降子结点的位置
void btree_delete_leaf(BTreeNode node, int location); //删除叶子结点关键字
int btree_delete_node_in(BTreeNode r_node, int i); //删除内结点关键字，并返回下降子结点的位置
void btree_delete_node(BTreeNode r_node, int key); //删除以r_node为根结点的树中关键字
void btree_delete(BTree tree, int key); //删除树中的关键字
#endif程序btree.c：
#include "btree.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <assert.h>
/*
* 为新结点分配空间
*/
BTreeNode
allocate_node()
{
BTreeNode node = (BTreeNode) malloc (BTREE_NODE_SIZE);
return node;
}
/*
* 生成一棵空树
* 关键字个数为0，且为叶子结点
*/
void
btree_create(BTree tree)
{
BTreeNode r_node = allocate_node();
(r_node)->n = 0;
(r_node)->leaf = 1;
(tree)->root = r_node;
}
/*
* 在以node为根结点的树中，寻找关键字位置
* 返回关键字所在结点，并将关键字位置保存在location
*/
void
btree_search(BTreeNode node, int key)
{
int j = 0;
/*
* 遍历当前结点，寻找恰当的关键字，如果找到相等的关键字，返回结点并将关键字位置保存在location
* 如果没找到相等结点，且该结点为叶子结点，则报错
* 否则递归寻找
*/
while(j < node->n && key > node->key[j])
j++;
if(j < node->n && key == node->key[j])
{
printf("the %d key's location is %d in the node %p\n", key, j, node);
}
else if(node->leaf)
{
printf("error:there is no a key\n");
}
else btree_search(node->child[j], key);
}
/*
* 分裂父结点node中位置为location的子结点的满结点
*/
void
btree_split_child(BTreeNode node, int location)
{
/* 建立新的空结点 */
BTreeNode newnode = allocate_node();
BTreeNode childnode = node->child[location];
int i = 0;
/* 初始化空结点newnode，将子结点childnode的信息复制到新结点node中 */
newnode->leaf = childnode->leaf;
newnode->n = MIN_T - 1;
/* 将子结点childnode后T-1个关键字复制到新结点中，并改变子结点的n值 */
for(i = 0;i <= MIN_T - 2;i++)
newnode->key[i] = childnode->key[i + MIN_T];
childnode->n = MIN_T - 1;
/* 如果子结点非叶子结点，则相应的将子结点的结点点复制到新结点中 */
if(!childnode->leaf)
for(i = 0;i <= MIN_T - 1;i++)
newnode->child[i] = childnode->child[i + MIN_T];
/* 将父结点对应的关键字以及子结点位置向后移动一位 */
for(i = node->n;i > location;i--)
{
node->key[i] = node->key[i - 1];
node->child[i+1] = node->child[i];
}
/* 为父结点增加新的关键字和子结点，并修改n值 */
node->child[location + 1] = newnode;
node->key[location] = childnode->key[MIN_T - 1];
node->n = node->n + 1;
}
/*
* 对非满结点进行插入关键字
*/
void
btree_insert_nonfull(BTreeNode node, int key)
{
int i = node->n - 1;
if(node->leaf)
{
/* 该结点为叶子结点时，找到对应位置，将关键字插入，并对结点node做出修改 */
while(i >=0 && key < node->key[i])
{
node->key[i+1] = node->key[i];
i--;
}
node->key[i+1] = key;
node->n = node->n + 1;
}
else
{
/* 非叶子结点时，查找对应子结点，判断其是否为满结点，是，则分裂，否递归插入 */
while(i >=0 && key < node->key[i])
i--;
i++;
if(node->child[i]->n == MAX_T - 1)
{
btree_split_child(node, i);
if(key > node->key[i])
i++;
}
btree_insert_nonfull(node->child[i], key);
}
}
/*
* 对整棵树进行插入关键字
* 当树为有且只有一个关键字，且已满时，需要建立新的结点作为树的根结点，
* 而当原树的根结点作为新结点的子结点，进行分裂操作
* 否则，直接进行非满结点插入操作
*/
void
btree_insert(BTree tree, int key)
{
BTreeNode r_node = tree->root;
if(r_node->n == MAX_T - 1)
{
BTreeNode r_node_new = allocate_node();
r_node_new->leaf = 0;
r_node_new->n = 0;
r_node_new->child[0] = r_node;
tree->root = r_node_new;
btree_split_child(r_node_new, 0);
btree_insert_nonfull(r_node_new, key);
}
else btree_insert_nonfull(r_node, key);
}
/*
* 为了验证插入以及删除结果正确，添加输出函数
* 输出以parent为父结点的子树的所有关键字
* 这里将所有的同一层的结点放入到一个数组中，方便输出
* 第一个参数node_first作为每一层结点数组的起始地址
* n为该层结点数
*/
void
display_node(BTreeNode *node_first, int n)
{
int i = 0, j = 0, k = 0,all = 0;
BTreeNode *node = node_first;
/* 将该层的结点所有的关键字输出，不同结点以“ ”为分隔，每层以“$$”为分隔 */
for(i = 0; i < n; i++)
{
for(j = 0; j < (*(node + i))->n; j++)
{
printf("%d ", (*(node + i))->key[j]);
}
all = all + (*(node + i))->n + 1;
//printf(" %p ", *(node + i));
printf(" ");
}
printf("$$\n");
if(!(*node)->leaf)
{
BTreeNode nodes[all];
i = 0;
for(j = 0; j < n; j++)
{
for(k = 0; k <= (*(node + j))->n; k++)
{
nodes[i] = (*(node + j))->child[k];
i++;
}
}
display_node(nodes, all);
}
}
/*
* 为了验证插入和删除操作的正确性，添加输出函数
* 将整棵树输出
*/
void
display_btree(BTree tree)
{
BTreeNode r_node = tree->root;
display_node(&r_node, 1);
}
/*
* 返回以node为根结点树的最小关键字的结点，关键字的位置肯定为0
*/
BTreeNode
btree_minimum(BTreeNode node)
{
BTreeNode newnode = node;
if(newnode->n < 1)
{
printf("this is null tree\n");
return NULL;
}
if(node->leaf)
return newnode;
else
newnode = btree_minimum(node->child[0]);
return newnode;
}
/*
* 返回以node为根结点树的最大关键字的结点，关键字的位置肯定为该结点的n-1值
*/
BTreeNode
btree_maximum(BTreeNode node)
{
BTreeNode newnode = node;
if(newnode->n < 1)
{
printf("this is null tree\n");
return NULL;
}
if(node->leaf)
return newnode;
else
newnode = btree_maximum(node->child[node->n]);
return newnode;
}
/*
* 输出整棵树的最小关键字
*/
void
btree_min(BTree tree)
{
BTreeNode r_node = tree->root;
BTreeNode n_node = btree_minimum(r_node);
printf("the min is %d\n", n_node->key[0]);
}
/*
* 输出整棵树的最大关键字
*/
void
btree_max(BTree tree)
{
BTreeNode r_node = tree->root;
BTreeNode n_node = btree_maximum(r_node);
printf("the max is %d\n", n_node->key[n_node->n - 1]);
}
/*
* 当下降的结点node的关键字个数为T-1时，
* 为了满足下降过程中，遇到的结点的关键字个数大于等于T，
* 对结点parent、node、othernode三个结点的关键字做调整。
* 当node在other左侧时，即node的右结点时（父结点的右子结点）， * 在T+1位置，增加一个关键字，其值为父结点对应的关键字值，
* 将父结点对应关键字值赋值为右子结点中的第一个关键字。
* 将右子结点的关键字和子结点（如果有的话）向前移动一位
* 修改右子结点以及该结点的n值
*/
void
btree_left(BTreeNode parent, BTreeNode node, BTreeNode othernode, int location)
{
int i = 0;
node->key[node->n] = parent->key[location];
parent->key[location] = othernode->key[0];
for(i = 0; i <= othernode->n - 2; i++)
othernode->key[i] = othernode->key[i + 1];
if(!othernode->leaf)
{
node->child[node->n + 1] = othernode->child[0];
for(i = 0; i <= othernode->n - 1; i++)
othernode->child[i] = othernode->child[i + 1];
}
node->n = node->n + 1;
othernode->n = othernode->n - 1;
}
/*
* 当下降的结点node的关键字个数为T-1时，
* 为了满足下降过程中，遇到的结点的关键字个数大于等于T，
* 对结点parent、node、othernode三个结点的关键字做调整。
* 当node在other右侧时，即node的左结点时（父结点的左子结点），
* node结点的关键字和子结点（如果有的话）向后移动一位,
* 在第一个位置增加一个关键字，其值为父结点对应的关键字值，
* 将父结点对应关键字值赋值为左子结点中的最后一个关键字。
* 修改左子结点和该结点的n值
*/
void
btree_right(BTreeNode parent, BTreeNode node, BTreeNode othernode, int location)
{
int i = 0;
for(i = node->n - 1; i >= 0; i--)
othernode->key[i+1] = othernode->key[i];
node->key[0] = parent->key[location];
parent->key[location] = othernode->key[othernode->n];
if(!node->leaf)
{
node->child[0] = othernode->child[othernode->n + 1];
for(i = othernode->n; i >= 0; i--)
othernode->child[i + 1] = othernode->child[i];
}
node->n = node->n + 1;
othernode->n = othernode->n - 1;
}
/*
* 合并两个关键字个数为T-1父结点为parent位置为location的子结点
* 以父结点对应的关键字为中间值连接两个子结点
* 并返回需要下降的子结点位置
*/
int
btree_merge_child(BTreeNode parent, int location)
{
int i;
BTreeNode lnode = NULL;
BTreeNode rnode = NULL;
if(location == parent->n)
location--;
lnode = parent->child[location];
rnode = parent->child[location + 1];
/* 将父结点对应的关键字以及右兄弟所有的关键字复制该结点，同时修改左子的n值 */
lnode->key[lnode->n] = parent->key[location];
for(i = 0; i < rnode->n; i++)
{
lnode->key[MIN_T + i] = rnode->key[i];
lnode->n++;
}
/* 如果有子结点同样复制到该结点 */
if(!rnode->leaf)
for(i = 0; i <= rnode->n; i++)
lnode->child[MIN_T + i] = rnode->child[i];
rnode->n= 0;
lnode->n = MAX_T - 1;
/* 对父结点相应的关键字和子结点位置发生变化 */
for(i = location; i < parent->n - 1; i++)
{
parent->key[i] = parent->key[i + 1];
parent->child[i + 1] = parent->child[i + 2];
}
/* 调整父结点的n值 */
parent->n = parent->n - 1;
rnode = NULL;
return location;
}
/*
* 对叶子结点node位置为location的关键字删除
* 直接将位置location后的关键字向前移动一位
*/
void
btree_delete_leaf(BTreeNode node, int location)
{
int i = 0;
for(i = location; i < node->n - 1; i++)
node->key[i] = node->key[i + 1];
node->n = node->n - 1;
}
/*
* 删除该层数组坐标为i的关键字
*/
int
btree_delete_node_in(BTreeNode r_node, int i)
{
BTreeNode lnode = r_node->child[i];
BTreeNode rnode = r_node->child[i + 1];
int temp = 0;
/*
* 当前于该位置的关键字的左子结点关键字个数大于等于T时，
* 寻找该位置的关键的前驱（左子结点的最大关键字）
*/
if(lnode->n >= MIN_T)
{
BTreeNode newnode = btree_maximum(lnode);
temp = r_node->key[i];
r_node->key[i] = newnode->key[newnode->n - 1];
newnode->key[newnode->n - 1] = temp;
}
/*
* 相反的，若右子结点符合条件，则找寻后继（即右子结点的最小关键字）
*/
else if(rnode->n >= MIN_T)
{
BTreeNode newnode = btree_minimum(rnode);
temp = r_node->key[i];
r_node->key[i] = newnode->key[0];
newnode->key[0] = temp;
i++;
}
/*
* 当左右子结点都不符合条件，则合并两个子结点
*/
else i = btree_merge_child(r_node, i);
return i;
}
/*
* 删除以r_node为根结点的树的关键字key
*/
void
btree_delete_node(BTreeNode r_node, int key)
{
int i = 0;
/* 寻找关键字位置，或者下降的子结点位置 */
while(i < r_node->n && key > r_node->key[i])
i++;
/* 若再该层且为叶子结点删除结点，否则下降寻找结点删除 */
if(i < r_node->n && key == r_node->key[i])
if(r_node->leaf)
btree_delete_leaf(r_node, i);
else
{
i = btree_delete_node_in(r_node, i);
btree_delete_node(r_node->child[i], key);
}
else
{
if(r_node->leaf)
printf("there is no the key %d!!\n", key);
else
{
if(r_node->child[i]->n >= MIN_T){
btree_delete_node(r_node->child[i], key);}
else
{
if(i > 0 && r_node->child[i - 1]->n >= MIN_T)
{
btree_right(r_node, r_node->child[i], r_node->child[i - 1], i);}
else if(i < r_node->n && r_node->child[i + 1]->n >= MIN_T)
btree_left(r_node, r_node->child[i], r_node->child[i + 1], i);
else
i = btree_merge_child(r_node, i);
btree_delete_node(r_node->child[i], key);
}
}
}
}
/*
* 删除树内的关键字key，如果根结点为空，则替换根结点
*/
void
btree_delete(BTree tree, int key)
{
BTreeNode r_node = tree->root;
btree_delete_node(r_node, key);
if(tree->root->n == 0 && tree->root->leaf == 0)
tree->root = tree->root->child[0];
}这是实现B树的详细C代码。
为了验证结果我以1-100数字作为关键字插入到树中，并且查找5，33的位置，删除100，94，81，36，42，下面看一下结果：
int main()
{
BTree tree = (BTree) malloc (BTREE_SIZE);
tree->root = (BTreeNode) malloc (BTREE_NODE_SIZE);
int keys[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,25,24,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,
82,81,83,84,85,86,87,88,89,90,91,92,99,94,93,95,96,97,98,100};
int i = 0;
btree_create(tree);
for(i = 0; i <= 99; i++){
btree_insert(tree, keys[i]);
//display_btree(&tree);
}
btree_max(tree);
display_btree(tree);
btree_max(tree);
btree_min(tree);
btree_search(tree->root,5);
btree_search(tree->root,33);
btree_delete(tree, 100);
display_btree(tree);
btree_delete(tree, 94);
display_btree(tree);
btree_delete(tree, 81);
display_btree(tree);
btree_delete(tree, 36);
display_btree(tree);
btree_delete(tree, 42);
display_btree(tree);
btree_max(tree);
btree_min(tree);
free(tree);
return 0;
}[root@localhost ~]# gcc -o btree btree.c -Wall
[root@localhost ~]# ./btree
the max is 100输出完全插入后的树：
27 54 $$
9 18 36 45 63 72 81 90 $$
3 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 84 87 93 96 $$
1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 91 92 94 95 97 98 99 100 $$输出关键字的做大最小值：
the max is 100
the min is 1输出5，33的位置
the 5 key's location is 1 in the node 0x9ff50c0
the 33 key's location is 1 in the node 0x9ff53d0删除100后的树：
27 54 $$
9 18 36 45 63 72 81 $$
3 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 84 87 90 93 96 $$
1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 91 92 94 95 97 98 99 $$删除94后的树：
27 54 $$
9 18 36 45 63 72 81 $$
3 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 84 87 90 93 97 $$
1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 91 92 95 96 98 99 $$删除81后的树：
27 54 $$
9 18 36 45 63 72 82 $$
3 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 87 90 93 97 $$
1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 83 84 85 86 88 89 91 92 95 96 98 99 $$删除36后的树：
27 63 $$
9 18 45 54 72 82 $$
3 6 12 15 21 24 30 33 39 42 48 51 57 60 66 69 75 78 87 90 93 97 $$
1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 83 84 85 86 88 89 91 92 95 96 98 99 $$删除42后的树：
27 $$
9 18 45 54 63 72 82 $$
3 6 12 15 21 24 30 33 39 48 51 57 60 66 69 75 78 87 90 93 97 $$
1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 83 84 85 86 88 89 91 92 95 96 98 99 $$最后再输出一次最大最小值：
the max is 99
the min is 1本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读