May 11 2011

Árvore Binária com a Linguagem C

Category: C ANSI — thalessuzuki @ 08:26

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.

ArvoreBinaria_01

  • 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:

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

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

ArvoreBinaria_02

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

ArvoreBinaria_03

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.

ArvoreBinaria_04

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

ArvoreBinaria_05

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:

view plaincopy to clipboardprint
  1. void inserir(tArv *t, int dado){   
  2.   int ok;   
  3.   // se t aponta para null, a inserção é na raiz...   
  4.   if (*t == NULL) {    
  5.     *t = (tnoarv *) malloc(sizeof(tnoarv));   
  6.     if (*t == NULL) return;   
  7.     (*t)->esq = NULL;   
  8.     (*t)->dir = NULL;   
  9.     (*t)->info = dado;   
  10.   }   
  11.   // Se o dado a ser inserido for menor que o nó atual, recursividade à esquerda   
  12.   if (dado < (*t)->info) {   
  13.      inserir(&((*t)->esq), dado);   
  14.   }   
  15.   else{   
  16.     // Se o dado a ser inserido for menor que o nó atual, recursividade à direita   
  17.     if (dado > (*t)->info) {               
  18.        inserir(&((*t)->dir), dado);   
  19.     }   
  20.   }   
  21. }  

 

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

 

view plaincopy to clipboardprint
  1. void remover(tArv *raiz, int valor){   
  2.     tArv aux;   
  3.     if(!arvore_vazia(*raiz)){   
  4.        // se o valor que será removido for menor que o nó atual,   
  5.        if(valor < (*raiz)->info){    
  6.            remover(&((*raiz)->esq), valor); // faz recursividade á esquerda   
  7.        }else{   
  8.             // se o valor que será removido for maior que o nó atual,   
  9.             if(valor > (*raiz)->info){    
  10.                  remover(&((*raiz)->dir), valor); // faz recursividade á direita.   
  11.              }else{ // encontrou   
  12.                 // quando o nó a ser removido for encontrado,   
  13.                 if( !arvore_vazia((*raiz)->esq) && !arvore_vazia((*raiz)->dir) ){    
  14.                      // verificamos se os nós filhos da esquerda e direita não são null.   
  15.                      // se não forem null, buscamos o menor nó a partir do nó da direita.   
  16.                      aux = minimo((*raiz)->dir);    
  17.                      (*raiz)->info = (aux->info);   
  18.                      remover(&(*raiz)->dir, (*raiz)->info);   
  19.                 }else{    
  20.                        // caso os nó da direita e da esqueda, ou somente o da direita for null,    
  21.                        // precisamos apenas remover   
  22.                        aux = *raiz;    
  23.                        // o nó atual e fazer ajustar os ponteiros    
  24.                        if(arvore_vazia((*raiz)->esq)){    
  25.                            // se o nó da esquerda for vazio   
  26.                            // o nó pai do atual, apontará para o filho da direita do nó atual.   
  27.                            *raiz = (*raiz)->dir;   
  28.                        }    
  29.                        else {   
  30.                             // se o nó da esquerda não for vazio.   
  31.                             // o nó pai do atual, apontará para o filho da esquerda do nó atual.   
  32.                             *raiz = (*raiz)->esq;                          
  33.                        }   
  34.                 free(aux);   
  35.                 }   
  36.             }        
  37.        }    
  38.     }     
  39. }  

 

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

view plaincopy to clipboardprint
  1. tArv minimo(tArv T){// procura o nó com valor mínimo   
  2.     if(arvore_vazia(T)){   
  3.        return NULL;   
  4.     }else{   
  5.           if( arvore_vazia(T->esq) ){   
  6.               return T;   
  7.           }else{   
  8.               return minimo(T->esq);   
  9.           }   
  10.     }   
  11. }  

 

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

view plaincopy to clipboardprint
  1. tArv maximo(tArv T){// procura o nó com valor máximo   
  2.      if( !arvore_vazia(T) ){   
  3.        while( !arvore_vazia(T->dir) ){   
  4.           T = T->dir;   
  5.        }   
  6.      }   
  7.        return T;   
  8. }  

 

Função para buscar elemento na árvore binária:
view plaincopy to clipboardprint
  1. //=======================================================================   
  2. // A função pesquisa nos nós da árvore o valor passado como parâmetro,    
  3. // caso o valor esteja na árvore, ela retorna este nó que está o valor.   
  4. tArv busca_elemento(tArv t, int dado){   
  5.   
  6.      tArv achou;   
  7.      if (arvore_vazia(t)) return NULL;   
  8.      if (t->info == dado) return t;   
  9.          achou = busca_elemento(t->esq, dado);   
  10.      if (arvore_vazia(achou))   
  11.          achou = busca_elemento(t->dir, dado);   
  12.      return achou;   
  13. }  

Caso você queira realizar o download deste projeto (árvore binária em C)  -> Árvore.zip (13.07 kb).

Fico por aqui e até a próxima.

 

Lança o teu cuidado sobre o SENHOR, e ele te susterá; não permitirá jamais que o justo seja abalado. (Salmos 55:22)

Tags: , , , , ,

Comments

1.
trackback DotNetKicks.com says:
Wednesday, May 11, 2011 at 9:25 AM

Binary Tree with Language C

You've been kicked (a good thing) - Trackback from DotNetKicks.com

2.
pingback thiagosatoshisuzuki.wordpress.com says:
Wednesday, May 11, 2011 at 9:31 AM

Pingback from thiagosatoshisuzuki.wordpress.com

Árvore Binária com a Linguagem C « Thiago Satoshi Suzuki

3.
Italo Italo Brazil says:
Friday, September 09, 2011 at 3:32 PM

foi muito importante para mim esse post, vlw ajudou no meu trabalho : )

4.
eduardo eduardo says:
Monday, October 24, 2011 at 11:30 AM

Muito bom meus parabens pelo projeto.

5.
Taty Taty Brazil says:
Tuesday, October 25, 2011 at 5:13 PM

Post EXCELENTE !! brigadão, me ajudou demais LaughingD

6.
Eduardo Eduardo Brazil says:
Thursday, November 17, 2011 at 10:27 AM

Muito bom esse trabalho que voces prestam pois, ajudam as pessoas que gostam de programação a desenvolver su lógica e seu aprendizado com exemplos corretos e executáveis...

7.
Murilo Campos Murilo Campos Brazil says:
Tuesday, November 22, 2011 at 7:25 AM

Muito bom conteúdo! Ajudou muito!

8.
Ricardo Ramos Ricardo Ramos Brazil says:
Tuesday, May 22, 2012 at 11:30 AM

Eu o parabenizo pelo codigo. Voce fez um codigo que era suposto ser complexo parecer simples e com uma interface que eu nunca tinha visto antes em C. Muito obrigado.

9.
Ricardo Ramos Ricardo Ramos Brazil says:
Tuesday, May 22, 2012 at 11:30 AM

Eu o parabenizo pelo codigo. Voce fez um codigo que era suposto ser complexo parecer simples e com uma interface que eu nunca tinha visto antes em C. Muito obrigado.

Add comment


(Will show your Gravatar icon)

  Country flag

biuquote
  • Comment
  • Preview
Loading