2

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.

Improve this question
2
  • Hi, actually I'm not sure I've understood your question: are you searching for a way to "disassemble" an arbitrary struct (with an arbitrary set of members of arbitrary types) into the node of a tree? I mean: setting up a generic node class (or struct, if you prefer) is not a problem, but creating the functions to "fill" it is more complicated, at least you could think about all your structs to be children of an ancestor with some "introspection enabling" method, if you don't want to mess up too much with the code... Commented Jul 26, 2013 at 9:05
  • Basically, I want to have different struct (or class) written to different branches of the tree, so that it becomes easy for me to read or update them. Taking from the example above, "daughter" might get a struct of {int, float, char} and so on.. Having a common generic class looks simple, but every time I want to update, I will read and write extra variables as well. Just wanted to know if this is possible anyway, else will go with a generic class. Commented Jul 26, 2013 at 9:16

3 Answers 3

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

There is no hard n fast rule that I need to go with structs. I'll try with some kind of variant class.
0 
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;
}
Improve this answer

2 Comments

The problem with this solution lies in the fact that I cannot have different structs for different nodes. Basically, I want to create child nodes based on number of variables in the struct, and the struct will be different for different branches.
Ah, so this is what you ment by changes in the struct :) You can always use a void* pointer to store different types in each node. I would then also recommend a marker in which you can store the datatype... for instance a char type and 'c' for char 'i' for int, 'd' for double and some value sof your own for different struct types.
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.