store binary search tree in file and read it without recreating the nodes

[hitro456]

Hi All,

I have a binary search tree (consider following structure).

struct bst
{
  void *value;
  struct bst *left, *right;
};  

I want to save this unbalanced binary search tree in a file. And when I read this file, I don't want to recreate the tree from these nodes. So the tree has to be saved in tree format, Any Ideas?? I am newbie in C language so a code snippet would be helpful...and is it possible to save this tree in binary format??

thanx in advance

[deceptikon]

Sorry, but it doesn't work like that. All of the links in your tree are pointers to the memory of your current process. If you save those pointer values, they'll be meaningless when read by another proces. Really the best you can do is save the tree's data in a way that's convenient for reconstructing it.

[rubberman]

Deceptikon is correct. One method to do this is to have a correlary to the in-memory tree for the on-disc version. For your case, it might look like this:

struct disc_bst
{
    size_t offsetofleft;
    size_t offsetofright;
    size_t sizeofvalue;
    unsigned char[] valuedata;
    /* Some compilers will require the above array to be declared as unsigned char[0]. */
};

In your code, when you map from the in-memory tree to disc, you will convert each node, as you write it, to one of the disc_bst structures, allocating the structure dynamically to hold the entire contents of the value element, setting the sizeofvalue to the actual size of value, computing the size of the left and right elements (including the size of their value data) so you can set their offsets in disc_bst, which is where they will be found relative to the top of the data file. Then you go to left and right and do all of this all over again... All this time, you need to keep track of the current size of the file. :-)

As you can tell, this is not simple. Of course, you could use a memory-mapped file for your tree so you don't need to go through all of this stuff, but that has a lot of other challenges to get it "right"... (more smileys here).

Welcome to software engineering 101!