Inorder traversal of a b-tree (c++)?

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.

Up vote 0 down vote favorite share g+ share fb share tw.

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* tree = new Tree(); 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 insert(entriesi); cout inorder(); cout void Tree::inorder() { inorder(root); } template void Tree::inorder(Node *current) { for (int I = 0; I count+1; i++) { if (current->branchi) inorder(current->branchi); if (i datai) cout datai; } } 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 struct Node { int count; Record dataorder - 1; Node* branchorder; Node() : count(0) {} }; Here's everything used to insert: template ErrorCode Tree::insert(const Record& new_entry) { Record median; Node *right_branch, *new_root; ErrorCode result = push_down(root, new_entry, median, right_branch); if (result == overflow) { new_root = new Node(); new_root->count = 1; new_root->data0 = median; new_root->branch0 = root; new_root->branch1 = right_branch; root = new_root; result = success; } return result; } template ErrorCode Tree::push_down( Node *current, const Record &new_entry, Record &median, Node *&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 *extra_branch; result = push_down(current->branchposition, new_entry, extra_entry, extra_branch); if (result == overflow) { if (current->count void Tree::push_in(Node *current, const Record &entry, Node *right_branch, int position) { for (int I = current->count; I > position; i--) { current->datai = current->datai-1; current->branchi+1 = current->branchi; } current->dataposition = entry; current->branchposition+1 = right_branch; current->count++; } c++ traversal b-tree link|improve this question edited Dec 2 '10 at 17:47 asked Dec 2 '10 at 4:16greggory. Hz623316 93% accept rate.

Please show us the Node data structure - I don't understand why branch is apparently count + 1 elements long. Showing the structure is clearer than trying to describe it. Also, what does the 'order' template parameter control?

– Karl Knechtel Dec 2 '10 at 4:22 the order template parameter controls what order of a tree we're working with. In this case, a 5-way tree (Tree* tree = new Tree). Adding node now .... – greggory.

Hz Dec 2 '10 at 4:28 @greggory. Hz can you clarify what 'count' means? Is it the number of branches which have been added?

Or the number of 'data' elements? Or something else? I think there might be a bug with how count is used but its hard to tell without knowing how 'insert' uses it.

– MerickOWA Dec 2 '10 at 4:54 @greggory. Hz can you provide the code for insert (if its not too big) I think the second bug something to do with 'count' and your for-loop – MerickOWA Dec 2 '10 at 5:08 It's kind of a lot, but I've added the insert code – greggory. Hz Dec 2 '10 at 5:18.

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 datai) cout datai; 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 idata and now it works just fine. ^^b Just finished up. If it doesn't work for you, sorry.

So with I data, I get a compiler error ... since I is an int and current->data is a pointer (array). However, you pointed me in the correct direction. I changed it to I count and it worked perfectly!

Thanks for the help :) (maybe edit your answer to reflect the change I made) – greggory. Hz Dec 3 '10 at 19:59.

Your problem is that your for-loop is going from 0 to count (inclusive) but your Node::data array isn't defined at datacount its only defined up to datacount-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->branchi) inorder(current->branchi); if (i datai) cout datai.

If I take the +1 out of the for loop condition, it doesn't always print all the chars. In iteration 4, I get 'abf' and in iteration 19 I get 'abcdefj' for example. Most (not all) of the other iterations are similarly short, but those two are the easiest to stop at a glance.

– greggory. Hz Dec 2 '10 at 4:38 1 @greggory. Hz Your code for inorder is assuming that it can use 'i' to access both the branch array and the data array, so when count = 4 you'll access an invalid location in data but you'll have a valid branch location.

– MerickOWA Dec 2 '10 at 4:43 @greggory. Hz Try the updated code – MerickOWA Dec 2 '10 at 4:46 I see what you're saying now! Thanks for that snippet.

That got rid of the errant 0s. However I still have the repeated chars problem. (updating question as well) – greggory.

Hz Dec 2 '10 at 5:04.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.