Árvores Binárias

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Estrutura de Dados II
ÁRVORES BINÁRIAS
PROF. MSC. ROMUERE SILVA 1
Livro Base
PROF. MSC. ROMUERE SILVA 2
Introdução: Árvore
É um conjunto de nós tal que:
◦ Existe um nó r, denominado raiz, com zero ou mais sub-árvores, cujas raízes estão ligadas a r
◦ Os nós raízes destas sub-árvores são os filhos de r;
◦ Os nós internos da árvore são os nós com filhos;
◦ as folhas ou nós externos da árvore são os nós sem filho;
PROF. MSC. ROMUERE SILVA 3
Árvore binária
Conceito: uma árvore em que cada nó tem zero, um ou dois filhos;
Uma árvore binária é:
◦ uma árvore vazia; ou
◦ um nó raiz com duas sub-árvores:
◦ a sub-árvore da direita (sad);
◦ a sub-árvore da esquerda (sae).
PROF. MSC. ROMUERE SILVA 4
Árvore binária: exemplo
Árvores binárias representando expressões aritméticas:
◦ nós folhas representam operandos
◦ nós internos operadores
◦ exemplo: (3+6)*(4-1)+5
PROF. MSC. ROMUERE SILVA 5
Árvore binária: Notação textual
A árvore vazia é representada por <>
Árvores não vazias por <raiz sae sad>
Exemplo:
<a <b <> <d<><>> > <c <e<><>> <f<><>>> >
PROF. MSC. ROMUERE SILVA 6
Árvores binárias - Implementação em C
Representação de uma árvore:
◦ Através de um ponteiro para o nó raiz
Representação de um nó da árvore:
◦ Estrutura em C contendo a informação propriamente dita (exemplo: um caractere) e os dois 
ponteiros para as sub-árvores, à esquerda e à direita.
PROF. MSC. ROMUERE SILVA 7
Árvores binárias - Implementação em C
Interface do tipo abstrato Árvore Binária: arv.h
PROF. MSC. ROMUERE SILVA 8
Árvores binárias - Implementação em C
A Função arv_criavazia cria uma árvore vazia.
PROF. MSC. ROMUERE SILVA 9
Árvores binárias - Implementação em C
Função arv_cria
◦ Cria um nó raiz dadas a informação e as duas sub-árvores, a da esquerda e a da direita;
◦ Retorna o endereço do nó raiz criado.
PROF. MSC. ROMUERE SILVA 10
Árvores binárias - Implementação em C
arv_criavazia e arv_cria: as duas funções para a criação de árvores 
representam os dois casos da definição recursiva de árvore binária:
◦ uma árvore binária Arv* a;
◦ É vazia a=arv_criavazia();
◦ É composta por uma raiz e duas sub-árvores a=arv_cria(c,sae,sad).
PROF. MSC. ROMUERE SILVA 11
Árvores binárias - Implementação em C
A função arv_libera libera memória alocada pela estrutura da árvore;
As sub-árvores devem ser liberadas antes de se liberar o nó raiz;
Retorna uma árvore vazia, representada por NULL.
PROF. MSC. ROMUERE SILVA 12
Árvores binárias - Implementação em C
PROF. MSC. ROMUERE SILVA 13
A função arv_vazia indica se uma árvore é ou não vazia.
Árvores binárias - Implementação em C
A função arv_pertence:
◦ Verifica a ocorrência de um caractere c em um de nós;
◦ Retorna um valor booleano (1 ou 0) indicando a ocorrência ou não do caractere na árvore.
PROF. MSC. ROMUERE SILVA 14
Árvores binárias - Implementação em C
A função arv_imprime percorre recursivamente a árvore, visitando todos os nós e imprimindo sua 
informação.
PROF. MSC. ROMUERE SILVA 15
Árvores binárias - Implementação em C
Exemplo: <a <b <> <d <><>> > <c <e <><> > <f <><> > > >
Representação gráfica?
Código?
PROF. MSC. ROMUERE SILVA 16
Árvores binárias - Implementação em C
PROF. MSC. ROMUERE SILVA 17
Árvores binárias - Implementação em C
Exemplo: <a <b <> <d <><>> > <c <e <><> > <f <><> > > >
Representação gráfica?
Código?
PROF. MSC. ROMUERE SILVA 18
Árvores binárias - Implementação em C
PROF. MSC. ROMUERE SILVA 19
Árvores binárias - Implementação em C
Exemplo: acrescentando nós
PROF. MSC. ROMUERE SILVA 20
Árvores binárias - Implementação em C
Exemplo: liberando nós
PROF. MSC. ROMUERE SILVA 21
Árvores binárias - Ordens de percurso
Ordens de percurso:
◦ Pré-ordem: raiz, sae, sad
◦ Exemplo: 4 2 1 3 6 5 7
◦ Ordem simétrica: sae, raiz, sad
◦ Exemplo:1 2 3 4 5 6 7
◦ Pós-ordem: sae, sad, raiz
◦ Exemplo: 1 3 2 5 7 6 4
PROF. MSC. ROMUERE SILVA 22
Árvores binárias - Altura
Propriedade fundamental de árvores:
◦ só existe um caminho da raiz para qualquer nó
Altura de uma árvore é comprimento do caminho mais longo da raiz até uma das folhas;
A altura de uma árvore com um único nó raiz é zero;
A altura de uma árvore vazia é -1;
Exemplo: h = 2
PROF. MSC. ROMUERE SILVA 23
Árvores binárias - Altura
Nível de um nó
◦ A raiz está no nível 0, seus filhos diretos no nível 1;
◦ O último nível da árvore é a altura da árvore.
PROF. MSC. ROMUERE SILVA 24
Árvores binárias - Altura
Árvore cheia é aquela em que todos os seus nós internos têm duas sub-árvores associadas
◦ número n de nós de uma árvore cheia de altura h
◦ 𝑛 = 2ℎ+1 − 1
PROF. MSC. ROMUERE SILVA 25
Árvores binárias - Altura
Árvore degenerada é aquela onde todos os seus nós internos têm uma única sub-árvore
associada;
O número n de nós de uma árvore degenerada de altura h é calculado por:
n = h+1
PROF. MSC. ROMUERE SILVA 26
Árvores com número variável de filhos
Árvore com número variável de filhos:
◦ cada nó pode ter mais do que duas sub-árvores associadas
◦ sub-árvores de um nó dispostas em ordem
◦ primeira sub-árvore (sa1), segunda sub-árvore (sa2), etc.
PROF. MSC. ROMUERE SILVA 27
Árvores com número variável de filhos
Notação textual: <raiz sa1 sa2 ... san>
Exemplo:
arvore = <a <b <c <d> > <e> > <f> <g <h> <i <j> > > >
PROF. MSC. ROMUERE SILVA 28
Árvores com número variável de filhos
Representação de árvore com número variável de filhos:
◦ utiliza uma “lista de filhos”;
◦ um nó aponta apenas para seu primeiro (prim) filho;
◦ cada um de seus filhos aponta para o próximo (prox) irmão.
PROF. MSC. ROMUERE SILVA 29
Árvores com número variável de filhos
A representação de um nó da árvore é uma estrutura em C contendo:
◦ a informação propriamente dita;
◦ ponteiro para a primeira sub-árvore filha;
◦ NULL se o nó for uma folha
◦ ponteiro para a próxima sub-árvore irmão
◦ NULL se for o último filho
PROF. MSC. ROMUERE SILVA 30
Árvores com número variável de filhos
Interface do tipo abstrato Árvore Variável: arvvar.h
PROF. MSC. ROMUERE SILVA 31
Árvores com número variável de filhos
A função arvv_cria cria uma folha, aloca o nó e inicializa os campos, atribuindo NULL aos 
campos prim e prox.
PROF. MSC. ROMUERE SILVA 32
Árvores com número variável de filhos
A função arvv_insere insere uma nova sub-árvore como filha de um dado, sempre no início da 
lista, por simplicidade.
PROF. MSC. ROMUERE SILVA 33
Árvores com número variável de filhos
A função arvv_imprime imprime o conteúdo dos nós.
PROF. MSC. ROMUERE SILVA 34
Árvores com número variável de filhos
A função arvv_pertence verifica a ocorrência de uma dada informação na árvore.
PROF. MSC. ROMUERE SILVA 35
Árvores binárias - Altura
A função arvv_libera libera a memória alocada pela árvore, libera as sub-árvores antes de 
liberar o espaço associado a um nó.
TAREFA DE 
PROF. MSC. ROMUERE SILVA 36
Árvores com número variável de filhos
Nível e altura: semelhante às árvores binárias.
◦ Exemplo: h = 3
PROF. MSC. ROMUERE SILVA 37
Árvores com número variável de filhos
A função arvv_altura calcula a maior altura entre as sub-árvores, acrescido de uma unidade;
Caso o nó raiz não tenha filhos, a altura da árvore deve ser 0.
TAREFA DE 
PROF. MSC. ROMUERE SILVA 38
Atividades
Implemente os TAD’s mostrados para Árvores Binárias e Árvores com número variável de filhos.
Crie funções main e teste todas as funções criadas.
Faça a atividades propostas nos slides 36 e 38.
PROF. MSC. ROMUERE SILVA 39
Classificação das Árvores Binárias
Árvore Estritamente Binária:
◦ É uma A.B. na qual todo nodo tem 0 ou 2 sub-árvores, ou seja, nenhum nodo tem “filho único”. 
PROF.
MSC. ROMUERE SILVA 40
Classificação das Árvores Binárias
Árvore Binária Cheia
É uma árvore na qual todos os nós, exceto os do último nível, têm exatamente duas sub-árvores.
Uma árvore binária cheia de altura h tem 2ℎ − 1 nós.
PROF. MSC. ROMUERE SILVA 41
Classificação das Árvores Binárias
Árvore Binária Completa
É uma árvore estritamente binária (nós com grau 0 ou 2), na qual os nós folhas podem estar 
apenas no último ou no penúltimo nível.
PROF. MSC. ROMUERE SILVA 42
Classificação das Árvores Binárias
Árvore Binária de Pesquisa (ou A.B. Ordenada):
É aquela na qual todo nó tem chave maior que o filho esquerdo e menor que o seu filho direito; 
Uma árvore binária de pesquisa só admite uma ocorrência de cada chave.
PROF. MSC. ROMUERE SILVA 43
Árvore Binária de Pesquisa –
Implementação em C
Interface do tipo abstrato Árvore Binária de Pesquisa: abp.h
PROF. MSC. ROMUERE SILVA 44
Árvore Binária de Pesquisa –
Implementação em C
Função abp_cria_vazia: cria uma árvore vazia. 
PROF. MSC. ROMUERE SILVA 45
Árvore Binária de Pesquisa –
Implementação em C
Função abp_inserir: insere um elemento na árvore de pesquisa. 
PROF. MSC. ROMUERE SILVA 46
Árvore Binária de Pesquisa –
Implementação em C
Função abp_consultar verifica se determinado elemento está contido na árvore.
PROF. MSC. ROMUERE SILVA 47
Árvore Binária de Pesquisa –
Implementação em C
Função abp_mostrar_em_ordem.
PROF. MSC. ROMUERE SILVA 48
Árvore Binária de Pesquisa –
Implementação em C
Funções abp_mostrar_pre_ordem e abp_mostrar_pos_ordem.
TAREFA DE 
PROF. MSC. ROMUERE SILVA 49
Árvore Binária de Pesquisa –
Implementação em C
A função abp_remover irá remover um elemento da árvore.
TAREFA DE 
PROF. MSC. ROMUERE SILVA 50
Árvore Binária de Pesquisa –
Implementação em C
A função abp_desalocar irá desalocar espaço de memória
PROF. MSC. ROMUERE SILVA 51