B树C语言代码实现 - HelloWorld开发者社区

在这里实现的是在主存中的操作，没有进行文件的存储和修改。

头文件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

Android进阶之旅-(NDK实战篇之C/C++进阶)

Andriod第三方源码分析

热门文章