CODEWITHSUNDEEP
c++data-structures
Kevin
Kevin

Reputation: 855

C++ n-arry tree with different elements

I want to build a n-arry tree from a document. For that i have 3 different types of elements for the tree:

At the moment i think about something like this:


class Node {
    public:
        Node(int depth);
        int depth() const;
    private:
        int depth_;
};

class StructNode : public Node {
    ...
    private:
        std::vector<std::unique_ptr<Node>> children;
};

class ElementNode : public Node {
...
};

class ElementTemplateNode : public Node {
...
};

The Tree will be generated from an File on Startup and reused to create an output string like this:

Structname:
   key = value
   key = value
   Structname:
       key = value
   Structname:
       key = value
...

Where the Key and value where directly read from the ElementNode or read from another file with the value of the placeholder inside the ElementTemplateNode

Is there maybe a better Structure for the Tree? Because with the current one i have to check first if its a StructNode, ElementNode or ElementTemplateNode

Upvotes: 1

Views: 77

Answers (1)

Christophe
Christophe

Reputation: 73366

This is a typical structure for implementing a tree with different kind of nodes. Another variant would be the composite pattern.

The problem that you describe, is usually caused by asking the nodes about what they know, instead of telling them what to do. If you'd do it the other way round (tell, don't ask), you could get rid of those checks and benefit from polymorphism.

The different kind of nodes inherit from Node. You could design your tree using a uniform interface, with virtual functions defined for Node which then can be overridden for the different types of nodes. Calling the method would then do the right things, without need for a manual type check. For generating the output string, you'd tell the root node to generate a string. If it's a structure, it would add the heading and tell its children to generate a string, but if it's a leaf it would just add the key/value pair to the string. No need from outside to know anything about each node.

If the operation of exploring the tree shall not be implemented by the tree itself, the usual approach is to use a visitor pattern. The big advantage is that you write the vistor once, and it's then easy to specialize a new kind of visitor for different algorithms. Again, no need to check the type of the nodes. The pattern makes sure that the right elementary function is called for the right type of node.

Upvotes: 2

Related Questions