当前位置：首页 > news >正文

C语言实现数据结构B树

news 2025/7/12 12:57:06

B树（B-Tree）是一种自平衡的树数据结构，它维护着数据的有序性，并允许搜索、顺序访问、插入、删除等操作都在对数时间内完成。B树广泛用于数据库和操作系统的文件系统中。

B树的基本特性

根节点：根节点至少有两个子节点（除非它是叶子节点）。
内部节点：每个内部节点包含的关键字（或称“键”）数量m满足⌈m/2⌉ - 1 ≤ n ≤ m - 1，其中n是节点中关键字的数量，m是节点的最大容量（对于所有节点相同）。
叶子节点：所有叶子节点都在同一层上，并且不带信息（或带有指向数据记录的指针），也可以包含关键字信息。
分裂与合并：当节点中的关键字数量超过m-1时，该节点分裂成两个节点；当节点中的关键字数量少于⌈m/2⌉-1时，可能通过与其兄弟节点合并来避免这种情况。
关键字排序：节点内的关键字按升序排列，使得每个关键字都是其左子树所有值的最大值，也是其右子树所有值的最小值（对于非叶子节点）。

B树的C语言实现概述

这里我们不会完整地实现一个B树，但会展示一些关键部分，如节点结构定义、插入和分裂的简化逻辑。

节点结构定义


#include <stdio.h>  
#include <stdlib.h>  #define MAX_KEYS 4  // 假设每个节点的最大关键字数量为4  typedef struct BTreeNode {  int keys[MAX_KEYS];  // 存储关键字  int numKeys;         // 当前节点中关键字的数量  struct BTreeNode *children[MAX_KEYS + 1];  // 子节点指针数组，比关键字数多一个  struct BTreeNode *parent;  // 父节点指针  int isLeaf;  // 标记是否为叶子节点  
} BTreeNode;  // 初始化节点  
BTreeNode* createNode(int isLeaf) {  BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));  node->numKeys = 0;  node->parent = NULL;  node->isLeaf = isLeaf;  for (int i = 0; i <= MAX_KEYS; i++) {  node->children[i] = NULL;  }  return node;  
}

插入操作（简化版）

插入操作涉及在树中找到合适的位置插入新关键字，并在必要时分裂节点。这里只提供一个概念性的伪代码：

// 假设已有函数insertNonFull，用于向非满节点中插入关键字  
void insert(BTreeNode* root, int key) {  if (root == NULL) {  // 创建新的根节点  root = createNode(1);  // 假设根节点总是叶子  root->keys[0] = key;  root->numKeys = 1;  } else {  // 找到插入的位置  BTreeNode* node = findLeaf(root, key);  // 假设有findLeaf函数  // 插入到叶子节点  if (node->numKeys < MAX_KEYS) {  insertNonFull(node, key);  } else {  // 节点已满，需要分裂  splitChild(node, findInsertPos(node->keys, node->numKeys, key));  // 递归向上调整父节点  // 可能需要再次分裂父节点  }  }  
}
注意：上述代码是高度简化的，并未实现findLeaf、insertNonFull、findInsertPos、splitChild等函数，这些函数是实现B树的关键。