Översikt över trädet, implementering och mer

Många har nog försökt hitta strukturen för ett allmänt träd, men sökmotorn hittade bara binära... Binärt sökträd, traversering av binära träd och många andra algoritmer.
Ja, faktiskt, allmänt träd används ingenstans, traverseringen är långsam och användningsområdena är små.

Så, jag ställde mig frågan och kommer nu att förklara hur ett träd faktiskt byggs. Så, i idealfallet bör strukturen för ett allmänt träd lagra tre variabler:

• pekare till den äldre sonen
• pekare till brodern
• data som du planerar att lagra

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

Låt oss deklarera en pekare till roten:

Node *tree = NULL;

Vi måste på förhand komma överens om hur vi ska införa noder, det är ju inte ett binärt träd, och varje nod kan ha hur många söner som helst.

• + 2 (eller +ssbb 2) — infogning i trädet (för det allmänna trädet anges vägen som en sträng där r skapar roten, s går till den äldre sonen, b går till brodern);

Här är ett exempel:

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

Resultatet kommer att vara ett sådant träd:

1
  2
    5
  3
    6
    7
  3

Till att börja med skapar vi en funktion som lägger till en nod, det vill säga som allokerar minne för noden och ger en pekare till denna nod (som från början inte är kopplad till något).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // nollställer pekarna till bröder och söner, en oberoende nod som lagrar värdet
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Det är också nödvändigt att skapa en funktion som behandlar strängen för vägen (+bs…). Varje gång vi börjar traverseringen från roten, om den inte är skapad, visar vi NULL (vi kan inte göra något). Om noden inte finns, måste vi skapa den. Vi går till funktionen att skapa trädet och får en pekare till roten.

Observera att Node ** tree överför strukturen och kopierar inte. Detta ger oss möjlighet att förändra, vilket inte kan göras i motsats till deklarationen Node *tree.

I allmänhet måste vi hitta pekaren till noden, till vilken vi behöver lägga till en son:

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); // skapar roten
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funktion som returnerar pekare till sonen
            continue;
          return NULL; // annars NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // returnerar pekare till brodern t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // vi har kommit till toppen, som vi ville
   // och nu går vi till dess sista son,
   // för att lägga till i slutet av listan
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// om det inte finns någon son, skapar vi en
      t->son = create_tree(value);
      return t->son;
    }
}

Så bygger vi ett träd.

P.S. Min första artikel, så jag ber er att inte döma för hårt.

Källa: habr.com