Vista generale dell'albero, implementazione e non solo

Molti probabilmente hanno cercato di trovare la costruzione di un albero di tipo generico, ma il motore di ricerca ha trovato solo alberi binari... Alberi binari di ricerca, traversamento di alberi binari e molti altri algoritmi.
Sì, in effetti, l'albero di tipo generico non è utilizzato da nessuna parte, il traversamento è lento e le opzioni di utilizzo sono limitate.

Dunque, mi sono posto questa domanda e ora spiegherò come si costruisce un albero. Ideale sarebbe che la struttura dell'albero di tipo generico conservasse tre variabili:

• un puntatore al figlio maggiore
• un puntatore al fratello
• i dati che intendi memorizzare

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

Dichiareremo un puntatore alla radice:

Node *tree = NULL;

Dobbiamo prima concordare come effettuare l'inserimento dei nodi, dato che non stiamo parlando di un albero binario, e ogni nodo può avere un numero illimitato di figli.

• + 2 (o +ssbb 2) — inserimento nell'albero (per un albero di tipo generico il percorso è definito da una stringa, dove r indica la creazione della radice, s — passaggio al figlio maggiore, b — passaggio al fratello);

Riporto un esempio:

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

Ne risulterà un albero del genere:

1
  2
    5
  3
    6
    7
  3

Iniziamo creando una funzione che gestisce l'aggiunta di un nodo, cioè che alloca memoria per il nodo e restituisce un puntatore a questo nodo (inizialmente non collegato ad alcun altro).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // azzeriamo i puntatori ai fratelli e ai figli, nodo indipendente che conserva il valore
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

È necessario inoltre creare una funzione che gestisce la stringa del percorso (+bs...). Ogni volta iniziamo il traversamento dalla radice, se non è stata creata, restituiamo NULL (non possiamo fare nulla). Se il nodo non esiste, dobbiamo crearlo. Passiamo alla funzione di creazione dell'albero e otteniamo un puntatore alla radice.

Nota, Node ** tree passa la struttura e non la copia. Questo ci dà la possibilità di modificare, cosa che non è possibile con la dichiarazione Node *tree.

In sostanza dobbiamo trovare il puntatore al nodo a cui dobbiamo aggiungere un figlio:

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); // creiamo la radice
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // funzione che restituisce un puntatore al figlio
            continue;
          return NULL; // altrimenti NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // restituisce un puntatore al fratello t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // siamo passati al nodo a cui volevamo 
   // e ora andiamo all'ultimo suo figlio,
   // per aggiungerlo alla fine della lista
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// se non c'è il figlio, lo creiamo
      t->son = create_tree(value);
      return t->son;
    }
}

In questo modo costruiamo l'albero.

P.S. Questo è il mio primo articolo, quindi vi prego di non essere troppo severi

Fonte: habr.com