Vista general del árbol, implementación y más

Muchos probablemente han intentado encontrar la construcción de un árbol de tipo general, pero el buscador solo encontraba árboles binarios... Árboles binarios de búsqueda, recorrido de árboles binarios y muchos otros algoritmos.
Sí, de hecho, el árbol de tipo general no se utiliza en ninguna parte, el recorrido es lento, las opciones de uso son pequeñas.

Así que me hice esta pregunta y ahora voy a explicar cómo se construye un árbol de este tipo. Idealmente, la estructura de un árbol de tipo general debe almacenar tres variables:

• un puntero al hijo mayor
• un puntero al hermano
• los datos que planeas almacenar

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

Declaramos un puntero a la raíz:

Node *tree = NULL;

Debemos acordar de antemano cómo se realizará la entrada de los nodos, ya que no se trata de un árbol binario, y cada nodo puede tener cualquier número de hijos.

• + 2 (o +ssbb 2) — inserción en el árbol (para un árbol de tipo general, el camino se define mediante una cadena, donde r crea la raíz, s se mueve al hijo mayor, b se mueve al hermano);

Voy a dar un ejemplo:

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

Como resultado, obtendremos el siguiente árbol:

1
  2
    5
  3
    6
    7
  3

Primero, crearemos una función que realiza la adición de un nodo, esto implica reservar memoria para el nodo y pasar el puntero a este nodo (inicialmente no asociado con nada).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // inicializamos los punteros a hermanos e hijos, un nodo independiente que almacena el valor
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

También es necesario crear una función que procese la cadena de camino (+bs…). Cada vez comenzamos el recorrido desde la raíz, si no se ha creado, mostramos NULL (no podemos hacer nada). Si el nodo no existe, debemos crearlo. Pasamos a la función crear árbol y obtenemos un puntero a la raíz.

A tener en cuenta, Node ** tree pasa la estructura, no la copia. Esto nos permite modificar, lo cual no se puede hacer a diferencia de declarar Node *tree.

En general, debemos encontrar el puntero al nodo al que queremos agregar un hijo:

Nodo* add_node(Nodo **árbol, const char *a) {
  Nodo* t = *árbol;
  int valor;
  scanf("%d", &valor);
  int i = 0;
      mientras (a[++i] != ' ') {
        if (a[i] == 'r') {
            *árbol = create_tree(valor); // creamos la raíz
            t = *árbol;
            return *árbol;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // función que devuelve el puntero al hijo
            continue;
          return NULL; // de lo contrario NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // devuelve el puntero al hermano t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // hemos llegado a la cima, a la que queríamos 
   // y ahora vamos al último de sus hijos,
   // para añadir al final de la lista
    t->brother = create_tree(valor);
    return t->brother;
    }
    else {// si no hay hijo, lo crearemos
      t->son = create_tree(valor);
      return t->son;
    }
}

Así construimos el árbol.

P.D. Este es mi primer artículo, así que por favor, no sean demasiado críticos.

Fuente: habr.com