Gesamtansicht des Baums, Umsetzung und mehr

Viele haben wahrscheinlich versucht, eine Baumstruktur allgemeinen Typs zu finden, aber die Suchmaschine konnte nur binäre Ergebnisse liefern... Binäre Suchbäume, Traversierungen binärer Bäume und viele andere Algorithmen.
Ja, tatsächlich wird ein Baum allgemeinen Typs nirgendwo verwendet, die Traversierung ist langsam und die Anwendungsmöglichkeiten sind gering.

Deshalb habe ich mir diese Frage gestellt und werde jetzt erklären, wie ein solcher Baum aufgebaut wird. Idealerweise sollte die Struktur eines allgemeinen Baumes drei Variablen speichern:

• Zeiger auf den ältesten Sohn
• Zeiger auf den Bruder
• Daten, die Sie speichern möchten

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

Lassen Sie uns einen Zeiger auf die Wurzel deklarieren:

Node *tree = NULL;

Wir müssen uns im Voraus darauf einigen, wie wir Knoten eingeben, denn das ist kein binärer Baum, und jeder Knoten kann eine beliebige Anzahl von Söhnen haben.

• + 2 (oder +ssbb 2) — Einfügen in den Baum (bei einem allgemeinen Baum wird der Pfad durch eine Zeichenkette angegeben, wo r das Erstellen der Wurzel bedeutet, s — das Wechseln zum ältesten Sohn, b — das Wechseln zum Bruder);

Ich gebe ein Beispiel:

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

Das Ergebnis wird ein solcher Baum sein:

1
  2
    5
  3
    6
    7
  3

Zuerst erstellen wir eine Funktion, die einen neuen Knoten hinzufügt, indem sie Speicher für den Knoten zuweist und einen Zeiger auf diesen Knoten übergibt (anfangs unverbunden).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // Setzen der Zeiger auf Geschwister und Kinder auf NULL, da es sich um einen unabhängigen Knoten handelt, der den Wert speichert
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Es muss auch eine Funktion erstellt werden, die den Pfadstring verarbeitet (+bs…). Jedes Mal beginnen wir den Durchlauf am Wurzelknoten; wenn dieser nicht existiert, geben wir NULL aus (wir können nichts tun). Wenn der Knoten nicht existiert, müssen wir ihn erstellen. Wir gehen zur Funktion zum Erstellen des Baumes und erhalten einen Zeiger auf die Wurzel.

Zur Information: Node ** tree übergibt die Struktur und kopiert sie nicht. Dies ermöglicht uns Änderungen, was mit der Deklaration Node *tree nicht möglich ist.

Im Allgemeinen müssen wir den Zeiger auf den Knoten finden, zu dem wir einen Sohn hinzufügen möchten:

Node* add_node(Node **tree, const char *a) {
  Node* t = *tree;
  int value;
  scanf("%d", &value);
  int i = 0;
      while (a[++i] != ' ') {
        if (a[i] == 'r') {
            *tree = create_tree(value); // Wurzel erstellen
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // Funktion, die einen Zeiger auf den Sohn zurückgibt
            continue;
          return NULL; //sonst NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // gibt einen Zeiger auf den Bruder t zurück
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // Wir sind an die Spitze gegangen, zu der wir wollten 
   // und jetzt gehen wir zu ihrem letzten Sohn,
   // um ihn am Ende der Liste hinzuzufügen
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// wenn es keinen Sohn gibt, erstellen wir ihn
      t->son = create_tree(value);
      return t->son;
    }
}

So bauen wir den Baum auf.

P.S. Dies ist mein erster Artikel, also bitte urteilen Sie nicht zu streng.

Quelle: habr.com