B树&&B+树

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义 B 树的最小度数（每个节点至少有 t 个孩子，最多有 2t - 1 个键值）
5. #define T 3
7. // B 树节点结构
8. typedef struct BTreeNode {
9.     int *keys;               // 存储键值的数组
10.     int t;                   // 最小度数
11.     struct BTreeNode **C;    // 子节点指针数组
12.     int n;                   // 当前节点的键值个数
13.     int leaf;                // 是否是叶子节点
14. } BTreeNode;
16. // 创建一个新的 B 树节点
17. BTreeNode *createNode(int t, int leaf) {
18.     BTreeNode *node = (BTreeNode *)malloc(sizeof(BTreeNode));
19.     if (!node) {
20.         fprintf(stderr, "Memory allocation failed for BTreeNode.\n");
21.         exit(EXIT_FAILURE);
22.     }
24.     node->t = t;
25.     node->leaf = leaf;
26.     node->keys = (int *)malloc((2 * t - 1) * sizeof(int));
27.     node->C = (BTreeNode **)malloc(2 * t * sizeof(BTreeNode *));
28.     node->n = 0;
30.     if (!node->keys || !node->C) {
31.         fprintf(stderr, "Memory allocation failed for keys or children.\n");
32.         exit(EXIT_FAILURE);
33.     }
35.     return node;
36. }
38. // 遍历 B 树（中序遍历）
39. void traverse(BTreeNode *root) {
40.     if (root == NULL) return;
42.     // 遍历每个键值前的子树
43.     for (int i = 0; i < root->n; i++) {
44.         if (!root->leaf) {
45.             traverse(root->C[i]);
46.         }
47.         printf("%d ", root->keys[i]); // 打印键值
48.     }
50.     // 遍历最后一个子树
51.     if (!root->leaf) {
52.         traverse(root->C[root->n]);
53.     }
54. }
56. // 搜索键值
57. BTreeNode *search(BTreeNode *root, int k) {
58.     int i = 0;
60.     // 在当前节点中查找键值的位置
61.     while (i < root->n && k > root->keys[i]) {
62.         i++;
63.     }
65.     // 如果找到键值，返回当前节点
66.     if (i < root->n && root->keys[i] == k) {
67.         return root;
68.     }
70.     // 如果是叶子节点，直接返回 NULL
71.     if (root->leaf) {
72.         return NULL;
73.     }
75.     // 在对应的子节点递归查找
76.     return search(root->C[i], k);
77. }
79. // 分裂子节点 y
80. void splitChild(BTreeNode *parent, int i, BTreeNode *y) {
81.     int t = y->t;
83.     // 创建新节点 z，存储 y 的后半部分键值和子节点
84.     BTreeNode *z = createNode(t, y->leaf);
85.     z->n = t - 1;
87.     // 将 y 的后半部分键值复制到 z
88.     for (int j = 0; j < t - 1; j++) {
89.         z->keys[j] = y->keys[j + t];
90.     }
92.     // 如果 y 不是叶子节点，将 y 的后半部分子节点指针复制到 z
93.     if (!y->leaf) {
94.         for (int j = 0; j < t; j++) {
95.             z->C[j] = y->C[j + t];
96.         }
97.     }
99.     y->n = t - 1; // 更新 y 的键值个数
101.     // 将 z 插入到 parent 的子节点列表中
102.     for (int j = parent->n; j >= i + 1; j--) {
103.         parent->C[j + 1] = parent->C[j];
104.     }
105.     parent->C[i + 1] = z;
107.     // 将 y 的中间键提升到 parent
108.     for (int j = parent->n - 1; j >= i; j--) {
109.         parent->keys[j + 1] = parent->keys[j];
110.     }
111.     parent->keys[i] = y->keys[t - 1];
112.     parent->n++;
113. }
115. // 插入到非满节点中
116. void insertNonFull(BTreeNode *node, int k) {
117.     int i = node->n - 1;
119.     // 如果是叶子节点
120.     if (node->leaf) {
121.         // 找到插入位置并移动键值
122.         while (i >= 0 && k < node->keys[i]) {
123.             node->keys[i + 1] = node->keys[i];
124.             i--;
125.         }
126.         node->keys[i + 1] = k; // 插入键值
127.         node->n++;
128.     } else {
129.         // 找到子节点的位置
130.         while (i >= 0 && k < node->keys[i]) {
131.             i--;
132.         }
133.         i++;
135.         // 如果子节点已满，先分裂子节点
136.         if (node->C[i]->n == 2 * node->t - 1) {
137.             splitChild(node, i, node->C[i]);
139.             // 判断 k 应插入到哪个子节点
140.             if (k > node->keys[i]) {
141.                 i++;
142.             }
143.         }
144.         insertNonFull(node->C[i], k);
145.     }
146. }
148. // 插入键值到 B 树
149. void insert(BTreeNode **rootRef, int k, int t) {
150.     BTreeNode *root = *rootRef;
152.     // 如果根节点已满
153.     if (root->n == 2 * t - 1) {
154.         // 创建新根节点
155.         BTreeNode *newRoot = createNode(t, 0);
156.         newRoot->C[0] = root;
158.         // 分裂旧根节点
159.         splitChild(newRoot, 0, root);
161.         // 插入到合适的子节点
162.         int i = 0;
163.         if (k > newRoot->keys[0]) {
164.             i++;
165.         }
166.         insertNonFull(newRoot->C[i], k);
168.         *rootRef = newRoot; // 更新根节点
169.     } else {
170.         insertNonFull(root, k);
171.     }
172. }
174. // 释放 B 树节点
175. void freeBTree(BTreeNode *node) {
176.     if (node == NULL) return;
178.     if (!node->leaf) {
179.         for (int i = 0; i <= node->n; i++) {
180.             freeBTree(node->C[i]);
181.         }
182.     }
184.     free(node->keys);
185.     free(node->C);
186.     free(node);
187. }
189. // 主函数
190. int main() {
191.     // 创建空 B 树
192.     BTreeNode *root = createNode(T, 1);
194.     // 插入一些数据
195.     insert(&root, 10, T);
196.     insert(&root, 20, T);
197.     insert(&root, 5, T);
198.     insert(&root, 6, T);
199.     insert(&root, 12, T);
200.     insert(&root, 30, T);
201.     insert(&root, 7, T);
202.     insert(&root, 17, T);
204.     // 遍历 B 树
205.     printf("Traversal of the B-Tree:\n");
206.     traverse(root);
207.     printf("\n");
209.     // 搜索键值
210.     int key = 6;
211.     printf("Searching for key %d in the B-Tree...\n", key);
212.     BTreeNode *result = search(root, key);
213.     if (result != NULL) {
214.         printf("Key %d found in the B-Tree.\n", key);
215.     } else {
216.         printf("Key %d not found in the B-Tree.\n", key);
217.     }
219.     // 释放 B 树
220.     freeBTree(root);
222.     return 0;
223. }

复制代码

  C语言b树

  

• 数据结构：
  
  
  
  • 每个节点存储一个 keys 数组和一个 C 子节点指针数组。
    
  • n 表现当前键值数，leaf 表现是否为叶子节点。
    
  
  
• 主要功能：
  
  
  
  • 创建节点：createNode 动态分配节点。
    
  • 插入：插入时处理节点分裂，包管 B 树平衡。
    
  • 查找：递归在树中查找键值。
    
  • 遍历：按中序遍历输出键值。
    
  • 释放内存：freeBTree 确保无内存泄漏。
    
  
  
• 加强结实性：
  
  
  
  • 内存分配检测：每次动态分配都检查是否乐成。
    
  • 边界条件处理：空树或单节点插入、满节点分裂等情况均已处理。
    
  
  

1. #include <iostream>
2. #include <vector>
3. #include <memory>
4. using namespace std;
6. // 定义 B 树的最小度数
7. const int T = 3; // 每个节点最多 2*T-1 个键，最少 T-1 个键
9. // B 树节点类
10. class BTreeNode {
11. public:
12.     vector<int> keys;                   // 键值数组
13.     vector<shared_ptr<BTreeNode>> children; // 子节点指针数组
14.     int t;                              // 最小度数
15.     bool leaf;                          // 是否为叶子节点
17.     // 构造函数
18.     BTreeNode(int t, bool leaf) : t(t), leaf(leaf) {}
20.     // 遍历 B 树（中序遍历）
21.     void traverse() {
22.         int i;
23.         // 遍历每个键值前的子树
24.         for (i = 0; i < keys.size(); i++) {
25.             if (!leaf) {
26.                 children[i]->traverse();
27.             }
28.             cout << keys[i] << " ";
29.         }
31.         // 遍历最后一个子树
32.         if (!leaf) {
33.             children[i]->traverse();
34.         }
35.     }
37.     // 搜索键值
38.     shared_ptr<BTreeNode> search(int k) {
39.         int i = 0;
41.         // 找到第一个大于或等于 k 的键
42.         while (i < keys.size() && k > keys[i]) {
43.             i++;
44.         }
46.         // 如果键值等于 k，返回当前节点
47.         if (i < keys.size() && keys[i] == k) {
48.             return shared_from_this();
49.         }
51.         // 如果是叶子节点，则键值不存在
52.         if (leaf) {
53.             return nullptr;
54.         }
56.         // 在对应的子节点递归查找
57.         return children[i]->search(k);
58.     }
60.     // 分裂子节点
61.     void splitChild(int i, shared_ptr<BTreeNode> y) {
62.         // 创建一个新节点 z，存储 y 的后半部分键值和子节点
63.         auto z = make_shared<BTreeNode>(y->t, y->leaf);
64.         z->keys.resize(t - 1);
66.         for (int j = 0; j < t - 1; j++) {
67.             z->keys[j] = y->keys[j + t];
68.         }
70.         // 如果 y 不是叶子节点，将 y 的后半部分子节点移动到 z
71.         if (!y->leaf) {
72.             z->children.resize(t);
73.             for (int j = 0; j < t; j++) {
74.                 z->children[j] = y->children[j + t];
75.             }
76.         }
78.         // 调整 y 的键值数
79.         y->keys.resize(t - 1);
81.         // 在父节点中插入新的子节点 z
82.         children.insert(children.begin() + i + 1, z);
84.         // 将 y 的中间键提升到父节点
85.         keys.insert(keys.begin() + i, y->keys[t - 1]);
86.     }
88.     // 插入到非满节点中
89.     void insertNonFull(int k) {
90.         int i = keys.size() - 1;
92.         if (leaf) {
93.             // 如果是叶子节点，找到插入位置并插入
94.             while (i >= 0 && k < keys[i]) {
95.                 i--;
96.             }
97.             keys.insert(keys.begin() + i + 1, k);
98.         } else {
99.             // 找到子节点位置
100.             while (i >= 0 && k < keys[i]) {
101.                 i--;
102.             }
103.             i++;
105.             // 如果子节点已满，先分裂子节点
106.             if (children[i]->keys.size() == 2 * t - 1) {
107.                 splitChild(i, children[i]);
109.                 // 判断插入位置
110.                 if (k > keys[i]) {
111.                     i++;
112.                 }
113.             }
114.             children[i]->insertNonFull(k);
115.         }
116.     }
117. };
119. // B 树类
120. class BTree {
121. private:
122.     shared_ptr<BTreeNode> root; // 根节点
123.     int t;                      // 最小度数
125. public:
126.     // 构造函数
127.     BTree(int t) : t(t), root(nullptr) {}
129.     // 遍历 B 树
130.     void traverse() {
131.         if (root != nullptr) {
132.             root->traverse();
133.         }
134.     }
136.     // 搜索键值
137.     shared_ptr<BTreeNode> search(int k) {
138.         if (root == nullptr) {
139.             return nullptr;
140.         } else {
141.             return root->search(k);
142.         }
143.     }
145.     // 插入键值
146.     void insert(int k) {
147.         if (root == nullptr) {
148.             // 如果根节点为空，创建一个新节点
149.             root = make_shared<BTreeNode>(t, true);
150.             root->keys.push_back(k);
151.         } else {
152.             // 如果根节点已满
153.             if (root->keys.size() == 2 * t - 1) {
154.                 // 创建一个新根节点
155.                 auto newRoot = make_shared<BTreeNode>(t, false);
157.                 // 将旧根节点作为新根的子节点
158.                 newRoot->children.push_back(root);
160.                 // 分裂旧根节点
161.                 newRoot->splitChild(0, root);
163.                 // 插入到合适的子节点
164.                 if (k > newRoot->keys[0]) {
165.                     newRoot->children[1]->insertNonFull(k);
166.                 } else {
167.                     newRoot->children[0]->insertNonFull(k);
168.                 }
170.                 root = newRoot; // 更新根节点
171.             } else {
172.                 root->insertNonFull(k);
173.             }
174.         }
175.     }
176. };
178. // 主函数
179. int main() {
180.     // 创建 B 树
181.     BTree tree(T);
183.     // 插入一些数据
184.     tree.insert(10);
185.     tree.insert(20);
186.     tree.insert(5);
187.     tree.insert(6);
188.     tree.insert(12);
189.     tree.insert(30);
190.     tree.insert(7);
191.     tree.insert(17);
193.     // 遍历 B 树
194.     cout << "Traversal of the B-Tree:\n";
195.     tree.traverse();
196.     cout << endl;
198.     // 搜索键值
199.     int key = 6;
200.     cout << "Searching for key " << key << " in the B-Tree..." << endl;
201.     auto result = tree.search(key);
202.     if (result != nullptr) {
203.         cout << "Key " << key << " found in the B-Tree.\n";
204.     } else {
205.         cout << "Key " << key << " not found in the B-Tree.\n";
206.     }
208.     return 0;
209. }

复制代码

  CPP版本b树

  

• 数据结构设计：
  
  
  
  • BTreeNode 类表现 B 树的节点，包罗键值数组 (keys) 和子节点指针数组 (children)。
    
  • BTree 类表现 B 树，封装了树的根节点和相干操纵。
    
  
  
• 核心操纵：
  
  
  
  • 创建节点：通过构造函数动态创建新节点。
    
  • 插入：
    
    
    
    • 假如根节点已满，会创建一个新根节点并分裂旧根。
      
    • 插入操纵通过递归调整子节点，确保 B 树的平衡性。
      
    
    
  • 查找：在节点中二分查找键值并递归到子节点。
    
  • 遍历：中序遍历全部键值。
    
  
  
• 加强结实性：
  
  
  
  • 使用 vector 自动管理数组内存，避免手动分配和释放。
    
  • 使用 shared_ptr 管理节点的生命周期，防止内存泄漏。
    
  • 异常检测和边界条件处理（如空树或满节点）。
    
  
  
• 输入输出：
  
  
  
  • 插入一组数据构建 B 树。
    
  • 遍历 B 树，输出全部键值。
    
  • 搜索指定键值，输出是否存在。
    
  
  

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <stdbool.h>
5. // 定义 B+树的最小度数 T
6. #define T 3
8. // 定义 B+树节点结构
9. typedef struct BPTreeNode {
10.     int *keys;                      // 键值数组
11.     struct BPTreeNode **children;   // 子节点指针数组
12.     int n;                          // 当前节点的键值数量
13.     bool isLeaf;                    // 是否为叶子节点
14.     struct BPTreeNode *next;        // 用于叶子节点的链表指针
15. } BPTreeNode;
17. // 创建一个新节点
18. BPTreeNode *createNode(bool isLeaf) {
19.     BPTreeNode *node = (BPTreeNode *)malloc(sizeof(BPTreeNode));
20.     if (!node) {
21.         fprintf(stderr, "Memory allocation failed for BPTreeNode.\n");
22.         exit(EXIT_FAILURE);
23.     }
25.     node->keys = (int *)malloc((2 * T - 1) * sizeof(int));
26.     node->children = (BPTreeNode **)malloc(2 * T * sizeof(BPTreeNode *));
27.     node->n = 0;
28.     node->isLeaf = isLeaf;
29.     node->next = NULL;
31.     if (!node->keys || !node->children) {
32.         fprintf(stderr, "Memory allocation failed for keys or children.\n");
33.         exit(EXIT_FAILURE);
34.     }
36.     return node;
37. }
39. // 遍历 B+树的叶子节点（范围查询）
40. void traverse(BPTreeNode *root) {
41.     if (!root) return;
43.     // 找到最左叶子节点
44.     while (!root->isLeaf) {
45.         root = root->children[0];
46.     }
48.     // 遍历所有叶子节点
49.     while (root) {
50.         for (int i = 0; i < root->n; i++) {
51.             printf("%d ", root->keys[i]);
52.         }
53.         root = root->next;
54.     }
55.     printf("\n");
56. }
58. // 搜索键值
59. BPTreeNode *search(BPTreeNode *root, int key) {
60.     if (!root) return NULL;
62.     int i = 0;
64.     // 找到键值范围
65.     while (i < root->n && key > root->keys[i]) {
66.         i++;
67.     }
69.     if (root->isLeaf) {
70.         // 如果是叶子节点，检查是否找到
71.         if (i < root->n && root->keys[i] == key) {
72.             return root;
73.         }
74.         return NULL;
75.     }
77.     // 如果不是叶子节点，递归到子节点
78.     return search(root->children[i], key);
79. }
81. // 分裂非叶子节点的子节点
82. void splitNonLeafChild(BPTreeNode *parent, int idx, BPTreeNode *child) {
83.     // 创建新节点
84.     BPTreeNode *newNode = createNode(child->isLeaf);
85.     newNode->n = T - 1;
87.     // 将后半部分的键值复制到新节点
88.     for (int i = 0; i < T - 1; i++) {
89.         newNode->keys[i] = child->keys[i + T];
90.     }
92.     // 如果不是叶子节点，将子节点指针复制到新节点
93.     if (!child->isLeaf) {
94.         for (int i = 0; i < T; i++) {
95.             newNode->children[i] = child->children[i + T];
96.         }
97.     }
99.     child->n = T - 1;
101.     // 插入新的子节点到父节点
102.     for (int i = parent->n; i >= idx + 1; i--) {
103.         parent->children[i + 1] = parent->children[i];
104.     }
105.     parent->children[idx + 1] = newNode;
107.     // 将中间键值插入到父节点
108.     for (int i = parent->n - 1; i >= idx; i--) {
109.         parent->keys[i + 1] = parent->keys[i];
110.     }
111.     parent->keys[idx] = child->keys[T - 1];
112.     parent->n++;
113. }
115. // 分裂叶子节点
116. void splitLeafChild(BPTreeNode *parent, int idx, BPTreeNode *leaf) {
117.     // 创建一个新叶子节点
118.     BPTreeNode *newLeaf = createNode(true);
119.     newLeaf->n = T - 1;
121.     // 将后半部分的键值复制到新叶子节点
122.     for (int i = 0; i < T - 1; i++) {
123.         newLeaf->keys[i] = leaf->keys[i + T - 1];
124.     }
126.     leaf->n = T - 1;
128.     // 设置叶子节点的链表指针
129.     newLeaf->next = leaf->next;
130.     leaf->next = newLeaf;
132.     // 插入新叶子节点到父节点
133.     for (int i = parent->n; i >= idx + 1; i--) {
134.         parent->children[i + 1] = parent->children[i];
135.     }
136.     parent->children[idx + 1] = newLeaf;
138.     // 将新叶子节点的第一个键值插入到父节点
139.     for (int i = parent->n - 1; i >= idx; i--) {
140.         parent->keys[i + 1] = parent->keys[i];
141.     }
142.     parent->keys[idx] = newLeaf->keys[0];
143.     parent->n++;
144. }
146. // 插入到非满节点中
147. void insertNonFull(BPTreeNode *node, int key) {
148.     int i = node->n - 1;
150.     if (node->isLeaf) {
151.         // 找到插入位置
152.         while (i >= 0 && key < node->keys[i]) {
153.             node->keys[i + 1] = node->keys[i];
154.             i--;
155.         }
156.         node->keys[i + 1] = key;
157.         node->n++;
158.     } else {
159.         // 找到子节点位置
160.         while (i >= 0 && key < node->keys[i]) {
161.             i--;
162.         }
163.         i++;
165.         // 如果子节点已满
166.         if (node->children[i]->n == 2 * T - 1) {
167.             if (node->children[i]->isLeaf) {
168.                 splitLeafChild(node, i, node->children[i]);
169.             } else {
170.                 splitNonLeafChild(node, i, node->children[i]);
171.             }
173.             // 确定插入位置
174.             if (key > node->keys[i]) {
175.                 i++;
176.             }
177.         }
178.         insertNonFull(node->children[i], key);
179.     }
180. }
182. // 插入键值到 B+树
183. void insert(BPTreeNode **rootRef, int key) {
184.     BPTreeNode *root = *rootRef;
186.     if (!root) {
187.         // 如果根节点为空，创建一个新节点
188.         root = createNode(true);
189.         root->keys[0] = key;
190.         root->n = 1;
191.         *rootRef = root;
192.         return;
193.     }
195.     // 如果根节点已满
196.     if (root->n == 2 * T - 1) {
197.         // 创建一个新根节点
198.         BPTreeNode *newRoot = createNode(false);
199.         newRoot->children[0] = root;
201.         // 分裂根节点
202.         if (root->isLeaf) {
203.             splitLeafChild(newRoot, 0, root);
204.         } else {
205.             splitNonLeafChild(newRoot, 0, root);
206.         }
208.         // 插入到新根节点的合适位置
209.         int i = (key > newRoot->keys[0]) ? 1 : 0;
210.         insertNonFull(newRoot->children[i], key);
212.         *rootRef = newRoot;
213.     } else {
214.         insertNonFull(root, key);
215.     }
216. }
218. // 释放 B+树节点
219. void freeBPTree(BPTreeNode *node) {
220.     if (!node) return;
222.     if (!node->isLeaf) {
223.         for (int i = 0; i <= node->n; i++) {
224.             freeBPTree(node->children[i]);
225.         }
226.     }
228.     free(node->keys);
229.     free(node->children);
230.     free(node);
231. }
233. // 主函数
234. int main() {
235.     BPTreeNode *root = NULL;
237.     // 插入数据
238.     insert(&root, 10);
239.     insert(&root, 20);
240.     insert(&root, 5);
241.     insert(&root, 6);
242.     insert(&root, 12);
243.     insert(&root, 30);
244.     insert(&root, 7);
245.     insert(&root, 17);
247.     // 遍历 B+树
248.     printf("Traversal of the B+ Tree:\n");
249.     traverse(root);
251.     // 搜索键值
252.     int key = 6;
253.     printf("Searching for key %d in the B+ Tree...\n", key);
254.     BPTreeNode *result = search(root, key);
255.     if (result) {
256.         printf("Key %d found in the B+ Tree.\n", key);
257.     } else {
258.         printf("Key %d not found in the B+ Tree.\n", key);
259.     }
261.     // 释放 B+树
262.     freeBPTree(root);
264.     return 0;
265. }

复制代码

  C语言版本b+树

  

• 数据结构：
  
  
  
  • BPTreeNode 表现 B+树的节点，包罗 keys、children 和 next（叶子节点链表指针）。
    
  • 支持叶子节点链表结构，优化范围查询。
    
  
  
• 主要功能：
  
  
  
  • 插入：自动处理节点分裂，支持叶子和非叶子节点分裂。
    
  • 搜索：递归搜索键值。
    
  • 遍历：从叶子节点链表输出全部键值。
    
  • 内存释放：递归释放全部节点，避免内存泄漏。
    
  
  
• 结实性：
  
  
  
  • 检查内存分配是否乐成，失败时终止步伐。
    
  • 处理空树和根节点分裂等边界情况。
    
  
  
• 测试功能：
  
  
  
  • 插入一组数据，输出全部键值。
    
  • 搜索特定键值，输出是否找到。
    
  
  

   
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。