How can I correctly traverse a tree?

Question

The following code inserts some nodes in a tree and displays the inorder and preorder traversals of the same tree. The inorder traversal seems to be right because the nodes are arranged in an ascending order. The preorder traversal is not right. Would you please give some pieces of advice or help in order to correct the pretraverse() function?

 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;
 }

Answer 1

In a preorder traversal, the keys of a node are all output before any of the children keys. Yet your code mixes the output of parent keys with child keys in the following method (I fix the indentation):

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();         
} 

The output should be split into two phases: one for outputting the current node's keys, and one for doing the same recursively for the children:

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

Now the output for your example will be:

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

which corresponds to the shape that this B tree has: