Aspetto generale dell'albero, implementazione e non solo

Molti, probabilmente, hanno cercato di trovare una costruzione ad albero di aspetto generale, ma il motore di ricerca trovava solo alberi binari... Albero binario di ricerca, traversata dell'albero binario e molti altri algoritmi.
Sì, in effetti, l'albero di aspetto generale non viene utilizzato da nessuna parte, la traversata è lenta, le opzioni di utilizzo sono poche.

Bene, mi sono posto questa domanda e ora spiegherò come costruire effettivamente un albero. Quindi, idealmente, la struttura dell'albero di aspetto generale dovrebbe memorizzare tre variabili:

• puntatore al figlio maggiore
• puntatore al fratello
• dati che si intende 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 gestire l'input dei nodi, poiché non si tratta di un albero binario e ogni nodo può avere un numero arbitrario di figli.

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

Farò un esempio:

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

Il risultato sarà un albero di questo tipo:

1
  2
    5
  3
    6
    7
  3

Iniziamo creando una funzione che aggiunge un nodo, ovvero alloca memoria per il nodo e restituisce un puntatore a questo nodo (inizialmente non associato a nulla).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  \\ inizializziamo a NULL i puntatori a fratelli e figli, un nodo indipendente che memorizza il valore
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

È anche necessario creare una funzione che elabora la stringa del percorso (+bs…). Ogni volta iniziamo la traversata dalla radice, se non è stata creata, stampiamo 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.

Da notare che Node ** tree passa la struttura invece di copiarla. Questo ci consente di apportare modifiche, cosa che non è possibile fare con la dichiarazione Node *tree.

In generale, dobbiamo trovare un puntatore al nodo a cui aggiungere il 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 che volevamo 
   // e ora andiamo all'ultimo suo figlio,
   // per aggiungere in fondo alla lista
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// se non c'è figlio, lo creeremo
      t->son = create_tree(value);
      return t->son;
    }
}

In questo modo costruiamo l'albero.

P.S. il mio primo articolo, quindi vi prego di non giudicare severamente

Fonte: habr.com