How to make a tree in C++?

Question

How do I make a tree data structure in C++ that uses iterators instead of pointers? I couldn't find anything in the STL that can do this. What I would like to do is to be able to create and manipulate trees like this:

#include <iostream>
#include <tree>
using namespace std;

int main()
{
    tree<int> myTree;

    tree<int>::iterator i = myTree.root();
    *i = 42;

    tree<int>::iterator j = i.add_child();
    *j = 777;
    j = j.parent();

    if (i == myTree.root() && i == j) cout << "i and j are both pointing to the root\n";

    return 0;
}

Answer 1

Why would you want to do that? If this is for learning purposes then you can write your own tree data structure. If this is for gaining the benefit of a data-structure holding arbitrary index types, optimized for searching and good at insertion then consider using a map.

A map is an associative container that has performance guarantees identical to those of a tree: logarithmic searching, logarithmic insertion, logarithmic deletion, linear space. Internally they are often implemented as red-black trees, although that is not a guarantee. Still, as an STL user all you should care about is the performance guarantees of the STL algorithms and data-structures. Whether they're implemented as trees or little green men shouldn't matter to you.

As a side note, there's no such thing as a root() function. All STL containers have the begin() function implementing the conceptual beginning of a container. The kind of iterator returned by that function depends on the characteristics of the container.

Answer 2

Here is tree.hh which is a bit close to what you want to do, though a bit different.

Here is a piece of code extracted from its website.

int main(int, char **)
   {
   tree<string> tr;
   tree<string>::iterator top, one, two, loc, banana;

   top=tr.begin();
   one=tr.insert(top, "one");
   two=tr.append_child(one, "two");
   tr.append_child(two, "apple");
   banana=tr.append_child(two, "banana");
   tr.append_child(banana,"cherry");
   tr.append_child(two, "peach");
   tr.append_child(one,"three");

   loc=find(tr.begin(), tr.end(), "two");
   if(loc!=tr.end()) {
      tree<string>::sibling_iterator sib=tr.begin(loc);
      while(sib!=tr.end(loc)) {
         cout << (*sib) << endl;
         ++sib;
         }
      cout << endl;
      tree<string>::iterator sib2=tr.begin(loc);
      tree<string>::iterator end2=tr.end(loc);
      while(sib2!=end2) {
         for(int i=0; i<tr.depth(sib2)-2; ++i) 
            cout << " ";
         cout << (*sib2) << endl;
         ++sib2;
         }
      }
   }

Now what's different? Your implementation is simpler when it comes to append a node to the tree. Though your version is indiscutably simpler, the dev of this lib probably wanted to have some info accessible without browsing the tree, such as the size of the tree for instance.

I also assume he didn't want to store the root on all nodes for performance reason. So if you want to implement it your way, I suggest you keep most of the logic and add the link to the parent tree in the iterator and rewrite append a bit.

Answer 3

Thank you, tree.hh seems to be just what I was looking for.

If this is for gaining the benefit of a data-structure holding arbitrary index types, optimized for searching and good at insertion then consider using a map.

A map is an associative container that has performance guarantees identical to those of a tree: logarithmic searching, logarithmic insertion, logarithmic deletion, linear space. Internally they are often implemented as red-black trees, although that is not a guarantee. Still, as an STL user all you should care about is the performance guarantees of the STL algorithms and data-structures. Whether they're implemented as trees or little green men shouldn't matter to you.

I'm not sure if a map is what I need, but thanks for the info. I will remember to use maps whenever possible instead of implementing trees.

Answer 4

@wilhelmtell

Why would you want to do that?

We are all happy to know that you know that map are implemented via trees, but dacodemonkey never said he was trying to reimplement a binary tree for lookup purpose...

Here is a few example of situations where map just weren't good enough for me. - A preprocessed template library. - Manipulation of logical expressions - Storing predicates, and getting out all of those who are compatible with another. - Storing chains of integers and getting all of those who match patterns such as ab... ...