Vedere generală a arborelui, implementare și multe altele

Mulți oameni au încercat probabil să găsească o construcție generală de arbore, dar motorul de căutare a găsit doar cele binare... Arborele de căutare binar, traversarea arborelui binar și mulți alți algoritmi.
Da, într-adevăr, arborele general nu este folosit nicăieri, traversarea este lentă, cazurile de utilizare sunt mici.

Așadar, mi-am pus această întrebare și acum voi explica cum este construit copacul. Deci, în mod ideal, o structură arborescentă generală ar trebui să stocheze trei variabile:

• arătătorul către fiul cel mare
• arătătorul către frate
• datele pe care urmează 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 vârf:

Node *tree = NULL;

Trebuie să cădem de acord în prealabil cum să introduceți vârfuri, acesta nu este un arbore binar și fiecare vârf poate avea cât de mulți copii doriți.

• + 2 (sau +ssbb 2) - inserare într-un arbore (pentru un arbore general, calea este dată de linie, unde r este crearea unei rădăcini, s este o tranziție la fiul cel mare, b este o tranziție la un frate);

Voi da un exemplu:

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

Rezultatul va fi un arbore ca acesta:

1
  2
    5
  3
    6
    7
  3

Mai întâi, să creăm o funcție care adaugă un vârf, și anume, alocă memorie pentru vârf și trece 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;
  //обнуляем указатели к братьям и сыновьям, независимая вершина, которая хранит value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

De asemenea, trebuie să creați o funcție care să gestioneze șirul de cale (+bs...). De fiecare dată când începem traversarea de la rădăcină, dacă nu este creată, atunci scoatem NULL (nu putem face nimic). Dacă nu există un vârf, atunci trebuie să-l creăm. Mergem la funcția de creare a arborelui și obținem un pointer către rădăcină.

Rețineți că Node**tree trece structura, nu o copiază. Acest lucru ne oferă posibilitatea de a schimba lucruri pe care nu le putem face cu declarația Node *tree.

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

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;
    }
}

Așa construim un copac.

PS acesta este primul meu articol, așa că vă rugăm să nu judeca prea aspru

Sursa: www.habr.com