How can I store a generic tree in a file?

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?

Solution

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;