How can I store a generic tree in a file?

Question

I have a generic tree implementation written in C++ that can store any type (int, float, string, etc.)

template<class T> class Tree {
public:
// Class interface
private:
T node;
std::list<Tree<T>*>* children;
};

and I have a program (written in C++) that take as input a source tree and give in output another tree based on a set of rules (stored in a file).

Any instance of class A become an instance of class X
Any instance of class B become an instance of class Y
Any instance of class C become an instance of class Z

For example, suppose I have this input tree A(B(C)) (the node A has B as child and B has C as child). Based on the file of rule my program give me this tree X(Y(Z)). My question is: How can I save in a file the set of rules? How can I store the tree type in this file? I'm thinking to use XML for store the rules, like this

<translationUnit>
  <from>
    <A>
      <B>
        <C></C>
      </B>
    </A>
  </from>
  <to>
    <X>
      <Y>
        <Z></Z>
      </Y>
    </X>
  <to>
</translationUnit>

but how can I store the class type?

Answer 1

For each value in your tree you should associate a type. So each elements in the tree is a pair of the type of the value and the value and a list of children. In your file you have to store this information for each node.

You can consider json to do store the serialized version of your tree, it's easy to read and a lot of good c++ library exist. For instance, the input tree will be :

{ 
     type: "A",
     value: "value of the first node,
     children: [
         {
             type: "B"
             value: "a value ...",
             children: [
                  {
                      type: "C",
                      value: "a value ...",
                  }
             ]
         }
     ]
}

your result will become:

{ 
     type: "X",
     value: "value of the first node,
     children: [
         {
             type: "Y"
             value: "a value ...",
             children: [
                  {
                      type: "Z",
                      value: "a value ...",
                  }
             ]
         }
     ]
}

and in your configuration file you can store each type transformation:

[
     { from: "A", to: "X" },  
     { from: "B", to: "Y" },
     { from: "C", to: "Z" }
]

If you want to store a children of type B inside a Tree of type A, with you interface, A and B should share a base type and you should use pointers to store your node member. If you don't want to manage it manually use a unique_ptr :

unique_ptr<T> node;

After that, you have a pointer to a list of pointer to trees, it's a lot of pointer to manage, if you want to avoid a pointer to a list, you can use boost::container::list which allow containers of incomplete type. After that, you don't need to have a pointer to a tree stored in the list, a Tree value will do the job.

boost::container::list<Tree<T> > children;

Answer 2

I guess you use pointers for relation between nodes. something like:

class node{
 int value;
 node* first_child;
 node* next_sibling;
};

you can create serialize node with indexes instead of pointers. something like:

class node2{
     int value;
     int id_first_child;
     int id_next_sibling;
};

Now you can flat the tree. means turn it into array.

add all nodes pointers to a vector<node*>, and to a map<node*,int> the map used to translate pointer to the index in the vector.

now write the nodes to the file with indexes instead of pointers.

when you read from the file you need to do it opposite, and translate the indexes to pointers.