Como implementar a árvore binária em C?

Uma árvore é um formato de dados comum para armazenar informações contidas hierarquicamente. Uma árvore é composta de nós ligados pelas bordas, com cada nó tendo seu nó pai e um ou vários nós filhos. Este artigo estuda e analisa árvores binárias e vê a implementação de árvores binárias Na programação C.

Árvore binária em C

Em c, um Árvore binária é uma instância de uma estrutura de dados de árvore com um nó pai que pode possuir um número máximo de dois nós filhos; 0, 1 ou 2 descendentes. Cada nó em um Árvore binária tem um valor próprio e dois ponteiros para seus filhos, um ponteiro para o filho esquerdo e o outro para a criança certa.

Declaração de árvore binária

A Árvore binária pode ser declarado em c usando um objeto chamado estrutura que descreve um dos nós na árvore.

Nó da estrutura
Datatype VAR_NAME;
Nó da estrutura* esquerda;
Nó da estrutura* à direita;
;

Acima está uma declaração de um Árvore binária Nó Nome como um nó. Ele possui três valores; um é a variável de armazenamento de dados e os outros dois são os ponteiros da criança. (Filho esquerdo e direito do nó pai).

Fatos da árvore binária

Mesmo para grandes conjuntos de dados, usando um Árvore binária torna a pesquisa mais fácil e rápida. O número de galhos de árvores não é limitado. Em contraste com uma matriz, árvores de qualquer tipo podem ser feitas e aumentadas com base no que é exigido de um indivíduo.

Implementação de árvores binárias em C

A seguir, é apresentado um guia passo a passo para implementar um Árvore binária em c.

Etapa 1: Declare uma árvore de pesquisa binária

Crie um nó de estrutura que tenha três tipos de dados, como dados, *esquerd_child e *right_child, onde os dados podem ser do tipo inteiro, e os nós *left_child e *right_child podem ser declarados como nulos ou não.

Nó da estrutura

int dados;
Nó da estrutura *Right_Child;
Nó da estrutura *esquerd_child;
;

Etapa 2: Crie novos nós na árvore de pesquisa binária

Crie um novo nó criando uma função que aceita um número inteiro como um argumento e fornece o ponteiro para o novo nó criado com esse valor. Use a função malloc () em C para alocação de memória dinâmica para o nó criado. Inicialize a criança esquerda e direita para nulo e devolver o nome do noden.

Nó da estrutura* Criar (dados do tipo de dados)

Nó da estrutura* nodename = MALLOC (sizeof (nó da estrutura));
nodename-> data = value;
nodename-> esquerd_child = nodename-> right_child = null;
retornar nodename;

Etapa 3: Insira filhos direito e esquerdo na árvore binária

Crie funções insert_left e insert_right que aceitarão duas entradas, que são o valor a ser inserido e o ponteiro para o nó ao qual ambas as crianças serão conectadas. Chame a função Criar para criar um novo nó e atribuir o ponteiro devolvido ao ponteiro esquerdo do filho esquerdo ou o ponteiro direito do filho direito do pai da raiz.

Nó da estrutura* insert_left (nó struct* root, dados de dados de dados)
raiz-> esquerda = create (dados);
retornar raiz-> esquerda;

Nó da estrutura* insert_right (nó de estrutura* root, dados do tipo de dados)
raiz-> direita = create (dados);
retornar raiz-> certo;

Etapa 4: Exibir nós de árvore binária usando métodos de travessia

Podemos exibir árvores usando três métodos de travessia em C. Esses métodos atravessados ​​são:

1: Traversal de pré-encomenda

Neste método de travessia, seguiremos os nós em uma direção de parent_node-> left_child-> right_child.

void pre_order (nó * root)
if (root)
printf ("%d \ n", raiz-> dados);
display_pre_order (root-> esquerda);
display_pre_order (root-> à direita);

2: Traversal de pós-ordem

Neste método de travessia, passaremos pelos nós em uma direção do esquerd_child-> direita_child-> parent_node->.

void display_post_order (nó * root)
if (binary_tree)
display_post_order (root-> esquerda);
display_post_order (root-> à direita);
printf ("%d \ n", raiz-> dados);

3: Traversal na ordem

Neste método de travessia, seguiremos os nós em uma direção de esquerd_node-> root_child-> right_child.

void display_in_order (nó * root)
if (binary_tree)
display_in_order (root-> esquerda);
printf ("%d \ n", raiz-> dados);
display_in_order (root-> à direita);

Etapa 5: Execute a exclusão na árvore binária

Podemos excluir o criado Árvore binária Excluindo as duas crianças com a função do nó pai em C da seguinte forma.

void delete_t (nó * root)
if (root)
delete_t (root-> esquerda);
delete_t (root-> à direita);
livre (raiz);

C Programa de Árvore de Pesquisa Binária

A seguir, é apresentada a implementação completa da árvore de pesquisa binária na programação C:

#incluir
#incluir
Nó da estrutura
int valor;
Nó da estrutura * esquerda, * direita;
;
Nó da estrutura * node1 (int dados)
Nó da estrutura * tmp = (nó da estrutura *) Malloc (sizeof (nó da estrutura));
tmp -> value = dados;
tmp -> esquerda = tmp -> direita = null;
retornar tmp;

impressão void (nó de estrutura * root_node) // exibindo os nós!

if (root_node != Null)
imprimir (root_node -> esquerda);
printf ("%d \ n", root_node -> value);
print (root_node -> direita);


Nó da estrutura * insert_node (nó de estrutura * nó, int dados) // inserindo nós!

if (node ​​== null) retornar node1 (dados);
if (dados < node -> valor)
nó -> esquerda = insert_node (nó -> esquerda, dados);
else if (dados> nó -> value)
nó -> direita = insert_node (nó -> à direita, dados);

Nó de retorno;

int main ()
printf ("C Implementação da árvore de pesquisa binária!\ n \ n ");
nó de estrutura * pai = nulo;
pai = insert_node (pai, 10);
insert_node (pai, 4);
insert_node (pai, 66);
insert_node (pai, 45);
insert_node (pai, 9);
insert_node (pai, 7);
impressão (pai);
retornar 0;

No código acima, declaramos primeiro um nó usando estrutura. Então inicializamos um novo nó como “node1”E alocar memória dinamicamente usando Malloc () Em C com dados e dois ponteiros tipo crianças usando o nó declarado. Depois disso, exibimos o nó por printf () função e chame no principal() função. Então o insertion_node () A função é criada, onde se os dados do nó forem nulos, então node1 é aposentado, caso contrário, os dados são colocados no nó(pai) da criança esquerda e direita. O programa começa a executar a partir do principal() função, que gera um nó usando alguns nós de amostra quando crianças e depois usa métodos de travessia em ordem para imprimir o conteúdo do nó.

Saída

Conclusão

As árvores são frequentemente empregadas para manter os dados em uma forma não linear. Árvores binárias são tipos de árvores onde cada nó (pai) tem dois filhos da criança esquerda e a criança certa. A Árvore binária é um método versátil de transferência e armazenamento de dados. É mais eficiente em comparação com a lista vinculada em C. No artigo acima, vimos o conceito de um Árvore binária com a implementação passo a passo de um Árvore de pesquisa binária em c.