Árvore binária
Publicado por Marcos (última atualização em 14/01/2013)
[ Hits: 26.561 ]
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; }
MeikeNeime - Programa gerador de nomes aleatórios
Conciliando o uso da ZRAM e SWAP em disco na sua máquina
Servidor de Backup com Ubuntu Server 24.04 LTS, RAID e Duplicati (Dell PowerEdge T420)
Visualizar câmeras IP ONVIF no Linux sem necessidade de instalar aplicativos
Realizar overclock no Miyoo Mini (plus ou normal)
Otimização de memória para máquinas modestas
linux mint reconhece microfone de lapela como fone de ouvido sem micro... (0)
Dúvidas sobre a originalidade de conteúdos online (10)
Erro de interface de Rede no Virt Manager dentro Debian 13 KDE (12)
Monitoramento pfsense com zabbix (3)
Google Crhome não abre desde que eu atualizei pelo "program... (13)