inorder traversal of a b-tree (c++) -

i'm working on b-tree (or btree?) class i'm current taking. have of implement correctly (i think). however, i'm having trouble nailing down inorder traversal. here's main function:

tree<char, 5>* tree = new tree<char, 5>();  char entries[] = {'a', 'g', 'f', 'b', 'k', 'd', 'h', 'm', 'j', 'e', 's',                    'i', 'r', 'x', 'c', 'l', 'n', 't', 'u', 'p' };  (int = 0; < 20; i++) {     tree->insert(entries[i]);     cout << << ":\t";     tree->inorder();     cout << endl; } 

so i'm create 5-way btree holds chars. i'm inserting each of chars tree, , showing inorder traversal each iteration debugging purposes. output get:

0:  1:  ag 2:  afg 3:  abfg 4:  abffgk 5:  abdgfgk 6:  abdgfghk 7:  abdgfghkm 8:  abdgfghjjkm 9:  abdefghjjkm 10: abdefghjjkms 11: abdefghimjkms 12: abdefghimjkmrs 13: abdefghimjkmrrsx 14: abccdefghimjkmrrsx 15: abccdefghimjklmsrsx 16: abccdefghimjklmnrsx 17: abccdefghimjklmnrstx 18: abccdefghimjklmnrstux 19: abccdefghimjjklmmnprstux 

in of them, of chars duplicated, not consistently between insertions, (to me) doesn't seem duplicate data getting in. can't seem make sense of it, here's inorder method:

template <class record, int order> void tree<record, order>::inorder() {     inorder(root); }  template <class record, int order> void tree<record, order>::inorder(node<record, order> *current) {     (int = 0; < current->count+1; i++) {         if (current->branch[i])             inorder(current->branch[i]);         if (i < order-1 && current->data[i])             cout << current->data[i];     } } 

in node implementation, count number of 'data' (each char) in tree. count+1 how many branches come off node non-leaf nodes. branch array of next lower set of nodes, data array of chars.

here's node implementation:

template <class record, int order> struct node {     int count;     record data[order - 1];     node<record, order>* branch[order];     node() : count(0) {} }; 

here's used insert:

template <class record, int order> errorcode tree<record, order>::insert(const record& new_entry) {     record median;     node<record, order> *right_branch, *new_root;     errorcode result = push_down(root, new_entry, median, right_branch);      if (result == overflow) {         new_root = new node<record, order>();         new_root->count = 1;         new_root->data[0] = median;         new_root->branch[0] = root;         new_root->branch[1] = right_branch;         root = new_root;         result = success;     }      return result; }  template <class record, int order> errorcode tree<record, order>::push_down(                 node<record, order> *current,                 const record &new_entry,                 record &median,                 node<record, order> *&right_branch) {     errorcode result;     int position;      if (current == null) {         median = new_entry;         right_branch = null;         result = overflow;     }     else {         if (search_node(current, new_entry, position) == success)             result = duplicate_error;         else {             record extra_entry;             node<record, order> *extra_branch;             result = push_down(current->branch[position], new_entry,                                  extra_entry, extra_branch);             if (result == overflow) {                 if (current->count < order - 1) {                     result = success;                     push_in(current, extra_entry, extra_branch, position);                 }                 else                     split_node(current, extra_entry, extra_branch, position,                                  right_branch, median);             }         }     }      return result; }  template <class record, int order> void tree<record, order>::push_in(node<record, order> *current,                  const record &entry,                 node<record, order> *right_branch,                 int position) {     (int = current->count; > position; i--) {         current->data[i] = current->data[i-1];         current->branch[i+1] = current->branch[i];     }      current->data[position] = entry;     current->branch[position+1] = right_branch;     current->count++; } 

heh, think we're in same class. finished mine, , saw problem in inorder traversal, new 1 too. in second if:

if (i < order-1 && current->data[i]) cout << current->data[i]; 

it order, not how data in node, it's going spit out little bit extra. changed i<current->data , works fine. ^^b finished up. if doesn't work you, sorry. ^^;