Visão geral da árvore, implementação e não apenas

Muitos provavelmente tentaram encontrar a construção de uma árvore geral, mas o mecanismo de pesquisa encontrou apenas binários ... A árvore de pesquisa binária, a travessia da árvore binária e muitos outros algoritmos.
Sim, de fato, a árvore geral não é usada em nenhum lugar, o desvio é lento, os casos de uso são pequenos.

Então, eu fiz essa pergunta e agora vou explicar como a árvore está sendo construída. Portanto, idealmente, a estrutura de uma árvore de forma geral deve armazenar três variáveis:

• ponteiro para o filho mais velho
• ponteiro para irmão
• dados que você vai armazenar

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

Declare um ponteiro para o topo:

 Node *tree = NULL; 

Devemos concordar com antecedência sobre como inserir os vértices, isso não é uma árvore binária e cada vértice pode ter filhos.

• + 2 (ou + ssbb 2) - inserção na árvore (para uma árvore geral, o caminho é especificado pela linha, onde r é a raiz, s é a transição para o filho mais velho, b é a transição para o irmão);

Vou dar um exemplo:

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

Como resultado, esta árvore será lançada:

 1 2 5 3 6 7 3 

Primeiro, crie uma função que adicione um vértice, ou seja, aloque memória para o vértice e passe um ponteiro para esse vértice (inicialmente não relacionado 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; } 

Você também deve criar uma função que processe a sequência do caminho (+ bs ...). Cada vez que iniciamos a travessia a partir da raiz, se não for criada, imprimimos NULL (não podemos fazer nada). Se não houver pico, devemos criá-lo. Vá para a função create tree e obtenha um ponteiro para a raiz.

Nota: Nó ** árvore passa estrutura, não copia. Isso nos permite alterar o que não pode ser feito, diferentemente da declaração da árvore Node *.

Em geral, devemos encontrar um ponteiro para o topo, 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] != '\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; } } 

Desta forma, construímos uma árvore.

PS é o meu primeiro artigo, por isso não julgue estritamente