Wie erstellt man einen Baum in C++?

Question

Wie mache ich eine Baumstruktur in C++, die Iteratoren anstelle von Zeigern verwendet? Ich konnte nichts in der STL finden, das das kann. Was ich möchte in der Lage sein zu tun ist, Bäume zu erstellen und zu manipulieren, wie folgt aus:

#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, scheint tree.hh genau das, was ich suchte.

Wenn dies für die Gewinnung der Nutzen von ist eine Datenstruktur beliebigen Indextypen halten, optimiert für und gut Einsetzen suchen, dann betrachten eine Karte.

Eine Karte ist ein assoziativer Behälter, die Leistungsgarantien identisch die einen Baums hat: logarithmische Suche, logarithmische Insertion, Deletion logarithmisch, linear Raum. Intern werden sie oft als rot-schwarze Bäume implementiert, obwohl das keine Garantie ist. Als STL-Benutzer sollten Sie jedoch nur die Leistungsgarantien der STL Algorithmen und Datenstrukturen beachten. Ob sie als Bäume implementiert sind oder kleine grüne Männer sollten Sie nicht auf setzen.

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

Answer 1

Hier ist tree.hh das ist ein bisschen nah an dem, was Sie tun möchten, obwohl ein bisschen anders.

Hier ist ein Stück Code von seiner Website extrahiert.

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

Nun, was ist anders? Ihre Implementierung ist einfacher, wenn es darum geht, einen Knoten an den Baum anzuhängen. Obwohl Ihre Version unzweifelhaft einfacher ist, wollte der Entwickler dieser lib wahrscheinlich einige Informationen zugänglich haben, ohne den Baum zu durchsuchen, wie zum Beispiel die Größe des Baums.

Ich nehme auch an, er wollte nicht die Wurzel auf allen Knoten aus Leistungsgründen speichern. Also, wenn Sie es auf Ihre Weise implementieren möchten, schlage ich vor, Sie behalten den größten Teil der Logik und fügen Sie die Verbindung zum übergeordneten Baum im Iterator und umschreiben ein wenig anhängen.

Answer 2

Warum möchten Sie das tun? Wenn dies zu Lernzwecken ist, können Sie Ihre eigene Baumdatenstruktur schreiben. Wenn dies der Vorteil einer Datenstruktur sein soll, die willkürliche Indextypen enthält, die für die Suche optimiert sind und bei der Einfügung gut sind, dann sollten Sie eine Karte verwenden.

Eine Map ist ein assoziativer Container, dessen Leistungsgarantien identisch mit denen eines Baumes sind: logarithmische Suche, logarithmische Insertion, logarithmische Deletion, linearer Raum. Intern werden sie oft als rot-schwarze Bäume implementiert, obwohl das keine Garantie ist. Als STL-Benutzer sollten Sie jedoch nur die Leistungsgarantien der STL-Algorithmen und Datenstrukturen beachten. Ob sie als Bäume oder kleine grüne Männer umgesetzt werden, sollte dir egal sein.

Als eine Randnotiz gibt es keine so genannte 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.