Generelt overblik over træet, implementeringen og mere

Mange har sikkert forsøgt at finde en træstruktur af almindelig type, men søgemaskinen fandt kun binære... Binære søgetræer, traversal af binære træer og mange andre algoritmer.
Ja, faktisk anvendes træet af almindelig type ingen steder, traversal er langsom, og anvendelsesmulighederne er små.

Så jeg stillede mig selv dette spørgsmål og vil nu forklare, hvordan træet faktisk bygges. Så i ideelle tilfælde skal strukturen af træet af almindelig type gemme tre variabler:

• et peger til den ældste søn
• et peger til broderen
• dataene, som du ønsker at gemme

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

Lad os erklære en peger til roden:

Node *tree = NULL;

Vi skal på forhånd blive enige om, hvordan vi indtaster noder, da det ikke er et binært træ, og hver node kan have et ubegribeligt antal sønner.

• + 2 (eller +ssbb 2) — indsættelse i træet (for et træ af almindelig type angives stien som en streng, hvor r skaber roden, s — bevægelse til den ældste søn, b — bevægelse til broderen);

Jeg vil give et eksempel:

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

Som resultat vil træet se således ud:

1
  2
    5
  3
    6
    7
  3

Lad os først oprette en funktion, der tilføjer en node, hvilket specifikt tildeler hukommelse til noden og returnerer pegeren til denne node (oprindeligt ikke knyttet til noget).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // nulstil pegerne til brødre og sønner, en uafhængig node, der gemmer værdien
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Det er også nødvendigt at oprette en funktion, der behandler strengen for stien (+bs…). Hver gang starter vi traversal fra roden, hvis den ikke er oprettet, så returnerer vi NULL (vi kan ikke gøre noget). Hvis noden ikke findes, skal vi oprette den. Vi går til træoprettelsesfunktionen og får pegeren til roden.

Til noten, Node ** tree overdrager strukturen og kopierer ikke. Dette giver os mulighed for at ændre, hvilket ikke kan gøres i modsætning til erklæringen Node *tree.

Generelt skal vi finde pegeren til den node, hvortil vi skal tilføje en søn:

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); // opretter rod
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funktion, der returnerer en peger til sønnen
            continue;
          return NULL; // ellers NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // returnerer en peger til bror t
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // vi er gået til den top, vi ønskede 
   // og nu går vi til dens sidste søn,
   // for at tilføje i slutningen af listen
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// hvis der ikke er nogen søn, så opretter vi den
      t->son = create_tree(value);
      return t->son;
    }
}

Således bygger vi et træ.

P.S. dette er min første artikel, så vær venlig ikke at dømme for hårdt

Kilde: habr.com