Vista general del árbol, implementación y no solo

Muchos probablemente trataron de encontrar la construcción de un árbol general, pero el motor de búsqueda solo encontró binarios ... El árbol de búsqueda binario, el recorrido del árbol binario y muchos otros algoritmos.
Sí, de hecho, el árbol general no se usa en ninguna parte, el bypass es lento, los casos de uso son pequeños.

Entonces, hice esta pregunta y ahora explicaré cómo se está construyendo el árbol. Entonces, idealmente, la estructura de un árbol de forma general debería almacenar tres variables:

• puntero al hijo mayor
• puntero al hermano
• datos que vas a almacenar

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

Declara un puntero a la parte superior:

 Node *tree = NULL; 

Debemos acordar de antemano cómo ingresar los vértices, este no es un árbol binario y cada vértice puede tener hijos.

• + 2 (o + ssbb 2): inserción en el árbol (para un árbol general, la ruta está especificada por la línea, donde r es la raíz, s es la transición al hijo mayor, b es la transición al hermano);

Daré un ejemplo:

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

Como resultado, se lanzará este árbol:

 1 2 5 3 6 7 3 

Primero, cree una función que agregue un vértice, es decir, asigne memoria para el vértice y pase un puntero a este vértice (inicialmente no relacionado con nada).

 Node *create_tree(int v) { Node *Tree = (Node *) malloc(sizeof(Node)); Tree->key = v; //     ,  ,   value Tree->son = NULL; Tree->brother = NULL; return Tree; } 

También debe crear una función que procese la cadena de ruta (+ bs ...). Cada vez que comenzamos el recorrido desde la raíz, si no se crea, imprimimos NULL (no podemos hacer nada). Si no hay pico, entonces debemos crearlo. Vaya a la función crear árbol y obtenga un puntero a la raíz.

Nota: El nodo ** árbol pasa la estructura, no la copia. Esto nos da la capacidad de cambiar lo que no se puede hacer, a diferencia de la declaración del árbol Node *.

En general, debemos encontrar un puntero en la parte superior, al que debemos agregar un hijo:

 Node* add_node(Node **tree, const char *a) { Node* t = *tree; int value; scanf("%d", &value); int i = 0; while (a[++i] != '\0') { 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; } } 

De esta manera construimos un árbol.

PD es mi primer artículo, así que no juzgues estrictamente