Saving a general tree to a flat file

I am parsing a tagged file and creating a tree structure if it. This tree is unordered and each node can have any number of child nodes. I need to use this tree often and do not want to parse and construct the tree each time. Is it possible to save the entire tree to a disk such that we can easily reconstruct it from the disk when needed ? C/C++ Code would greatly help. I have access to STL too.
tellis_georgeAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
RuskConnect With a Mentor Commented:
I will try to expand the pseodo-code I gave in my old comment
say you choose "up" as your delimiter
(its not wise to actually choose that)

bool Place(ifstream& File,Node* Root)
{string Temp="";
 File>>Temp;
 Node* NextChild;
 if (Temp=="up") return false;
 Root->data=Temp;
 while (true)
 {NextChild=new Node;
  if (Place(File,NextChild))
   Root->linkList.push(NextChild);
  else
  {delete NextChild;
   return false;
  }
 }  
 return true;
}
I think this is a good starting point but there are couple things to think about (I did not test this and I probably has errors, this is just to demostrate what I explained)

* I assume the string class you use
has == and = operators;
* I assume your linklist has a push function.

as I said in my old comment the write function would be very similar.
 I will be on for a couple hours ask me anything I have left unclear. And try to post the actual code so that we can see how to implement this if what I assumed was wrong.
0
 
PacmanCommented:
my suggestion:

walk through the tree and write it node for node to the file.
Link the nodes in the file by saving their filepositions.
0
 
tellis_georgeAuthor Commented:
Hi Pacman, Walking thro the tree and recording each node is OK, but I am not too clear on the second point of saving file positions ???
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
tellis_georgeAuthor Commented:
Hi Pacman, Walking thro the tree and recording each node is OK, but I am not too clear on the second point of saving file positions ???
0
 
KangaRooCommented:
The exact details depend on the nodes, but this is the general idea. Its a bit simpler then 'reconstructing' the tree in the file as pacman suggested.

class Node
{
   void write(file)
   {
      // write this nodes data
      write(file, somedatamembers);
      // for each of its children:
      child->write(file);
   }
   void read(file)
   {
      read(file, somedatamembers);
      while(there are children written in the file)
         new_child->read(file);
   }
}

One such 'detail' is a way to delimit the list of children, which is left open in the example.
0
 
tellis_georgeAuthor Commented:
Could you explain in some more detail assuming each node is a simple structure with a data field, and a series of link fields.
0
 
PacmanCommented:
tellis george,

you want to do it with procedures ?
Then just code your WiteNode() and ReadNode() function:

WriteNode (file, node)
{
      write(file, node)
      for each child:
          WriteNode (file, child);
}

ReadNode( ... )
{
     // like WriteNode()
}


0
 
tellis_georgeAuthor Commented:
I was reading it up and learnt that to reconstruct the tree exactly as it was in memory we need to traverse the tree in some fashion (inorder traversal) and mark the nodes with "keys". We then traverse these nodes again in the inorder fashion to write the nodes to file along with with these keys... and we can then reconstruct the tree when needed using these keys. But this method holds good gor unordered binary trees, mine is a general tree (any number of child nodes) so the problem gets more complicated.
In the solutions given above I am not sure how the tree structure will be maintained when reconstructed....
0
 
KangaRooCommented:
Is the number of links fixed?
#define NODE_NO_LINKS
class Node
{
   Node links[NODE_NO_LINKS];
   DataType data;
   public:
      // stuff

   void write(FILE* file);
   {
     write(file, data); // or whatever writes datatype to file
     for(int i = 0; i < NODE_NO_LINKS;++i)
        links[i].write(file);
   }

  void read(FILE* file)
     read(file, data); // or whatever reads datatype from file
     for(int i = 0; i < NODE_NO_LINKS;++i)
        links[i].read(file);
   }

};

Maybe it is better if you give the declaration of your Node. What type of files, C style FILE* or C++ iostreams do you want to use? Should the node use operator<<?
0
 
KangaRooCommented:
And how do they vary. Is the number of children fixed for all the nodes of one specific tree or can it vary from node to node? Does a node 'know' exactly how many children it has, ie can we do something like
   for(i = 0; i < GetChildCount(); ++i)...
or more like
   while(!EndOfChildren())...

If the number of children is known we can write this in the file, just before we start writing the children. If not we need some way of making the beginning and end of the list of children in the file.
0
 
abstractionCommented:
Just an idea.. see if it works.. if the tree is something like below :

                A
             |    |
            B    C
           | |
          D E
 
store it as
<HEADING DELIMITER>
1,1,<info of node A> <some delimiter>  2,1,<info of node B> <some delimiter>  2,2,<info of node C>
2,1,<info of node B> <some delimiter>  2,2,<info of node C>, etc.
<DELIMTER END>

Immediately after the information about all the nodes, you store the relations between the nodes. So, each entry can be something like 1,1|2,1 <some delimter> 1,1 | 2,2. etc.
 


     Hope you got the general idea. I was trying to say that first of all you can store the nodes with an additional prefix that identifies the node's position. Next you store the relations between the nodes. So, when you read the tree from the file, you will fill your array / linked list (whatever data structure) accordingly and then fill in the relations.
           Hope I'm able to help you.
0
 
tellis_georgeAuthor Commented:
Answers from Kangaroo do not allow proper re-construction.
The comment by "abstraction" appears promising but there is some amount of data redundancy in it. Also how exactly do we traverse the tree while reading and writing ? Recursively ?
Also the tree can be anyway
Ex
                  A
                / | \
               B  C  D
              /|  | /|\
             E F  GH I J
I need to reconstruct the tree exactly as above from the file.
0
 
tellis_georgeAuthor Commented:
OZO, I did not see any useful info in the link. The page was dealing with "XDR: External Data Representation Standard" which was a totally different topic
0
 
RuskCommented:
For this tree
                  A
                / | \
               B  C  D
              /|  | /|\
             E F  GH I J

The pre-order file would be like this:
A/B/E/o/F/o/o/C/G/o/o/D/H/o/I/o/J/o/o/o

the 'o's mean that the following node is the child of the parent(sibling)
so for each time you encounter an 'o'
just go up one level.

you can implement this recursively

briefly how to read:
Next is the next item on disk

Place(Root)
{while (Next!=o)
 {Root=Next
  Place(Root->Nextchild)
 }
 return
}
Writing would be really similar
it is hard to say w/o knowing the exact tree implementation
0
 
ozoCommented:
XDR can portably save a tree in a flat file using Optional-data (3.18)
(You could also store it in ASCII, in the same format as a C initializer for the data, which would be even more portable, but more work to generate)
0
 
tellis_georgeAuthor Commented:
I am trying to implement Rusk's code. I'll get back as soon as I know the results.
0
 
tellis_georgeAuthor Commented:
Rusk, The solution you provided appears like it will work just fine.
It will be great if you could provide some sample read/write code in C/C++ as I'm pretty new here.
The node is a structure
structure
{
string data;
linkList NodePtr(each list element in this linklist points to a node structure)
} node

Each node is as shown

[data][L1]-[L2]-[L3]
        |    
     [data]-[L1]
              |    
            [data]-[L1]


0
 
KangaRooCommented:
It doesn't matter how the tree looks, it would be reconstructed exactly the same. Redundancy can be avoided, but if there is redundancy you'r not writing a tree but a graph. You are pretty late with information on your node.
0
 
tellis_georgeAuthor Commented:
Thanks everyone for the help....
0
All Courses

From novice to tech pro — start learning today.