Visão geral da árvore, implementação e mais

Muitos provavelmente tentaram encontrar uma árvore de estrutura geral, mas o mecanismo de busca encontrava apenas árvores binárias... Árvore binária de busca, percorrendo a árvore binária e muitos outros algoritmos.
Sim, realmente, a árvore de estrutura geral não é utilizada em lugar algum, a navegação é lenta e as opções de uso são pequenas.

Então, eu me questionei sobre isso e agora vou explicar como a árvore é construída. Portanto, idealmente, a estrutura da árvore geral deve armazenar três variáveis:

• um ponteiro para o filho mais velho
• um ponteiro para o irmão
• os dados que você pretende armazenar

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

Vamos declarar um ponteiro para a raiz:

Node *tree = NULL;

Devemos combinar de antemão como faremos a entrada dos nós, pois não se trata de uma árvore binária e cada nó pode ter quantos filhos quiser.

• + 2 (ou +ssbb 2) — inserção na árvore (para a árvore geral, o caminho é definido por uma string, onde r significa criar a raiz, s — ir para o filho mais velho, b — ir para o irmão);

Vou dar um exemplo:

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

O resultado será a seguinte árvore:

1
  2
    5
  3
    6
    7
  3

Primeiro, vamos criar uma função que realiza a adição de um nó, ou seja, aloca memória para o nó e retorna um ponteiro para esse nó (inicialmente desconectado).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // zeramos os ponteiros para irmãos e filhos, um nó independente que armazena o valor
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Também é necessário criar uma função que processa a string do caminho (+bs…). Sempre começamos o percurso a partir da raiz; se ela não foi criada, exibimos NULL (não podemos fazer nada). Se o nó não existir, precisamos criá-lo. Vamos para a função que cria a árvore e obtemos um ponteiro para a raiz.

Observe que Node ** tree passa a estrutura, em vez de copiá-la. Isso nos permite fazer modificações, o que não é possível com a declaração Node *tree.

Basicamente, devemos encontrar o ponteiro para o nó ao qual precisamos adicionar um filho:

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); // criando raiz
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // função que retorna o ponteiro para o filho
            continue;
          return NULL; // caso contrário, NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // retorna ponteiro para o irmão t
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // chegamos ao topo que queríamos
   // e agora vamos até o último filho dela,
   // para adicionar ao final da lista
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// se não houver filho, vamos criá-lo
      t->son = create_tree(value);
      return t->son;
    }
}

Dessa forma, construímos a árvore.

P.S. este é o meu primeiro artigo, então peço que não sejam muito rigorosos.

Fonte: habr.com