Árvore binária
Publicado por Marcos (última atualização em 14/01/2013)
[ Hits: 26.290 ]
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; }
Exibe quantos números perfeitos foram digitados
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Como renomear arquivos de letras maiúsculas para minúsculas
Imprimindo no formato livreto no Linux
Vim - incrementando números em substituição
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Vou voltar moderar conteúdos de Dicas e Artigos (1)
SysAdmin ou DevOps: Qual curso inicial pra essa área? (3)
É cada coisa que me aparece! - não é só 3% (3)
Melhorando a precisão de valores flutuantes em python[AJUDA] (5)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta