Arvore Binaria - Conceitos e Definições para Estudantes

Árvore Binária Profa Rachel Reis Árvore binária definição Uma árvore binária T é um conjunto finito de nós com as seguintes propriedades O conjunto é vazio T Ø ou O conjunto é formado por uma raiz r e por duas subárvores binárias distintas TL e TR T r TL TR Árvore binária exemplo raiz Árvore binária T Subárvore direita Subárvore esquerda Máximo 7 elementos Número máximo de nós de uma árvore binária de altura h maior ou igual a zero 2h 1 23 1 7 Exemplo 5 elementos Árvore binária fórmulas Número máximo de folhas 2h1 231 22 4 Exemplo 2 folhas Máximo 4 folhas Árvore binária fórmulas Árvore binária conceitos Uma árvore binária pode ser estritamente binária Cada nó não terminal ou não tem filhos ou tem tanto a subárvore esquerda quanto a direita Árvore estritamente binária Cada nó não terminal ou não tem filhos ou tem tanto a subárvore esquerda quanto a direita Subárvore esquerda Árvore estritamente binária Árvore estritamente binária Cada nó não terminal ou não tem filhos ou tem tanto a subárvore esquerda quanto a direita Subárvore direita Árvore estritamente binária Cada nó não terminal ou não tem filhos ou tem tanto a subárvore esquerda quanto a direita Árvore estritamente binária Cada nó não terminal ou não tem filhos ou tem tanto a subárvore esquerda quanto a direita Subárvore esquerda Árvore estritamente binária Cada nó não terminal ou não tem filhos ou tem tanto a subárvore esquerda quanto a direita Subárvore direita Árvore binária definição Uma árvore binária pode ser estritamente binária completa Árvore binária completa É uma árvore estritamente binária Árvore binária completa É uma árvore estritamente binária onde todos os nós folhas Árvore binária completa É uma árvore estritamente binária onde todos os nós folhas se encontram ou no último ou no penúltimo nível da árvore Nível 2 Nível 1 Nível 3 Nível 4 Árvore binária conceitos Uma árvore binária pode ser estritamente binária completa cheia Árvore binária cheia Todos os nós possuem exatamente duas subárvores exceto os nós do último nível Nível 1 Nível 2 Nível 3 Árvore binária Implementação TADs do tipo árvore podem ser implementadas Representação estática array Representação dinâmica ponteiros Representação Estática define TAMMAX 10 typedef struct sArvore tipo arvTAMMAX Arvore Representação Estática Os nós são armazenados no vetor por nível Funcionamento se um nó está na posição de índice i seus filhos diretos serão colocados nas posições 2i 1 se o nó estiver à esquerda 2i 2 se o nó estiver à direita Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 Nível 1 A 2i 1 nó da esquerda 2i 2 nó da direita Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 A 2i 1 nó da esquerda 2i 2 nó da direita Nível 2 2 x 0 1 1 Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 A 2i 1 nó da esquerda 2i 2 nó da direita B Nível 2 2 x 0 2 2 Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 A 2i 1 nó da esquerda 2i 2 nó da direita B C Nível 2 Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 A 2i 1 nó da esquerda 2i 2 nó da direita B C Nível 3 Nível 3 Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 A 2i 1 nó da esquerda 2i 2 nó da direita B C 2 x 1 1 3 D Nível 3 Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 A 2i 1 nó da esquerda 2i 2 nó da direita B C 2 x 2 1 5 D F Nível 3 Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 A 2i 1 nó da esquerda 2i 2 nó da direita B C 2 x 2 2 6 D F G Representação Estática Exemplo 0 1 2 3 4 5 6 7 8 10 9 A B C D F G Desvantagem espaços vagos se a árvore não é completa por níveis ou se sofrer eliminação Árvore binária Implementação TADs do tipo árvore podem ser implementadas Representação estática array Representação dinâmica ponteiros typedef struct sNo TIPO info struct sNo esq struct sNo dir NO typedef struct sArvore NO ptRaiz Deque ptRaiz Representação Dinâmica esq info dir Representação Dinâmica A B C D E F G Árvores Binárias percursotravessia Objetivo percorrer uma árvore visitando cada nó uma única vez Um percurso gera uma sequência linear de nós Não existe percurso único para árvores binárias ou não Visitar um nó pode ser Imprimir os itens de uma árvore Atualizar o campo de um ou mais nós Pesquisar por um item Etc Três percursos básicos Préordem preorder Emordem inorder Pósordem postorder Árvores Binárias percursotravessia Passos 1 Visitar a raiz da árvore 2 Visitar recursivamente a subárvore esquerda 3 Visitar recursivamente a subárvore direita Percurso em Árvore PréOrdem A B C Visitar Imprimir A B C PréOrdem Exemplo void preordemNO raiz if raiz NULL visitaraiz preordemraizesq preordemraizdir void preordemNO raiz A if raiz NULL visitaraiz preordemraizesq preordemraizdir raiz A B C void preordemNO raiz A if raiz NULL visitaraiz preordemraizesq preordemraizdir TRUE raiz A B C void preordemNO raiz A if raiz NULL imprimirraiz preordemraizesq preordemraizdir A raiz A B C void preordemNO raiz A if raiz NULL imprimirraiz preordemraizesq B preordemraizdir A raiz A B C void preordemNO raiz A B if raiz NULL imprimirraiz preordemraizesq B preordemraizdir A raiz A B C raiz void preordemNO raiz A B if raiz NULL imprimirraiz preordemraizesq B preordemraizdir A TRUE raiz A B C raiz void preordemNO raiz A B if raiz NULL imprimirraiz preordemraizesq B preordemraizdir A B raiz A B C raiz void preordemNO raiz A B if raiz NULL imprimirraiz preordemraizesq NULL preordemraizdir A B raiz A B C raiz void preordemNO raiz A B NULL if raiz NULL imprimirraiz preordemraizesq BD preordemraizdir A B raiz raiz A B C raiz void preordemNO raiz A B NULL if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B FALSE raiz raiz A B C raiz void preordemNO raiz A B if raiz NULL imprimirraiz preordemraizesq ABD preordemraizdir A B raiz raiz A B C raiz void preordemNO raiz A B if raiz NULL imprimirraiz preordemraizesq preordemraizdir NULL A B raiz A B C raiz void preordemNO raiz A B NULL if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B raiz A B C raiz raiz void preordemNO raiz A B NULL if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B raiz A B C raiz raiz FALSE raiz void preordemNO raiz A B if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B raiz A B C raiz raiz void preordemNO raiz A if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B raiz A B C void preordemNO raiz A if raiz NULL imprimirraiz preordemraizesq preordemraizdir C A B A B C raiz void preordemNO raiz A C if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B raiz A B C raiz void preordemNO raiz A C if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B TRUE raiz A B C raiz void preordemNO raiz A C if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B C raiz A B C raiz void preordemNO raiz A C if raiz NULL imprimirraiz preordemraizesq NULL preordemraizdir A B raiz A B C C raiz void preordemNO raiz A C NULL if raiz NULL imprimirraiz preordemraizesqNULL preordemraizdir A B raiz A B C raiz C raiz void preordemNO raiz A C NULL if raiz NULL imprimirraiz preordemraizesqNULL preordemraizdir A B raiz A B C raiz FALSE C raiz void preordemNO raiz A C if raiz NULL imprimirraiz preordemraizesqNULL preordemraizdir A B raiz A B C raiz C raiz void preordemNO raiz A C if raiz NULL imprimirraiz preordemraizesq preordemraizdir NULL A B A B C raiz C raiz void preordemNO raiz A C NULL if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B raiz A B C raiz C raiz void preordemNO raiz A C NULL if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B FALSE A B C raiz C raiz raiz raiz void preordemNO raiz A C if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B A B C C raiz raiz raiz void preordemNO raiz A if raiz NULL imprimirraiz preordemraizesq preordemraizdir A B C A B C raiz A B C A B C raiz Saída linear préordem PréOrdem Implementação void preordemNO r if raiz NULL visitaraiz preordemraizesq preordemraizdir Imprima o percurso em préordem para a árvore binária abaixo Exercício 1 Passos 1 Visitar recursivamente a subárvore esquerda 2 Visitar a raiz da árvore 3 Visitar recursivamente a subárvore direita Percurso em Árvore EmOrdem A B C Visitar Imprimir B A C EmOrdem Implementação void emordemNO r if raiz NULL emordemraizesq visitaraiz emordemraizdir Imprima o percurso em emordem para a árvore binária abaixo Exercício 2 Passos 1 Visitar recursivamente a subárvore esquerda 2 Visitar recursivamente a subárvore direita 3 Visitar a raiz da árvore Percurso em Árvore PósOrdem A B C Visitar Imprimir B C A PósOrdem Implementação void posordemNO r if raiz NULL posordemraizesq posordemraizdir visitaraiz Imprima o percurso em pósordem para a árvore binária abaixo Exercício 3 Árvores Binárias percursotravessia A B C Préordem Emordem Pósordem B C A B A C A B C Referências Bibliográficas Ascencio A F G Araújo G S de 2010 Estruturas de Dados algoritmos análise da complexidade e implementações em JAVA e C São Paulo Pearson Prentice Hall Forbellone A L V Eberspacher H F 2005 Lógica de Programação A construção de algoritmos e estruturas de dados 3ª edição São Paulo Pearson Prentice Hall