如何正确遍历B树？请求修正preordertraverse()函数的技术支持

我实现了一个阶数为3的B树，插入若干节点后，中序遍历结果为升序，符合预期，但前序遍历结果不符合预期。请帮忙修正preordertraverse()函数。

class bnode
{
    int *keys;  
    int t;      
    bnode **C; 
    int n;     
    bool leaf; 

public:
    bnode(int _t, bool _leaf);  
    void inordertraverse(); 
    void preordertraverse(); 
    void insnoful(int k);
    void spchild(int i, bnode *y);
    void insert(int k);
    
    friend class btree;
};

class btree
{
    bnode *root; 
    int t; 
public:
    btree(int _t)
    {
        root = NULL;
        t = _t;
    }

    void inordertraverse()
    {
        if (root != NULL) root->inordertraverse();
    }

    void preordertraverse()
    {
        if (root != NULL) root->preordertraverse();
    }

    void insert(int k);
};

bnode::bnode(int t1, bool leaf1)
{
    t = t1;
    leaf = leaf1;
    keys = new int[2*t-1];
    C = new bnode *[2*t];
    n = 0;
}

void btree::insert(int k)
{
    if (root == NULL)
    {
        root = new bnode(t, true);
        root->keys[0] = k;  
        root->n = 1;
    }
    else 
    {
        if (root->n == 2*t-1)
        {
            bnode *s = new bnode(t, false);
            s->C[0] = root;
            s->spchild(0, root);
            int i = 0;
            if (s->keys[0] < k)
                i++;
            s->C[i]->insnoful(k);
            root = s;
        }
        else  
            root->insnoful(k);
    }
}

void bnode::insnoful(int k)
{
    int i = n-1;
    if (leaf == true)
    {
        while (i >= 0 && keys[i] > k)
        {
            keys[i+1] = keys[i];
            i--;
        }
        keys[i+1] = k;
        n = n+1;
    }
    else 
    {
        while (i >= 0 && keys[i] > k)
            i--;
        if (C[i+1]->n == 2*t-1)
        {
            spchild(i+1, C[i+1]);
            if (keys[i+1] < k)
                i++;
        }
        C[i+1]->insnoful(k);
    }
}

void bnode::spchild(int i, bnode *y)
{
    bnode *z = new bnode(y->t, y->leaf);
    z->n = t - 1;
    for (int j = 0; j < t-1; j++)
        z->keys[j] = y->keys[j+t];
    if (y->leaf == false)
    {
        for (int j = 0; j < t; j++)
            z->C[j] = y->C[j+t];
    }
    y->n = t - 1;

    for (int j = n; j >= i+1; j--)
        C[j+1] = C[j];
    C[i+1] = z;
    for (int j = n-1; j >= i; j--)
        keys[j+1] = keys[j];
    keys[i] = y->keys[t-1];
    n = n + 1;
}

void bnode::inordertraverse()
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (leaf == false)
            C[i]->inordertraverse();
        cout << " " << keys[i];
    }
    if (leaf == false)
        C[i]->inordertraverse();
}

void bnode::preordertraverse()
{
    int i;
    for (i = 0; i < n; i++)     
    {
        cout << " " << keys[i];
        if (leaf == false)          
            C[i]->preordertraverse();       
    }

    if (leaf == false)      
        C[i]->preordertraverse();
} 

int main()
{
    btree t(3); 

    t.insert(128);
    t.insert(92);
    t.insert(48);
    t.insert(72);
    t.insert(115);
    t.insert(85);
    t.insert(1);
    t.insert(101);
    t.insert(111);
    t.insert(53);
    t.insert(193);
    t.insert(189);
    t.insert(75);
    t.insert(129);
    t.insert(119);
    cout<<"inorder traversal of btree";
    cout << endl;
    t.inordertraverse();
    cout << endl;
    cout<<"preorder traversal of btree";
    cout << endl;
    t.preordertraverse(); 

    return 0;
}

问题分析 #

当前preordertraverse()函数的逻辑是输出单个关键字后立即遍历对应子节点，这种方式不符合标准B树前序遍历的定义。标准前序遍历的规则是：

1. 先访问当前节点的所有关键字
2. 再按顺序递归遍历每个子节点

当前代码的遍历顺序会将父节点的单个关键字与子树结果穿插，导致输出顺序不符合预期。

修正后的函数 #

void bnode::preordertraverse()
{
    // 第一步：输出当前节点的所有关键字
    for (int i = 0; i < n; i++)
    {
        cout << " " << keys[i];
    }
    // 第二步：递归遍历所有子节点
    if (!leaf)
    {
        for (int i = 0; i <= n; i++)
        {
            C[i]->preordertraverse();
        }
    }
}

修正效果 #

修正后，前序遍历会先输出当前节点的所有关键字，再依次遍历每个子节点，符合标准前序遍历定义。针对测试用例，修正后的前序输出为：
53 92 115 129 1 48 72 75 85 101 111 119 128 189 193

内容的提问来源于stack exchange，提问作者cppbeginer