On disk Binary tree

There are several approaches to take when serializing a tree like this. If the tree is a search tree and the order of the nodes can be determined simply from the elements, then storing the tree structure wouldn''t be necessary. Just write the number of nodes to the file and then write each element one after another.

Alternately, if the structure of the tree isn''t based on the elements stored, then there are still several methods to do this. For example, you can use a text representation with prefix, postfix or infix notation to represent the tree. For example, with prefix notation, you might represent a node like (element node node) or an empty node (). So the tree:

   1
  / \
 2   3
    / \
   5   4
 

Might be represented like: (1 (2 () ()) (3 (5 () ()) (4 () ()))). When reading it from the file, nodes can be built with a simple recursive function to construct each node. There are any number of variations for syntax of the representation in this case.

Another method is to just dump the entire tree to disk, one node after another including the pointers, and when you record each node, write the address of the node. When you read the nodes from disk you do a two stage process. One stage gets the raw node data from the file. The next step patches together the new tree from the old addresses.

You might want to read the C++ FAQ Lite''s section on serialization for other ideas and further details.

Tnx, i''ll study it !

Store two traversal of the tree ? how could that be helpful ?