🥇Vista generale dell'albero, realizzazione e altro

Molte persone probabilmente hanno provato a trovare una costruzione generale di alberi, ma il motore di ricerca ha trovato solo costruzioni binarie... Albero di ricerca binario, attraversamento di alberi binari e molti altri algoritmi.
Sì, in effetti, l'albero generale non viene utilizzato da nessuna parte, la traversata è lenta, i casi d'uso sono piccoli.

Allora mi sono posto questa domanda e ora vi spiego come si costruisce l'albero. Quindi, idealmente, una struttura ad albero generale dovrebbe memorizzare tre variabili:

puntatore al figlio maggiore
puntatore al fratello
i dati che intendi archiviare

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

Dichiariamo un puntatore al vertice:

Node *tree = NULL;

Dobbiamo concordare in anticipo come inserire i vertici; questo non è un albero binario e ogni vertice può avere quanti figli si desidera.

+ 2 (o +ssbb 2) - inserimento in un albero (per un albero generale, il percorso è dato dalla linea, dove r è la creazione di una radice, s è una transizione al figlio maggiore, b è una transizione a un fratello);

Darò un esempio:

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

Il risultato sarà un albero come questo:

Innanzitutto, creiamo una funzione che aggiunge un vertice, ovvero alloca memoria per il vertice e passa un puntatore a questo vertice (inizialmente non connesso a nulla).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //обнуляем указатели к братьям и сыновьям, независимая вершина, которая хранит value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

È inoltre necessario creare una funzione che gestisca la stringa del percorso (+bs...). Ogni volta che iniziamo l'attraversamento dalla radice, se non viene creata, restituiamo NULL (non possiamo fare nulla). Se non c'è un vertice, allora dobbiamo crearlo. Andiamo alla funzione di creazione dell'albero e otteniamo un puntatore alla radice.

Tieni presente che Node**tree passa la struttura, non la copia. Questo ci dà la possibilità di cambiare cose che non possiamo fare con la dichiarazione Node *tree.

In generale dobbiamo trovare un puntatore al vertice a cui dobbiamo 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); // создаем корень
            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;
    }
}

Ecco come costruiamo un albero.

PS il mio primo articolo, quindi per favore non giudicare troppo severamente

Fonte: habr.com

Vista generale dell'albero, implementazione e altro

Aggiungi un commento Cancella risposta