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

I'm working on a b-tree (or is it BTree?) for a class I'm current taking. I have most of it implement correctly (I think). However, I'm having trouble nailing down an inorder traversal. Here's my 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' };

for (int i = 0; i < 20; i++) {
    tree->insert(entries[i]);
    cout << i << ":\t";
    tree->inorder();
    cout << endl;
}

So I'm create a 5-way btree that holds chars. I'm inserting each of the chars into the tree, and then showing the inorder traversal for each iteration for debugging purposes. This is the output I get:

0:  a
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 nearly all of them, some of the chars are duplicated, but not consistently between insertions, so it (to me) doesn't seem like duplicate data is getting in. I can't seem to make sense of it, but here's my 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)
{
    for (int i = 0; i < current->count+1; i++) {
        if (current->branch[i])
            inorder(current->branch[i]);
        if (i < order-1 && current->data[i])
            cout << current->data[i];
    }
}

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

Here's my 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 everything used to 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)
{
    for (int i = current->count; i > 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, I think we're in the same class. I just finished mine, and I saw the problem in your inorder traversal, with the new one too. In that second if:

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

it does it for the order, not for how much data is currently in the node, so it's going to spit out that little bit extra. I changed it to i<current->data and now it works just fine. ^^b Just finished up. If it doesn't work for you, sorry. ^^;

---

Your problem is that your for-loop is going from 0 to count (inclusive) but your Node::data array isn't defined at data[count] its only defined up to data[count-1] so the last iteration of your that loop always gets garbage which sometimes might be non-zero and not show up, but othertimes might be random characters.

You need to special case your code for when "i == order" like so

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