Как сделать дерево на C++?
Как создать древовидную структуру данных на C++, в которой используются итераторы вместо указателей? Я не нашел в STL ничего, что могло бы это сделать. Я бы хотел иметь возможность создавать деревья и управлять ими следующим образом:
#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;
}
Спасибо, tree.hh кажется именно тем, что я искал.
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.
Я не уверен, что карта мне нужна, но спасибо за информацию. Я буду не забывать использовать карты, когда это возможно, вместо того, чтобы реализовывать деревья.
Ответы 2
Почему вы хотите это сделать? Если это сделано в учебных целях, вы можете написать свою собственную древовидную структуру данных. Если это необходимо для получения преимущества структуры данных, содержащей произвольные типы индексов, оптимизированной для поиска и удобной для вставки, рассмотрите возможность использования карты.
Карта - это ассоциативный контейнер, который имеет гарантии производительности, идентичные таковым у дерева: логарифмический поиск, логарифмическая вставка, логарифмическое удаление, линейное пространство. Внутри они часто реализуются как красно-черные деревья, хотя это не гарантия. Тем не менее, как пользователь STL, все, о чем вы должны заботиться, - это гарантии производительности алгоритмов STL и структур данных. Неважно, реализованы ли они в виде деревьев или маленьких зеленых человечков.
Кстати, не существует такой вещи, как функция root (). Все контейнеры STL имеют функцию begin (), реализующую концептуальное начало контейнера. Тип итератора, возвращаемого этой функцией, зависит от характеристик контейнера.
Вот tree.hh, который немного близок к тому, что вы хотите сделать, хотя и немного разные.
Вот фрагмент кода, извлеченный с его веб-сайта.
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;
}
}
}
Что изменилось? Ваша реализация проще, когда дело доходит до добавить узел к дереву. Хотя ваша версия indiscutably проще, Дев из этой библиотеки, вероятно, хотел бы иметь некоторую информацию, доступную без просмотра дерева, таких как размер дерева, например.
Я также предполагаю, что он не хотел хранить корень на всех узлах по соображениям производительности. Поэтому, если вы хотите реализовать это по-своему, я предлагаю вам сохранить большую часть логики и добавить ссылку на родительское дерево в итераторе и немного переписать добавление.