Árvore Binária com a Linguagem C

Em Ciência da Computação, uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz. O objetivo desta árvore é estruturar os dados de forma flexível, permitindo pesquisa binária.

Árvore Binária

  • Nós – são todos os itens guardados na árvore;
  • Raiz – é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8);
  • Filhos – são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3);
  • Pais – são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14);
  • Folhas – são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13).

A operação de busca em uma árvore binária por um determinado valor, pode ser feita de maneira recursiva ou interativa. (fiz a abordagem recursiva).

A busca inicia-se no nó raiz, se o valor contido na raiz não for o desejado, verificamos se o valor é maior ou menor que o nó raiz. Caso o valor seja menor que o nó raiz, a busca continua pelo seu filho menor, ou seja, pelo filho da esquerda, mas, caso o valor seja maior a busca continua pelo filho da direita, até que se encontre o valor desejado ou a busca chegue em um nó folha (valor não encontrado).

A inserção de um novo valor é praticamente uma busca na árvore pois, precisamos percorrer toda a árvore até chegarmos em um nó folha correspondente. Se o valor a ser inserido for maior que o raiz, seguimos pelo filho da direita, se for menor seguimos pelo filho da esquerda, até chegarmos em um nó que mantenha a ordenação da árvore.

A operação remoção começa a complicar um pouco. Temos 3 casos diferentes:

  1. Exclusão de um nó folha;
  2. Exclusão de um nó com 1 filho;
  3. Exclusão de um nó com 2 filhos;

 

Para a exclusão de um nó folha, precisamos somente removê-lo da árvore.

Árvore Binária - Remover Folha

Para a exclusão de um nó com 1 filho, o filho apenas sobe para a posição do pai.

Árvore Binária - Remover nó com 1 filho

Para a remoção de um nó com 2 filhos, temos duas maneiras diferentes de trabalhar:

  • Usando o maior nó da sub-árvore à esquerda;
  • Usando o menor nó da sub-árvore à direita;

Estas duas maneiras são apenas definições de projeto, possuem a mesma complexidade e tempo de busca.

No exemplo abaixo, para remover o 3 usando a definição do menor nó da sub-árvore à direita, pesquisamos pelo menor nó à partir do 6 que no caso será o 4.

Árvore Binária - Remover nó, direita

Agora, usando a definição do maior nó da subárvore à esquerda, removeremos o 8, o resultado será o seguinte:

Árvore Binária - Remover nó, esquerda

Apresentando alguns códigos, lembrando que ao final desta postagem você poderá fazer o download de um projeto que foi desenvolvido utilizando o Dev-C++, com a linguagem C.

Função Inserir em árvore binária:

Função remover da árvore binária:

Função minimo, retorna o nó com valor minímo:

Função maximo, retorna o nó com o valor máximo:

Função para buscar elemento na árvore binária:

 

Caso você queira realizar o *download deste projeto (árvore binária em C)  -> Árvore Binária com a Linguagem C (2 downloads) .

Atenção, para fazer o download você precisa se registrar/login neste site.

 

Obrigado por ler este post.
Curta e compartilhe se se você gostou!

Gostaria de ver a versão inglesa deste post?
Clique na bandeira inglesa -> United-Kingdom

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios são marcados com *

 
Translate »