原 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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

单链表

线性表的链式表示和实现       线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以使不连续的)。因此,为...

2855
来自专栏后端之路

最熟悉的ArrayList

上来先问几个问题 ArrayList是否存在最大容量? 如果ArrayList存在最大容量 那么达到最大之后会如何处理 ArrayList的性能影响因素 Arr...

1895
来自专栏从流域到海域

二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合 性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:...

2229
来自专栏拭心的安卓进阶之路

Java 集合深入理解(7):ArrayList

今天心情有点美丽,学学 ArrayList 放松下吧! 什么是 ArrayList ? ? ArrayList 是 Java 集合框架中 List接口 的一个实...

2167
来自专栏mathor

LeetCode222. 完全二叉树的节点个数

 常规思路,遍历整棵树,时间复杂度O(N),但是有一种时间复杂度小于O(N)的做法  首先遍历头结点右子树的最左边界,如果最左边界不为空,说明头结点的左子...

903
来自专栏数据结构与算法

codevs 1814 最长链

1814 最长链 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 现给出...

2995
来自专栏Java爬坑系列

【Java入门提高篇】Day21 容器类详解(四)ArrayList源码分析

   今天要介绍的是List接口中最常用的实现类——ArrayList,本篇的源码分析基于JDK8,如果有不一致的地方,可先切换到JDK8后再进行操作。

1936
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

1033
来自专栏趣学算法

数据结构 第4讲 单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

953
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

1956

扫码关注云+社区