C++怎么实现一个简单的B树_C++数据结构与B树实现方法

template <typename T, int t>
class BTreeNode {
public:
    bool leaf;
    int n; // 当前关键字数量
    T keys[2*t - 1]; // 关键字数组
    BTreeNode* children[2*t]; // 子节点指针
<pre class='brush:php;toolbar:false;'>BTreeNode() : leaf(true), n(0) {
    for (int i = 0; i < 2*t; ++i)
        children[i] = nullptr;
}

void traverse();
int findKey(T k);
void insertNonFull(T k);
void splitChild(int i, BTreeNode* y);
bool search(T k);

template <typename T, int t>
class BTree {
public:
    BTreeNode<T, t>* root;
    void insert(T k);
    bool search(T k) { return root ? root->search(k) : false; }
};
<p>template <typename T, int t>
void BTree<T, t>::insert(T k) {
if (!root) {
root = new BTreeNode<T, t>();
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2<em>t - 1) {
BTreeNode<T, t></em> s = new BTreeNode<T, t>();
s->leaf = false;
s->children[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k) i++;
s->children[i]->insertNonFull(k);
root = s;
} else {
root->insertNonFull(k);
}
}
}</p>

template <typename T, int t>
bool BTreeNode<T, t>::search(T k) {
    int i = 0;
    while (i < n && k > keys[i])
        i++;
<pre class='brush:php;toolbar:false;'>if (keys[i] == k)
    return true;

if (leaf)
    return false;

return children[i]->search(k);