Gesamtansicht des Baums, Implementierung und mehr

Viele Leute haben wahrscheinlich versucht, eine allgemeine Baumkonstruktion zu finden, aber die Suchmaschine hat nur binäre gefunden ... Binärer Suchbaum, Binärbaum-Traversierung und viele andere Algorithmen.
Ja, tatsächlich wird der allgemeine Baum nirgendwo verwendet, die Durchquerung ist langsam und die Anwendungsfälle sind klein.

Also habe ich mir diese Frage gestellt und jetzt werde ich erklären, wie der Baum gebaut wird. Idealerweise sollte eine allgemeine Baumstruktur also drei Variablen speichern:

• Hinweis auf den ältesten Sohn
• Zeiger auf 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 Zeiger auf den Scheitelpunkt deklarieren:

Node *tree = NULL;

Wir müssen uns im Voraus darauf einigen, wie die Eckpunkte eingegeben werden. Dies ist kein binärer Baum und jeder Eckpunkt kann so viele untergeordnete Elemente haben wie gewünscht.

• + 2 (oder +ssbb 2) – Einfügung in einen Baum (für einen allgemeinen Baum ist der Pfad durch die Linie gegeben, wobei r die Bildung einer Wurzel ist, s ein Übergang zum ältesten Sohn ist, b ein Übergang zu ein Bruder);

Ich werde ein Beispiel geben:

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

Das Ergebnis wird ein Baum wie dieser sein:

1
  2
    5
  3
    6
    7
  3

Erstellen wir zunächst eine Funktion, die einen Scheitelpunkt hinzufügt, nämlich Speicher für den Scheitelpunkt zuweist und einen Zeiger auf diesen Scheitelpunkt übergibt (zunächst mit nichts verbunden).

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 außerdem eine Funktion erstellen, die die Pfadzeichenfolge (+bs...) verarbeitet. Jedes Mal, wenn wir die Durchquerung von der Wurzel aus starten und sie nicht erstellt wird, geben wir NULL aus (wir können nichts tun). Wenn es keinen Scheitelpunkt gibt, müssen wir ihn erstellen. Wir gehen zur Funktion „Baum erstellen“ und erhalten einen Zeiger auf die Wurzel.

Beachten Sie, dass Node**tree die Struktur übergibt und nicht kopiert. Dies gibt uns die Möglichkeit, Dinge zu ändern, die wir mit der Node *tree-Deklaration nicht tun können.

Im Allgemeinen müssen wir einen Zeiger auf den Scheitelpunkt finden, zu dem wir den 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] != ' ') {
        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;
    }
}

So bauen wir einen Baum.

PS: Dies ist mein erster Artikel, also urteilen Sie bitte nicht zu hart

Source: habr.com