Implementing a tree in C++

Question

Hello,

I'm trying to implement a generic hierarchical tree for C++ Linux project.

I haven't been able to find any standard library tree containers, though.

Do any exist?

Thanks in advance, Tim

Answer 1

The STL set and map both use binary trees internally

Answer 2

std:map<> is implemented using a tree, you may be able to leverage that. It's the only "standard library tree container" I can think of at the moment.

Answer 3

Hi,

there's no STL class for this by default. You could write your own tree class using STL components or you could give this STL-like tree lib a try:

http://tree.phi-sci.com/

Answer 4

Boost has a PropertyTree container which might be what you are looking for. It basically consists of nodes that store a value and an arbitrary number of child nodes. Boost is pretty close to being standard as well.

http://www.boost.org/doc/libs/1_44_0/doc/html/property_tree.html

Answer 5

Here is a simple method of creating a hierarchical tree (n-ary with no special properties), using STL containers. It isn't pre-built, but it is dead simple, and takes advantage of some STL properties. To create your own searching, you'd have to implement your own algorithms, but that should be fairly painless.

template<typename T>
class TreeNode
{
public:
    TreeNode()
    {
    }

    TreeNode(const T& value)
        : Value(value)
    {
    }

    T Value;
    std::list<TreeNode<T> > Children;
};

Answer 6

There are no standard library containers available for constructing a tree structure. But, if you know enough in theory and are okay with a programming language (c++ in your case) creating a generic tree is not much of a hard task.

Start by creating generic (templatized) nodes, add two pointers for children (binary tree) or a list of pointers for children (n-ary).

struct Node
{
    int data;
    Node *left;
    Node *right;
}

There you go. Create an instance and you have the root node. Create more nodes and attach them to the root node as children. Repeat the same. Playing with trees is great!

You'll find a lot of examples over the web. There's one here Totally support Niki's answer.