Árvore binária
Publicado por Marcos (última atualização em 14/01/2013)
[ Hits: 26.379 ]
O objetivo é falar da forma mais clara e resumida sobre árvores binárias de busca, e com isso auxiliar outros aspirantes a programadores (assim com eu) a conseguirem dar mais um passo nessa difícil jornada.
Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.
Uma grande vantagem de uma árvore binária é que ela propicia pesquisas muito rápidas.
Grande vantagem: flexibilidade e eficiência quando usadas em programas de gerenciamento de banco de dados.
O código que utilizo como exemplo apenas captura as informações fornecidas pelo usuário e as armazena numa árvore binária e na sequência percorre a árvore das três formas possíveis exibindo os valores armazenados.
Cada árvore possui:
• Raiz ou nó e várias subárvores
• As subárvores também são um árvore
• Os nós que não possuem nenhum filho, são chamados de folha
• O grau de uma árvore diz respeito ao número de máximo de subárvore em cada nós da árvore
• A altura ou tamanho da árvore diz respeito a quantidade de níveis da árvore
Numa árvore binária cada nó tem no máximo 2 filhos
Em cada nó temos a informação que será a raiz e dois ponteiros, um para o filho esquerdo e outro para o filho direito
A implementação de uma árvore binária é baseado no conceito de listas encadeadas.
Uma árvore binária com raiz R é uma árvore binária de busca (ABB) se:
1. Se a chave de cada nó da subárvore a esquerda de R é menor do que a chave do nó R;
2. A chave de cada nó da subárvore a direita for maior do que a chave do nó R;
3. As subárvores esquerda e direita também devem ser abb's.
Etapas de uma implementação:
a. Uma struct que será o molde da nossa árvore
b. Criar um ponteiro do tipo desta struct recém criada e uma variável do tipo inteiro que armazenará a quantidade de elementos inseridos na árvore (devem ser variáveis globais)
c. Um método construtor (onde o ponteiro receberá NULL e o contador receberá zero)
d. Método destrutor (devemos liberar a memória alocada)
e. Método que verifica se abb está vazia (essa condição é satisfeita quando a raiz apontar para NULL)
f. Método que verifica a quantidade de elementos inseridos
g. Método de inserção
h. Método de pesquisa
i. Método de busca:
i. Em ordem:subarvore esquerda, raiz, subarvore direita
ii. Pré-ordem: raiz, subarvore esquerda, subarvore direita
iii. Pós-ordem: subarvore esquerda, subarvore direita, raiz
j. Método de exclusão
Aguardo sugestões.
#include <stdio.h> #include <stdlib.h> #include <ctype.h> struct arvore{ char item; arvore *esq,*dir; }; arvore *Raiz; int contador; void arvore_Construtor(){ Raiz=NULL; contador=0; } void arvore_Destrutor(arvore *&Raiz){ if(Raiz!=NULL){ arvore_Destrutor(Raiz->esq); arvore_Destrutor(Raiz->dir); free(Raiz); Raiz=NULL; } } bool arvore_Vazia(){ return Raiz==NULL; } int arvore_Tamanho(){ return contador; } bool arvore_Inserir(char letra, arvore *&Raiz){ if(Raiz==NULL){ if((Raiz=(arvore *) malloc(sizeof(arvore)))==NULL) return false; else{ Raiz->item=letra; Raiz->esq=Raiz->dir=NULL; contador++; return true; } } else{ if(letra<Raiz->item) return arvore_Inserir(letra,Raiz->esq); else{ if(letra>Raiz->item) return arvore_Inserir(letra,Raiz->dir); else return false;//letra já existe na árvore } } } //percorre a árvore void arvore_Busca_em_Ordem(arvore *&Raiz){ if(Raiz!=NULL){ arvore_Busca_em_Ordem(Raiz->esq); printf(" %c",Raiz->item); arvore_Busca_em_Ordem(Raiz->dir); } } //percorre a árvore void arvore_Busca_pre_Ordem(arvore *&Raiz){ if(Raiz!=NULL){ printf(" %c",Raiz->item); arvore_Busca_pre_Ordem(Raiz->esq); arvore_Busca_pre_Ordem(Raiz->dir); } } //percorre a árvore void arvore_Busca_pos_Ordem(arvore *&Raiz){ if(Raiz!=NULL){ arvore_Busca_pos_Ordem(Raiz->esq); arvore_Busca_pos_Ordem(Raiz->dir); printf(" %c",Raiz->item); } } int main(){ char x,opcao; arvore_Construtor(); do{ printf("\nInforme a letra: "); setbuf(stdin,NULL); scanf("%c",&x); arvore_Inserir(x,Raiz); printf("\nMais dados? S/N: "); setbuf(stdin,NULL); scanf("%c",&opcao); }while(toupper(opcao)!='N'); // tamanho da árvore printf("\nQuantidade de elementos: %d\n",contador); // impressão em ordem printf("\nArvore em ordem:\n"); arvore_Busca_em_Ordem(Raiz); printf("\n\n"); // impressão em pré-ordem printf("Arvore em pre-ordem:\n"); arvore_Busca_pre_Ordem(Raiz); printf("\n\n"); // impressão em pós-ordem printf("Arvore em pos-ordem:\n"); arvore_Busca_pos_Ordem(Raiz); printf("\n\n"); // devolvendo memóra alocada ao sistema operacional arvore_Destrutor(Raiz); return 0; }
Raizes reais e complexas de uma equação de 2º grau
Ler N números e ver qual é o maior
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
VMs e Interfaces de Rede desapareceram (11)
Instalação do drive do adaptador wiffi (7)