How to make a tree in C ++?

Question

How to create a tree data structure in C ++ that uses iterators instead of pointers? I could not find anything in the STL that could do this. What I would like to do is create and process the trees as follows:

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

---

Thanks, tree.hh seems to be exactly what I was looking for.

If it is to benefit from a data structure, arbitrary types of indexes, optimized for searching and good at insertion, then consider using a map.

The card is an associative container that has performance guarantees identical to the bodies of the tree: logarithmic search, logarithmic insertion, logarithmic deletion, linear space. Inside, they are often sold as red-black trees, although this is not a guarantee. However, as an STL user, all you have to take care of is guaranteeing the performance of STL algorithms and data structures. Whether they are implemented as trees or small green people should not matter to you.

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

Answer 1

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

Here is a snippet of code extracted from his 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 else? Your implementation is simpler when it comes to add node to the tree. Although your version is inaudibly simpler, the developer of this library probably wanted to have information available without looking at the tree, such as the size of the tree.

I also assume that he did not want to store the root on all nodes due to performance. Therefore, if you want to implement it in your own way, I suggest that you save most of the logic and add a link to the parent tree in the iterator and rewrite a bit.

Answer 2

Why do you need this? If this is for training, you can write your own tree data structure. If this is to take advantage of a data structure that contains arbitrary types of indexes that are optimized for search and insert good, consider using a map.

A map is an associative container that has a guarantee of performance identical to the characteristics of a tree: logarithmic search, logarithmic insertion, logarithmic deletion, linear space. Inside, they are often sold as red-black trees, although this is not a guarantee. However, as an STL user, you don't care what the performance guarantees of STL algorithms and data structures are. Whether they are implemented as trees or small green people should not matter to you.

As a side note, there is no such function as the root () function. All STL containers have a begin () function that implements the conceptual beginning of the container. The type of iterator returned by this function depends on the characteristics of the container.