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

Question

Как мне создать древовидную структуру данных на 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;
}

---

Спасибо тебе, дерево.hh, кажется, это как раз то, что я искал.

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

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

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

Answer 1

Вот дерево.чч это немного близко к тому, что вы хотите сделать, хотя немного разных.

Вот фрагмент кода, извлеченный с его веб-сайта.

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

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

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

Answer 2

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

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

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