Aspectul general al copacului, implementare și nu numai

Multe persoane au încercat probabil să găsească o structură de arbore de tip general, dar motoarele de căutare găseau doar arborele binar... Arborele binar de căutare, parcurgerea arborelui binar și multe alte algoritmi.
Da, într-adevăr, arborele de tip general nu este folosit nicăieri, parcurgerea este lentă, iar opțiunile de utilizare sunt reduse.

Așadar, m-am pus pe mine însămi această întrebare și acum voi explica cum se construiește totuși arborele. Așadar, în ideal, structura arborelui de tip general ar trebui să fie formată din trei variabile:

• un pointer către fiul mai mare
• un pointer către frate
• datele pe care doriți să le stocați

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

Să declarăm un pointer către frunza:

Node *tree = NULL;

Trebuie să ne înțelegem din timp cum vom realiza introducerea vârfurilor, pentru că nu este un arbore binar, iar fiecare vârf poate avea un număr nelimitat de fii.

• + 2 (sau +ssbb 2) — inserare în arbore (pentru arborele de tip general, calea este dată printr-un șir unde r reprezintă crearea rădăcinii, s — trecerea la fiul mai mare, b — trecerea la frate);

Iată un exemplu:

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

Rezultatul va fi un arbore astfel:

1
  2
    5
  3
    6
    7
  3

În primul rând, să creăm o funcție care efectuează adăugarea unui vârf, adică alocă memorie pentru vârf și trimite un pointer către acest vârf (inițial neconectat la nimic).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // se inițializează pointerii către frați și fii, un vârf independent, care stochează value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

De asemenea, trebuie să creăm o funcție care procesează șirul de cale (+bs…). Începem întotdeauna parcurgerea de la rădăcină, dacă aceasta nu este creată, afișăm NULL (nu putem face nimic). Dacă vârful nu există, trebuie să-l creăm. Trecem la funcția de creare a arborelui și obținem un pointer către rădăcină.

De menționat, Node ** tree transmite structura, nu o copiază. Aceasta ne oferă posibilitatea de a modifica, ceea ce nu se poate face în cazul declarației Node *tree.

În general, trebuie să găsim un pointer către vârful la care trebuie adăugat un fiu:

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); // creăm rădăcina
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funcția care returnează un pointer la fiu
            continue;
          return NULL; // altfel NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // returnează un pointer la fratele t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // am ajuns la vârful dorit 
   // și acum mergem la ultimul său fiu,
   // pentru a adăuga la sfârșitul listei
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// dacă nu există fiu, îl vom crea
      t->son = create_tree(value);
      return t->son;
    }
}

Astfel construim arborele.

P.S. acesta este primul meu articol, așa că vă rog să nu fiți prea critici

Sursa: habr.com