Wie erstelle ich einen Baum in C++?

Question

Wie erstelle ich in C++ eine Baumdatenstruktur, die Iteratoren anstelle von Zeigern verwendet?Ich konnte in der STL nichts finden, was dies kann.Was ich gerne tun würde, ist in der Lage zu sein, Bäume wie diesen zu erstellen und zu manipulieren:

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

---

Vielen Dank, tree.hh scheint genau das zu sein, was ich gesucht habe.

Wenn dies dazu dient, den Vorteil einer Datenstruktur zu nutzen, die willkürliche Indextypen hält, die für die Suche optimiert und gut in der Einfügung ist, sollten Sie eine Karte verwenden.

Eine Karte ist ein assoziativer Container, der hat identische Leistungsgarantien zu denen eines Baumes:logarithmisch Suchen, logarithmisches Einfügen, Logarithmische Löschung, linearer Raum.Intern werden sie oft umgesetzt wie rot-schwarze Bäume, obwohl das Keine Garantie.Dennoch, als STL-Benutzer Alles, worum Sie sich kümmern sollten, ist die Leistungsgarantien des SEAF Algorithmen und Datenstrukturen.Ob sie als Bäume implementiert werden oder kleine grüne Männchen sollten keine Rolle spielen an Sie.

Ich bin mir nicht sicher, ob eine Karte das ist, was ich brauche, aber danke für die Info.Ich werde daran denken, nach Möglichkeit Karten zu verwenden, anstatt Bäume zu implementieren.

Answer 1

Hier ist Baum.hh Das ist ein bisschen nah an dem, was Sie tun wollen, wenn auch ein bisschen Verschieden.

Hier ist ein Code, der von seiner Website extrahiert wurde.

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

Was ist nun anders?Ihre Implementierung ist einfacher, wenn es darum geht, Hängen Sie einen Knoten an die Struktur an.Obwohl Ihre Version unbestreitbar einfacher ist, wollte der Entwickler dieser Bibliothek wahrscheinlich einige Informationen zugänglich machen, ohne den Baum durchsuchen zu müssen, wie zum Beispiel die Größe des Baums.

Ich gehe auch davon aus, dass er aus Leistungsgründen den Root nicht auf allen Knoten speichern wollte.Wenn Sie es also auf Ihre Weise implementieren möchten, empfehle ich Ihnen, den größten Teil der Logik beizubehalten, den Link zum übergeordneten Baum im Iterator hinzuzufügen und den Anhang ein wenig umzuschreiben.

Answer 2

Warum willst du das tun?Wenn dies zu Lernzwecken dient, können Sie Ihre eigene Baumdatenstruktur schreiben.Wenn Sie die Vorteile einer Datenstruktur nutzen möchten, die beliebige Indextypen enthält, für die Suche optimiert ist und sich gut einfügen lässt, sollten Sie die Verwendung einer Karte in Betracht ziehen.

Eine Karte ist ein assoziativer Container, dessen Leistungsgarantien mit denen eines Baums identisch sind:logarithmische Suche, logarithmische Einfügung, logarithmische Löschung, linearer Raum.Intern werden sie oft als rot-schwarze Bäume umgesetzt, obwohl das keine Garantie ist.Als STL-Benutzer sollten Sie sich jedoch nur um die Leistungsgarantien der STL-Algorithmen und Datenstrukturen kümmern.Ob sie als Bäume oder kleine grüne Männchen umgesetzt werden, sollte Ihnen egal sein.

Nebenbei bemerkt: Es gibt keine root()-Funktion.Alle STL-Container verfügen über die Funktion begin(), die den konzeptionellen Anfang eines Containers implementiert.Die Art des von dieser Funktion zurückgegebenen Iterators hängt von den Eigenschaften des Containers ab.