Как сделать дерево в 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 и структур данных. Будь они реализованы в виде деревьев или маленьких зеленых человечков, для вас не имеет значения.

Я не уверен, нужна ли мне карта, но спасибо за информацию. Я буду помнить использовать карты, когда это возможно, вместо реализации деревьев.

21.08.2008 01:28:06
2 ОТВЕТА
РЕШЕНИЕ

Вот 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;
         }
      }
   }

Теперь, что отличается? Ваша реализация проще, когда дело доходит до добавления узла в дерево. Хотя ваша версия намного проще, разработчик этой библиотеки, вероятно, хотел, чтобы некоторая информация была доступна без просмотра дерева, например, размер дерева.

Я также предполагаю, что он не хотел хранить корень на всех узлах по соображениям производительности. Поэтому, если вы хотите реализовать это по-своему, я предлагаю вам сохранить большую часть логики и добавить ссылку на родительское дерево в итераторе, а затем переписать и добавить немного.

5
21.08.2008 03:05:55

Почему вы хотите это сделать? Если это для целей обучения, то вы можете написать свою собственную древовидную структуру данных. Если это для получения выгоды от структуры данных, содержащей произвольные типы индексов, оптимизированных для поиска и хороших при вставке, тогда подумайте об использовании карты.

Карта - это ассоциативный контейнер, который имеет гарантии производительности, идентичные тем, что есть у дерева: логарифмический поиск, логарифмическая вставка, логарифмическое удаление, линейное пространство. Внутренне они часто реализуются как красно-черные деревья, хотя это не является гарантией. Тем не менее, как пользователь STL все, что вам нужно, это гарантии производительности алгоритмов STL и структур данных. Будь они реализованы в виде деревьев или маленьких зеленых человечков, для вас не имеет значения.

Как примечание, нет такой вещи как функция root (). Все контейнеры STL имеют функцию begin (), реализующую концептуальное начало контейнера. Тип итератора, возвращаемого этой функцией, зависит от характеристик контейнера.

3
21.08.2008 01:47:02