My<cod/>.net
Как сделать дерево в 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-это как раз то, что я искал.
Если это делается для получения выгоды от структура данных, содержащая произвольные типы индексов, оптимизированные для поиска и хорошо на вставке тогда считайте используя карту.
Карта-это ассоциативный контейнер, который имеет гарантии производительности идентичные к тем из дерева: логарифмические поиск, логарифмическая вставка, логарифмическое удаление, линейное пространство. Внутри страны они часто реализуются как красно-черные деревья, хотя это и так не гарантия. Тем не менее, как пользователь STL все, о чем вы должны заботиться, это гарантии производительности STL алгоритмы и структуры данных. Реализуются ли они в виде деревьев или маленькие зеленые человечки не должны иметь значения для тебя.
Я не уверен, что карта - это то, что мне нужно, но спасибо за информацию. Я буду помнить, чтобы использовать карты, когда это возможно, вместо реализации деревьев.
Вот 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;
}
}
}
А теперь что изменилось? Ваша реализация проще, когда дело доходит до добавьте узел к дереву. Хотя ваша версия заметно проще, разработчик этой библиотеки, вероятно, хотел бы иметь некоторую информацию, доступную без просмотра дерева, например, размер дерева, например.
Я также предполагаю, что он не хотел хранить корень на всех узлах по причине производительности. Поэтому, если вы хотите реализовать его по-своему, я предлагаю вам сохранить большую часть логики и добавить ссылку на родительское дерево в итераторе и немного переписать append.
Почему ты хочешь это сделать? Если это делается для целей обучения, то вы можете написать свою собственную древовидную структуру данных. Если это необходимо для получения преимуществ структуры данных, содержащей произвольные типы индексов, оптимизированной для поиска и хорошей при вставке, то рассмотрите возможность использования карты.
Карта-это ассоциативный контейнер, который имеет гарантии производительности, идентичные тем, что есть у дерева: логарифмический поиск, логарифмическая вставка, логарифмическое удаление, линейное пространство. Внутренне они часто реализуются как красно-черные деревья, хотя это и не является гарантией. Тем не менее, как пользователь STL, вы должны заботиться только о гарантиях производительности алгоритмов и структур данных STL. Будут ли они реализованы в виде деревьев или маленьких зеленых человечков, для вас не должно иметь значения.
В качестве дополнительной заметки, нет такой вещи, как функция root(). Все контейнеры STL имеют функцию begin(), реализующую концептуальное начало контейнера. Тип итератора, возвращаемого этой функцией, зависит от характеристик контейнера.