647580_ArvoresEArvBinaria

Prévia do material em texto

Algoritmos e Algoritmos e 
Estruturas de dadosEstruturas de dados
ÁRVORESÁRVORES
ÁrvoresÁrvores
➲ Uma árvore é um conjunto não vazio de Uma árvore é um conjunto não vazio de 
nós (vértices) e arestas;nós (vértices) e arestas;
➲ Um dos nós é definido como sendo a Um dos nós é definido como sendo a 
Raiz;Raiz;
➲ Nós sem filhos são chamados de Folhas Nós sem filhos são chamados de Folhas 
(nós terminais ou externos)(nós terminais ou externos)
➲ Todo nó é raiz de uma sub-árvore que Todo nó é raiz de uma sub-árvore que 
consiste do nó em questão e todos os consiste do nó em questão e todos os 
demais nós que se encontram abaixo demais nós que se encontram abaixo 
dele.dele.
ÁrvoresÁrvores
➲ O nó O nó raíz é aquele (único) nó que não tem raíz é aquele (único) nó que não tem 
ancestrais.ancestrais.
Raiz da Árvore
ÁrvoresÁrvores
➲ O Grau de um nó é o número de filhos desse nó.O Grau de um nó é o número de filhos desse nó.
➲ O Grau da Árvore é o máximo grau possível de ser O Grau da Árvore é o máximo grau possível de ser 
atingido por um nó da Árvore atingido por um nó da Árvore 
G = 3
G = 2
G = 3
G = 0
GA = 3
ÁrvoresÁrvores
➲ Nível de um nó é a distância do nó à RaizNível de um nó é a distância do nó à Raiz
NN = 0
NN = 1
NN = 2
ÁrvoresÁrvores
➲ Altura da Árvore é o maior nível atingido por ela.Altura da Árvore é o maior nível atingido por ela.
AA = 2
ÁrvoresÁrvores
➲ Caminho: Diz-se que existe um caminho entre dois Caminho: Diz-se que existe um caminho entre dois 
nós A e B de uma árvore, se a partir do nó A nós A e B de uma árvore, se a partir do nó A 
pode-se chegar ao nó B percorrendo-se as arestas pode-se chegar ao nó B percorrendo-se as arestas 
que ligam os nós intermediários entre A e B.que ligam os nós intermediários entre A e B.
➲ Caminho(1-7) => 1-2-7. Caminho(1-7) => 1-2-7. 
Características de uma ÁrvoreCaracterísticas de uma Árvore
➲ Número finito de nós.Número finito de nós.
➲ Cada nó possui de 0 a n filhos.Cada nó possui de 0 a n filhos.
➲ Todo nó, exceto a raiz, possui um único pai.Todo nó, exceto a raiz, possui um único pai.
➲ Só existe um caminho entre 2 nós da árvore.Só existe um caminho entre 2 nós da árvore.
➲ Uma árvore com N nós possui N - 1 arestas.Uma árvore com N nós possui N - 1 arestas.
Aplicações de ÁrvoresAplicações de Árvores
➲ Representação de estruturas hierárquicas.Representação de estruturas hierárquicas.
 Exemplo: sumário de um livro, árvore Exemplo: sumário de um livro, árvore 
genealógica, organograma.genealógica, organograma.
➲ Representação de processos decisórios.Representação de processos decisórios.
➲ Ordenação e pesquisa.Ordenação e pesquisa.
Algoritmos e Algoritmos e 
Estruturas de dadosEstruturas de dados
ÁRVORES BINÁRIASÁRVORES BINÁRIAS
Árvores BináriasÁrvores Binárias
➲ Uma árvore binária é um conjunto de Uma árvore binária é um conjunto de 
nós onde cada nó é composto por três nós onde cada nó é composto por três 
entidades:entidades:
 O conteúdo do nó (informação principal)O conteúdo do nó (informação principal)
 Um ponteiro (referência) para o nó seguinte à Um ponteiro (referência) para o nó seguinte à 
esquerdaesquerda
 Um ponteiro (referência) para o nó seguinte à Um ponteiro (referência) para o nó seguinte à 
direitadireita
Árvores Binárias (de Pesquisa)Árvores Binárias (de Pesquisa)
➲ Cada nó possui de 0 a 2 filhosCada nó possui de 0 a 2 filhos
➲ O Conteúdo do nó possui uma chave de comparaçãoO Conteúdo do nó possui uma chave de comparação
➲ Para cada nó X:Para cada nó X:
 todos os nós com chave menor que X estão na sub-todos os nós com chave menor que X estão na sub-
árvore à esquerda; eárvore à esquerda; e
 todos os nós com chave maior que X estão na sub-árvore todos os nós com chave maior que X estão na sub-árvore 
à direita.à direita.
Árvore BináriaÁrvore Binária
➲ Dois tipos especiais de árvores binárias Dois tipos especiais de árvores binárias 
merecem atenção: as árvores merecem atenção: as árvores cheias e as cheias e as 
árvores completas.árvores completas.
► Uma árvore cheia não tem nenhum nó apontando para Uma árvore cheia não tem nenhum nó apontando para 
apenas um outro nó ==> cada nó tem 0 ou dois filhos.apenas um outro nó ==> cada nó tem 0 ou dois filhos.
► Uma árvore completa de altura (k) é tal que todos os nós Uma árvore completa de altura (k) é tal que todos os nós 
até a profundidade (nível) (k-2) apontam cada um para até a profundidade (nível) (k-2) apontam cada um para 
dois outros nós. Os nós de profundidade (k-1) estão dois outros nós. Os nós de profundidade (k-1) estão 
organizados de forma que, da esquerda para a direita, organizados de forma que, da esquerda para a direita, 
encontremos primeiramente os que apontam para dois nós, encontremos primeiramente os que apontam para dois nós, 
depois os que apontam para um nó e finalmente os que depois os que apontam para um nó e finalmente os que 
não apontam para nenhum outro nó. Os nós de não apontam para nenhum outro nó. Os nós de 
profundidade k são todos folhas.profundidade k são todos folhas.
Árvores binárias Árvores binárias 
Uma Uma árvore cheia árvore cheia não tem nenhum nó não tem nenhum nó 
apontando para apenas um outro nó.apontando para apenas um outro nó.
Árvores bináriasÁrvores binárias
Uma árvore completa Uma árvore completa de altura (k) é tal que todos os nós até a de altura (k) é tal que todos os nós até a 
profundidade (k-2) apontam cada um para dois outros nós. Os profundidade (k-2) apontam cada um para dois outros nós. Os 
nós de profundidade (k-1) estão organizados de forma que, da nós de profundidade (k-1) estão organizados de forma que, da 
esquerda para a direita, encontremos primeiramente os que esquerda para a direita, encontremos primeiramente os que 
apontam para dois nós, depois os que apontam para um nó e apontam para dois nós, depois os que apontam para um nó e 
finalmente os que não apontam para nenhum outro nó. Os nós de finalmente os que não apontam para nenhum outro nó. Os nós de 
profundidade k são todos folhas.profundidade k são todos folhas.
Árvores binárias – percursosÁrvores binárias – percursos
➲ Frequentemente, quando construímos uma árvore Frequentemente, quando construímos uma árvore 
binária, nosso interesse é recuperar os conteúdos binária, nosso interesse é recuperar os conteúdos 
dos nós segundo alguma disciplina de ordenação. dos nós segundo alguma disciplina de ordenação. 
Existem basicamente duas categorias de percurso: Existem basicamente duas categorias de percurso: 
Em profundidade ou em nível. Em profundidade se Em profundidade ou em nível. Em profundidade se 
divide em três formas mais comuns, denominadas divide em três formas mais comuns, denominadas 
pré-ordem, in-ordem e pós-ordem.pré-ordem, in-ordem e pós-ordem.
► Pré-ordem: são recuperados primeiros os conteúdos dos nós, e Pré-ordem: são recuperados primeiros os conteúdos dos nós, e 
depois de seus descendentes diretos.depois de seus descendentes diretos.
► Pós-ordem: são recuperados primeiros os conteúdos dos Pós-ordem: são recuperados primeiros os conteúdos dos 
descendentes, e depois dos próprios nós.descendentes, e depois dos próprios nós.
► In-ordem: os conteúdos são recuperados na seguinte seqüência: In-ordem: os conteúdos são recuperados na seguinte seqüência: 
descendente à esquerda, o próprio nó, descendente à direita.descendente à esquerda, o próprio nó, descendente à direita.
Árvores binárias – percursosÁrvores binárias – percursos
➲ Exemplo: seja a árvore abaixo:Exemplo: seja a árvore abaixo:
A
B C
D E F
H IG
➲ Pré-ordem: ABDCEGFHI
➲ Pós-ordem: DBGEHIFCA
➲ In-ordem: BDAGECHFI
Árvores binárias – percursosÁrvores binárias – percursos
➲ Em Nível, a idéia básica é percorrer a árvore Em Nível, a idéia básica é percorrer a árvore 
visitando a raiz; sub-árvore à esquerda e sub-árvore visitando a raiz; sub-árvore à esquerda e sub-árvore 
à direita utilizando uma fila. à direita utilizando uma fila. 
A
B C
D E F
H IG
➲ Em-nível: ABCDEFGHI 
	Slide1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18