By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,412 Members | 917 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,412 IT Pros & Developers. It's quick & easy.

urgent, please help

P: 4
hey guys,

how do u Perform an inorder traversal of the Btree and as each node is visited its key is inserted sequentially into an array of ints
it would be great if u have some code to explain

thanks
Sep 28 '06 #1
Share this Question
Share on Google+
3 Replies


P: 4
hey banafa

i see that u help everyone please help me i really need ur help if u can evrytime i ask for help noone get back to my msgs

how do u Perform an inorder traversal of the Btree and as each node is visited its key is inserted sequentially into an array of ints
it would be great if u have some code to explain

if my question isnt clear plz let me know

thanks
Sep 28 '06 #2

Banfa
Expert Mod 5K+
P: 8,916
Please don't double post.

I know little about BTrees but this site look useful

http://www.bluerwhite.org/btree/
Sep 28 '06 #3

100+
P: 293
D_C
In order traversal prints left child, node, right child. I think you want level order traversal, which prints nodes from left to right in order of increasing depth.

1. Make an array, say key[], (which holds they key you want to print) large enough to hold all elements.
2. Traverse the B-tree by some other method, such as In order traversal.
3. Each time you come across a node, place it's key value into the array at index idx. The following relations will help you calculate a key's index:

idx(root) = 0.
idx(left child) = 2*idx(node)
idx(right child) = 2*idx(node)+1

4. After the array is populated, iterate through the array entries in increasing order.

If the key that you stored in the array can take any value, you have no idea of knowing whether you placed a node into to the array or not. In that case, make a boolean array, say valid[], the same size as your other array. Initialize all it's entries to false, and set valid[idx] = true when you set key[index] = value.
Sep 28 '06 #4

Post your reply

Sign in to post your reply or Sign up for a free account.