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;
}

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.

fulmicoton · Accepted Answer · 2008-08-21 03:05:55Z

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.

wilhelmtell · Accepted Answer · 2008-08-21 01:47:02Z

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.

Collectives™ on Stack Overflow

How to make a tree in C++?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related