[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

Re: saving binary tree to file

On Thu, 30 Nov 2000, Arun Sharma wrote:
> You can't construct a binary tree from it's pre-order traversal sequence.
> You can construct a balanced binary tree with the same data, but some
> information about the original structure is lost.
> 	-Arun

  ummm ....if I store the information if the node owns a child or not, it
should be possible to get the structure back. For example

                                /   \
                               B      C
                                    /   \
                                   D     E

This will be stored in the file as A,B,C,D,E

now first i encounter node A i note that it has 2 children so i create a
list showing that list0=YY. The next B and C I attach to A.

while reading B i note it does not have any children so i create a list
indicating that list1 = NN. At C, I notice it has the same
level as B and has 2 children. So i append to the list 2 y's. Now 
              list1 =NNYY.

I start with the next level. list1[0]=N therefore i attach NULL to B same
with list1[1]=N. Next since the entries are YY i attach the next 2 nodes D
and E to C.
  For this i have to maintain a hierarchy of lists and free them once
their level has been built. So this should construct the tree.

  But i was looking for short cuts. The db package has a functionality of
storing B trees. I was hoping if anyway i could use it or some other
library, cause this is quite an elemntary functionality and some tools
must exist. My understanding of "man db" especially "man btree" is on very
unstable ground. Would apreciate any help deeply