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

Probablemente muchas personas intentaron encontrar una construcción de árbol general, pero el motor de búsqueda solo encontró binarios... Árbol de búsqueda binario, recorrido de árbol binario y muchos otros algoritmos.
Sí, de hecho, el árbol general no se usa en ninguna parte, el recorrido es lento y los casos de uso son pequeños.

Entonces me hice esta pregunta y ahora explicaré cómo se construye el árbol. Entonces, idealmente, una estructura de árbol general debería almacenar tres variables:

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

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

Declaremos un puntero al vértice:

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 tantos hijos como desee.

+ 2 (o +ssbb 2) - inserción en un árbol (para un árbol general, el camino está dado por la línea, donde r es la creación de una raíz, s es una transición al hijo mayor, b es una transición a un hermano);

Daré un ejemplo:

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

El resultado será un árbol como este:

Primero, creemos 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 conectado a 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 necesita crear una función que maneje la cadena de ruta (+bs...). Cada vez que iniciamos el recorrido desde la raíz, si no se crea, generamos NULL (no podemos hacer nada). Si no hay ningún vértice, entonces debemos crearlo. Vamos a la función de creación de árbol y obtenemos un puntero a la raíz.

Tenga en cuenta que Node**tree pasa la estructura, no la copia. Esto nos da la capacidad de cambiar cosas que no podemos hacer con la declaración del árbol Node *.

En general, debemos encontrar un puntero al vértice al que necesitamos agregar el hijo:

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;
    }
}

Así construimos un árbol.

PD Mi primer artículo, así que no juzgues demasiado duramente.

Fuente: habr.com

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

Añadir un comentario Cancelar respuesta