Как сделать дерево в C ++? - PullRequest
Новая
       20

Как сделать дерево в C ++?

6 голосов
/ 21 августа 2008

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

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

Ответы [ 2 ]

5 голосов
/ 21 августа 2008

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

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

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

3 голосов
/ 21 августа 2008

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

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

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

...