Árvore Binária em C
Em C, um árvore binária é uma instância de uma estrutura de dados em árvore com um nó pai que pode possuir um número máximo de dois nós filhos; 0, 1 ou 2 nós 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 outro para o filho direito.
Declaração de Árvore Binária
A árvore binária pode ser declarado em C usando um objeto chamado estrutura que representa um dos nós da árvore.
estrutura nó {
tipo de dados var_name ;
estrutura nó * esquerda ;
estrutura nó * certo ;
} ;
Acima está uma declaração de um árvore binária nome do nó como um nó. Ele contém três valores; um é a variável de armazenamento de dados e os outros dois são os ponteiros para o filho. (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 árvore binária em C
A seguir, um guia passo a passo para a implementação de um árvore binária em C.
Etapa 1: declarar uma árvore de pesquisa binária
Crie um nó struct que tenha três tipos de dados, como dados, *left_child e *right_child, em que os dados podem ser do tipo inteiro e os nós *left_child e *right_child podem ser declarados como NULL ou não.
estrutura nó{
int dados ;
estrutura nó * filho_direito ;
estrutura nó * filho_esquerdo ;
} ;
Etapa 2: criar novos nós na árvore de pesquisa binária
Crie um novo nó criando uma função que aceite um número inteiro como argumento e forneça o ponteiro para o novo nó criado com esse valor. Use a função malloc() em C para alocação dinâmica de memória para o nó criado. Inicialize o filho esquerdo e direito como NULL e retorne o nodeName.
estrutura nó * criar ( dados de tipo de dados )
{
estrutura nó * nodeName = malloc ( tamanho de ( estrutura nó ) ) ;
nodeName -> dados = valor ;
nodeName -> filho_esquerdo = nodeName -> filho_direito = NULO ;
retornar nodeName ;
}
Passo 3: Inserir Filhos Direito e Esquerdo na Árvore Binária
Crie as 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 os dois filhos serão conectados. Chame a função create para criar um novo nó e atribua o ponteiro retornado ao ponteiro esquerdo do filho esquerdo ou ao ponteiro direito do filho direito do pai raiz.
estrutura nó * inserir_esquerda ( estrutura nó * raiz , dados de tipo de dados ) {raiz -> esquerda = criar ( dados ) ;
retornar raiz -> esquerda ;
}
estrutura nó * inserir_direito ( estrutura nó * raiz , dados de tipo de dados ) {
raiz -> certo = criar ( dados ) ;
retornar raiz -> certo ;
}
Etapa 4: exibir os nós da árvore binária usando métodos de travessia
Podemos exibir árvores usando três métodos de passagem em C. Esses métodos de passagem são:
1: Passagem de pré-encomenda
Neste método de travessia, iremos percorrer os nós em uma direção de parent_node->left_child->right_child .
vazio pedido antecipado ( nó * raiz ) {se ( raiz ) {
printf ( '%d \n ' , raiz -> dados ) ;
display_pre_order ( raiz -> esquerda ) ;
display_pre_order ( raiz -> certo ) ;
}
}
2: Passagem pós-ordem
Neste método de travessia, iremos percorrer os nós em uma direção a partir do left_child->right_child->parent_node-> .
vazio display_post_order ( nó * raiz ) {se ( binary_tree ) {
display_post_order ( raiz -> esquerda ) ;
display_post_order ( raiz -> certo ) ;
printf ( '%d \n ' , raiz -> dados ) ;
}
}
3: Percurso em ordem
Neste método de travessia, iremos percorrer os nós em uma direção de left_node->root_child->right_child .
vazio display_in_order ( nó * raiz ) {se ( binary_tree ) {
display_in_order ( raiz -> esquerda ) ;
printf ( '%d \n ' , raiz -> dados ) ;
display_in_order ( raiz -> certo ) ;
}
}
Etapa 5: executar a exclusão na árvore binária
Podemos excluir o criado árvore binária excluindo ambos os filhos com a função do nó pai em C da seguinte maneira.
vazio delete_t ( nó * raiz ) {se ( raiz ) {
delete_t ( raiz -> esquerda ) ;
delete_t ( raiz -> certo ) ;
livre ( raiz ) ;
}
}
Programa C de Árvore Binária de Busca
A seguir está a implementação completa da árvore de busca binária na programação C:
#include#include
estrutura nó {
int valor ;
estrutura nó * esquerda , * certo ;
} ;
estrutura nó * nó1 ( int dados ) {
estrutura nó * tmp = ( estrutura nó * ) malloc ( tamanho de ( estrutura nó ) ) ;
tmp -> valor = dados ;
tmp -> esquerda = tmp -> certo = NULO ;
retornar tmp ;
}
vazio imprimir ( estrutura nó * root_node ) // exibindo os nós!
{
se ( root_node != NULO ) {
imprimir ( root_node -> esquerda ) ;
printf ( '%d \n ' , root_node -> valor ) ;
imprimir ( root_node -> certo ) ;
}
}
estrutura nó * insert_node ( estrutura nó * nó , int dados ) // inserindo nós!
{
se ( nó == NULO ) retornar nó1 ( dados ) ;
se ( dados < nó -> valor ) {
nó -> esquerda = insert_node ( nó -> esquerda , dados ) ;
} outro se ( dados > nó -> valor ) {
nó -> certo = insert_node ( nó -> certo , dados ) ;
}
retornar nó ;
}
int principal ( ) {
printf ( 'Implementação C da Árvore de Busca Binária! \n \n ' ) ;
estrutura nó * pai = NULO ;
pai = insert_node ( pai , 10 ) ;
insert_node ( pai , 4 ) ;
insert_node ( pai , 66 ) ;
insert_node ( pai , Quatro cinco ) ;
insert_node ( pai , 9 ) ;
insert_node ( pai , 7 ) ;
imprimir ( pai ) ;
retornar 0 ;
}
No código acima, primeiro declaramos um nó usando estrutura . Em seguida, inicializamos um novo nó como “ nó1 ” e alocar memória dinamicamente usando malloc() em C com dados e dois ponteiros digite filhos usando o nó declarado. Depois disso, exibimos o nó por printf() função e chame-a no principal() função. Então o insert_node() função é criada, onde se os dados do nó são NULL então nó1 é retirado, caso contrário, os dados são colocados no nó (pai) do filho esquerdo e direito. O programa inicia a execução a partir do principal() função, que gera um nó usando alguns nós de amostra como filhos e, em seguida, usa métodos de travessia em ordem para imprimir o conteúdo do nó.
Saída
Conclusão
As árvores são freqüentemente empregadas para manter os dados de forma não linear. árvores binárias são tipos de árvores onde cada nó (pai) tem dois descendentes o filho esquerdo e o filho direito. A árvore binária é um método versátil de transferência e armazenamento de dados. É mais eficiente em comparação com a lista encadeada 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.