数据结构B树c++代码

### C++ 实现 B-Tree 数据结构

B-Tree 是一种自平衡的树形数据结构，允许存储大量有序的数据项并支持高效的插入、删除和查找操作。下面是一个简单的 B-Tree 的 C++ 实现。

#### 基本定义与节点类

为了创建一个 B-Tree，首先需要定义其基本组成部分——节点。每个节点可以有多个键值以及指向子节点的指针数组：

#include <iostream>
#include <vector>

class BTreeNode {
public:
    bool leaf;
    int *keys;          // An array of keys
    BTreeNode **C;      // An array of child pointers
    int n;              // Current number of keys
    int t;              // Minimum degree (defines the range for number of keys)

    BTreeNode(int temp, bool isLeaf);
    
    void traverse();
    void insertNonFull(int k);

private:
    int findKey(int k);  
};

此部分描述了 `BTreeNode` 类成员变量及其构造函数声明[^1]。

#### 构造函数初始化

当新实例化一个 `BTreeNode` 对象时，通过构造函数来分配必要的内存空间给键值和孩子结点，并设置叶子标志位：

BTreeNode::BTreeNode(int t1, bool leaf1) {
    t = t1;
    leaf = leaf1;

    keys = new int[2*t-1];
    C = new BTreeNode *[2*t];

    n = 0;
}

这段代码展示了如何利用传入参数完成对象属性赋初值的工作。

#### 遍历方法

遍历整个 B-Tree 可以按照顺序访问所有的关键字，在这里提供了一个递归版本的方法用于展示所有元素：

void BTreeNode::traverse() {
    int i;
    for (i = 0; i < n; i++) {
        if (!leaf)
            C[i]->traverse();

        std::cout << " " << keys[i];
    }

    if (!leaf)
        C[i]->traverse();  // Print elements in last subtree
}

上述逻辑实现了先序遍历的方式打印出所有存在于当前路径上的键值。

#### 插入非满节点

对于不完全填充的关键字列表来说，可以直接在其内部找到合适位置加入新的条目而无需分裂任何现有节点:

void BTreeNode::insertNonFull(int k) {
    int i = n - 1;

    if (leaf == true) {     // If this node is a leaf node
        while (i >= 0 && keys[i] > k) {
            keys[i + 1] = keys[i];
            i--;
        }
        
        keys[i + 1] = k;
        n = n + 1;
    } else {                // Otherwise, it's an internal node.
        while (i >= 0 && keys[i] > k)
            i--;

        if (C[i + 1]->n == 2*t - 1) {       // No room to add key directly into Ci+1
            splitChild(i + 1, C[i + 1]);

            if (keys[i + 1] < k)
                i++;
        }
        C[i + 1]->insertNonFull(k);
    }
}

int BTreeNode::findKey(int k) {
    int idx = 0;
    while (idx < n && keys[idx] < k)
        ++idx;
    return idx;
}

这部分包含了处理叶节点和内节点两种情况下的具体插入流程。