Gesamtansicht des Baums, Umsetzung und mehr

Viele haben wahrscheinlich versucht, eine Baumstruktur allgemeinen Typs zu finden, aber die Suchmaschine fand nur binäre... Binäre Suchbäume, Durchlauf von binären Bäumen und viele andere Algorithmen.
Ja, tatsächlich wird ein Baum allgemeinen Typs nirgendwo verwendet, der Durchlauf ist langsam, die Einsatzmöglichkeiten sind gering.

Ich habe mir also diese Frage gestellt und werde jetzt erklären, wie man den Baum letztendlich aufbaut. Idealerweise sollte die Struktur eines Baums allgemeinen Typs drei Variablen speichern:

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

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

Lassen Sie uns einen Verweis auf die Wurzel deklarieren:

Node *tree = NULL;

Wir müssen im Voraus vereinbaren, wie wir die Knoten eingeben, denn es ist ja kein binärer Baum, und jeder Knoten kann beliebig viele Söhne haben.

• + 2 (oder +ssbb 2) — Einfügen in den Baum (für einen Baum allgemeinen Typs wird der Pfad durch eine Zeichenkette festgelegt, wobei r die Erstellung der Wurzel, s den Übergang zum ältesten Sohn und b den Übergang zum Bruder bezeichnet);

Hier ist ein Beispiel:

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

Das Resultat wird wie folgt aussehen:

1
  2
    5
  3
    6
    7
  3

Fangen wir an, eine Funktion zu erstellen, die das Hinzufügen eines Knotens durchführt, indem sie Speicher für den Knoten reserviert und einen Verweis auf diesen Knoten zurückgibt (zunächst unbeziehungsweise).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // Setzen der Verweise auf Brüder und Söhne auf NULL, unabhängiger Knoten, der den Wert speichert
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Es ist auch notwendig, eine Funktion zu erstellen, die den Pfadstring verarbeitet (+bs...). Jedes Mal beginnen wir den Durchlauf von der Wurzel aus; wenn sie nicht erstellt wurde, geben wir NULL aus (wir können nichts tun). Wenn der Knoten nicht vorhanden ist, müssen wir ihn erstellen. Wir gehen zur Funktion zum Erstellen eines Baums und erhalten einen Verweis auf die Wurzel.

Zur Kenntnisnahme, Node ** tree übergibt die Struktur und kopiert sie nicht. Das gibt uns die Möglichkeit, Änderungen vorzunehmen, was bei der Deklaration von Node *tree nicht möglich ist.

Generell müssen wir einen Verweis auf den Knoten finden, zu dem ein Sohn hinzugefügt werden soll:

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); // wir erstellen die Wurzel
            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 zur Spitze gegangen, zu der wir wollten 
   // und jetzt gehen wir zu ihrem letzten Sohn,
   // um am Ende der Liste hinzuzufügen
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// wenn es keinen Sohn gibt, erstellen wir einen
      t->son = create_tree(value);
      return t->son;
    }
}

So bauen wir den Baum auf.

P.S. mein erster Artikel, also bitte nicht zu hart urteilen

Quelle: habr.com