Construct a tree(non-binary) structure from an unknown struct C++

Question

I need to dynamically add child nodes to a particular branch of a tree, according to the structure passed to me. For example, I have a structure like this :

  struct my_struct
  {
  int a;
  int b;
  char c;
  }

In my function, after moving to the node required, I should be able to add child nodes to the particular node, something like this :

                  root
                   |
      son------daughter----another_son
       |
   a---b--c

My tree Node structure is as below :

struct tree{
   string name;
   int child_count;
   int value;
   vector< tree* > child;
};

Since I want to update each of these variables later, I want separate out the nodes for each variable in the structure. Since the structure can be updated without my knowledge, I want the logic to be structure independent.

Answer 1

Use a data type

struct data {
   string name;
   my_struct structure;
   int sonc;
};

And define your tree generically.

---

Now I suggest using Boost Containers, so you can just create a vector/list/deqeue of incomplete type:

template <typename Data>
struct node
{
    Data _data;
    boost::deque<node> _children;
};

Or, if you favour inheritance, this could be valid as well:

template <typename Data>
struct node : public Data
{
    boost::deque<node> _children;
};

This saves you from all the trouble of manual allocation management.

Alternatively you can use std::unique_ptr<node> to save yourself from doing the memory management manually (hint: it's hard to get right. Think of exception safety, self-assignment, cycles)

Or even, using boost::variant:

typedef boost::make_recursive_variant<data, std::vector<boost::recursive_variant_> >::type tree;

What convenes you most will depend on the application.

Answer 2

Well, I can suggest an approach, without going too deep into details. I would setup something similar to the below code. Basically there is a generic struct which allows some sort of simplified introspection, by redefining the two pure virtual methods in the substructs, the algorithm will be able to "tree-ify" the structs into child nodes. At the end you will find an example of tree "navigation". Well, this is just a very quick example, by no means it can be considered exhaustive, you will notice that it doesn't implements any kind of tree recursion for more complex structures. Anyway, I don't know the reason for choosing structs instead of classes to handle all of this. Think about it!

#include <vector>
#include <string>
#include <iostream>

// Allowed data types
enum MyTypes {
    INT,
    DOUBLE,
    NODATA
};

// Base source struct
struct MyBaseStruct {
    std::vector <std::string> ids;
    virtual MyTypes getType(std::string id) = 0;
    virtual void *getPointer(std::string id) = 0;
};

// Example of used struct
struct MyStructA: MyBaseStruct {
    int a;
    double b;
    MyStructA();
    MyTypes getType(std::string id);
    void *getPointer(std::string id);
};

MyStructA::MyStructA()
{
    ids.push_back("a");
    ids.push_back("b");
}

MyTypes MyStructA::getType(std::string id)
{
    if (id == "a")
        return INT;
    else if (id == "b")
        return DOUBLE;
    return NODATA;
}

void *MyStructA::getPointer(std::string id)
{
    if (id == "a")
        return static_cast <void *> (&a);
    else if (id == "b")
        return static_cast <void *> (&b);
    return 0;
}

struct MyTreeNode {
    std::string id;
    MyTypes type;
    void *pointer;
    std::vector <MyTreeNode *> children;
    void addChildren(MyBaseStruct &data);
};

void MyTreeNode::addChildren(MyBaseStruct &data)
{
    std::vector <std::string>::const_iterator i(data.ids.cbegin());
    while (i != data.ids.cend()) {
        MyTreeNode *newNode= new MyTreeNode;
        newNode->id= (*i);
        newNode->type= data.getType(*i);
        newNode->pointer= data.getPointer(*i);
        children.push_back(newNode);
        i++;
    }
}

int main(int /*argc*/, char * /*argv[]*/)
{
    MyStructA a;
    a.a= 1;
    a.b= 12.34;

    MyTreeNode treeRoot;
    treeRoot.id= "root of my tree";
    treeRoot.type= NODATA;
    treeRoot.pointer= 0;
    treeRoot.addChildren(a);

    // Example of tree navigation
    std::vector <MyTreeNode *>::const_iterator i(treeRoot.children.cbegin());
    while (i != treeRoot.children.cend()) {
        std::cout << (*i)->id << ": ";
        if ((*i)->pointer) {
            if ((*i)->type == INT) {
                std::cout << *(static_cast <int *> ((*i)->pointer)) << "\n";
            }
            if ((*i)->type == DOUBLE) {
                std::cout << *(static_cast <double *> ((*i)->pointer)) << "\n";
            }
        }
        i++;
    }
}

If you have time, you can also consider writing a sort of variant class to handle different kind of data types and avoid the need for having to cast your values in multiple places.

Answer 3

struct tree{
   string name;
   my_struct structure;
   int sonc;
   vector< tree* > child;
};

I would recommend, that you use Node as a structure name for a tree node (those, which asseble a tree) and use terms like "parent" and "child" for nodes in a tree at different depths.

BTW, if you wish to traverse tree-upward i recommend adding another pointer which points to the node's parent.

Then write a function in wich you have a Node(tree) as a paramether to which you add children...

Like so:

addToTree(tree node, other parameters, like struct...)
{
    tree newNode = new tree();
    //do what you want with the new node...

    node.children.add(newNode);
    node.sonc++;
    newNode.Parent = node;
}