如何正确遍历b树？

Question

以下代码在 B 树中插入一些节点，并显示同一 B 树的中序和先序遍历。中序遍历似乎是正确的，因为节点是按升序排列的。前序遍历不对。您能否提供一些建议或帮助来纠正 preordertraverse() 函数？

代码输出：

btree的中序遍历：

1 48 53 72 75 85 92 101 111 115 119 128 129 189 193

btree的前序遍历：

53 1 48 92 72 75 85 115 101 111 119 128 129 189 193

 #include<iostream>
 using namespace std;

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

 public:

 btreenode(int _t, bool _leaf);  
 void inordertraverse(); 
 void preordertraverse(); 
 void insertnonfull(int k);
 void splitchild(int i, btreenode *y);
 void insert(int k);

 friend class btree;
 };

 class btree
 {
 btreenode *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);
 };

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

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

 void btreenode::insertnonfull(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)
    {
        splitchild(i+1, C[i+1]);
        if (keys[i+1] < k)
            i++;
    }
    C[i+1]->insertnonfull(k);
 }
 }

 void btreenode::splitchild(int i, btreenode *y)
 {
 btreenode *z = new btreenode(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 btreenode::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 btreenode::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;
}

Answer 1

在前序遍历中，节点的键都在任何子键之前输出。然而，您的代码通过以下方法将父键与子键的输出混合在一起（我修复了缩进）：

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

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

输出应分为两个阶段：一阶段用于输出当前节点的键，一阶段用于递归地为子节点执行相同的操作：

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

现在示例的输出将是：

53 92 115 1 48 72 75 85 101 111 119 128 129 189 193

这似乎是正确的，因为 B 树具有以下形状：