c++怎么实现一个B树_c++平衡树数据结构B树实现过程

// 拷贝后半部分关键字
for (int i = 0; i < newNode->n; ++i) {
    newNode->keys[i] = fullNode->keys[(M + 1) / 2 + i];
}

if (!fullNode->isLeaf) {
    for (int i = 0; i <= newNode->n; ++i) {
        newNode->children[i] = fullNode->children[(M + 1) / 2 + i];
    }
}

// 中间关键字上移
for (int i = parent->n; i > idx; --i) {
    parent->children[i + 1] = parent->children[i];
}
parent->children[idx + 1] = newNode;

for (int i = parent->n - 1; i >= idx; --i) {
    parent->keys[i + 1] = parent->keys[i];
}
parent->keys[idx] = fullNode->keys[(M - 1) / 2];
parent->n++;

fullNode->n = (M - 1) / 2;

if (root->n == M - 1) {
    auto newRoot = new BTreeNode<T, M>();
    newRoot->isLeaf = false;
    newRoot->children[0] = root;
    splitChild(newRoot, 0);
    root = newRoot;
}
insertNonFull(root, key);

<H3>5. 遍历与查找</H3>
<p>中序遍历输出所有元素，查找类似二叉搜索树：</p>
```cpp
template<typename T, int M>
void BTree<T, M>::traverseNode(BTreeNode<T, M>* node) {
    if (node) {
        int i = 0;
        for (; i < node->n; ++i) {
            if (!node->isLeaf) {
                traverseNode(node->children[i]);
            }
            std::cout << node->keys[i] << " ";
        }
        if (!node->isLeaf) {
            traverseNode(node->children[i]);
        }
    }
}

template<typename T, int M>
void BTree<T, M>::traverse() {
    traverseNode(root);
    std::cout << std::endl;
}

template<typename T, int M>
BTreeNode<T, M>* BTree<T, M>::search(BTreeNode<T, M>* node, const T& key) {
    int i = 0;
    while (i < node->n && key > node->keys[i]) ++i;

    if (i < node->n && key == node->keys[i]) return node;

    if (node->isLeaf) return nullptr;

    return search(node->children[i], key);
}

template<typename T, int M>
BTreeNode<T, M>* BTree<T, M>::search(const T& key) {
    return root ? search(root, key) : nullptr;
}