Gesamtansicht des Baumes, Implementierung und nicht nur

Viele haben wahrscheinlich versucht, die Konstruktion eines allgemeinen Baums zu finden, aber die Suchmaschine hat nur binäre gefunden ... Den binären Suchbaum, die Durchquerung des binären Baums und viele andere Algorithmen.
Ja, in der Tat wird der allgemeine Baum nirgendwo verwendet, der Bypass ist langsam, die Anwendungsfälle sind klein.

Also habe ich diese Frage gestellt und jetzt werde ich erklären, wie der Baum gebaut wird. Idealerweise sollte die Struktur eines Baums allgemeiner Form drei Variablen enthalten:

• Zeiger auf den ältesten Sohn
• Zeiger auf Bruder
• Daten, die Sie speichern werden

struct Tnode { int key; struct Tnode *son; struct Tnode *brother; }; typedef struct Tnode Node; 

Deklarieren Sie einen Zeiger nach oben:

 Node *tree = NULL; 

Wir müssen im Voraus vereinbaren, wie die Eckpunkte eingegeben werden sollen. Dies ist kein binärer Baum, und jeder Eckpunkt kann beliebige Söhne haben.

• + 2 (oder + ssbb 2) - Einfügen in den Baum (für einen allgemeinen Baum wird der Pfad durch die Linie angegeben, wobei r die Wurzel ist, s der Übergang zum ältesten Sohn ist, b der Übergang zum Bruder ist);

Ich werde ein Beispiel geben:

 +r 1 + 2 + 3 + 3 +s 5 +sb 6 +sb 7 

Als Ergebnis wird dieser Baum freigegeben:

 1 2 5 3 6 7 3 

Erstellen Sie zunächst eine Funktion, die einen Scheitelpunkt hinzufügt, nämlich Speicher für den Scheitelpunkt zuweist und einen Zeiger auf diesen Scheitelpunkt übergibt (anfangs ohne Bezug zu irgendetwas).

 Node *create_tree(int v) { Node *Tree = (Node *) malloc(sizeof(Node)); Tree->key = v; //     ,  ,   value Tree->son = NULL; Tree->brother = NULL; return Tree; } 

Sie müssen auch eine Funktion erstellen, die die Pfadzeichenfolge verarbeitet (+ bs ...). Jedes Mal, wenn wir den Traversal vom Stamm aus starten, wird NULL ausgegeben (wir können nichts tun), wenn er nicht erstellt wurde. Wenn es keinen Peak gibt, müssen wir ihn erstellen. Gehen Sie zur Funktion "Baum erstellen" und rufen Sie einen Zeiger auf die Wurzel auf.

Hinweis: Der Knotenbaum ** übergibt die Struktur, nicht das Kopieren. Dies gibt uns die Möglichkeit, zu ändern, was im Gegensatz zur Node * -Baumdeklaration nicht möglich ist.

Im Allgemeinen sollten wir einen Zeiger nach oben finden, zu dem wir einen Sohn hinzufügen müssen:

 Node* add_node(Node **tree, const char *a) { Node* t = *tree; int value; scanf("%d", &value); int i = 0; while (a[++i] != '\0') { if (a[i] == 'r') { *tree = create_tree(value); //   t = *tree; return *tree; } if (a[i] == 's') { if (t = to_son(t)) // ,      continue; return NULL; // NULL } if (a[i] == 'b') { if (t = to_brother(t)) //    t continue; return NULL; } } if (t->son != NULL) { t = last_son(t); //    ,    //      , //     t->brother = create_tree(value); return t->brother; } else {//  ,    t->son = create_tree(value); return t->son; } } 

Auf diese Weise bauen wir einen Baum.

PS ist mein erster Artikel, also bitte nicht streng beurteilen