🥇Vista xeral da árbore, implementación e moito máis

Moita xente probablemente intentou atopar unha construción de árbore xeral, pero o buscador só atopou unhas binarias... Árbore de busca binaria, percorrido de árbores binarias e moitos outros algoritmos.
Si, de feito, a árbore xeral non se usa en ningún lugar, o percorrido é lento, os casos de uso son pequenos.

Entón, fíxome esta pregunta e agora explicarei como se constrúe a árbore. Entón, idealmente, unha estrutura de árbore xeral debería almacenar tres variables:

punteiro para o fillo maior
punteiro a irmán
os datos que vai almacenar

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

Imos declarar un punteiro ao vértice:

Node *tree = NULL;

Debemos acordar previamente como introducir os vértices; esta non é unha árbore binaria e cada vértice pode ter tantos fillos como se desexe.

+ 2 (ou +ssbb 2) - inserción nunha árbore (para unha árbore xeral, o camiño vén dado pola liña, onde r é a creación dunha raíz, s é unha transición ao fillo maior, b é unha transición a un irmán);

Déixame un exemplo:

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

O resultado será unha árbore como esta:

En primeiro lugar, imos crear unha función que engade un vértice, é dicir, asigna memoria para o vértice e pasa un punteiro a este vértice (inicialmente non está 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;
}

Tamén cómpre crear unha función que manexa a cadea de ruta (+bs...). Cada vez que iniciamos o percorrido dende a raíz, se non se crea, saímos NULL (non podemos facer nada). Se non hai vértice, entón debemos crealo. Imos á función de crear árbore e obtemos un punteiro á raíz.

Teña en conta que Node**tree está a pasar a estrutura, non a copiala. Isto dános a posibilidade de cambiar cousas que non podemos facer coa declaración Node *tree.

En xeral, debemos atopar un punteiro ao vértice ao que necesitamos engadir o fillo:

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í é como construímos unha árbore.

P.S. o meu primeiro artigo, así que, por favor, non xulgues demasiado

Fonte: www.habr.com

Vista xeral da árbore, implementación e moito máis

Engadir un comentario Cancelar resposta