View
1
Download
0
Category
Preview:
Citation preview
Algoritmos e Estruturas de Dados I
Árvores
Prof. Tiago Eugenio de Melotmelo@uea.edu.br
www.tiagodemelo.info
2/292
Observações
● O conteúdo dessa aula é parcialmente proveniente do Capítulo 13 do livro “Data Structure and Algorithms Using Python”.
● As palavras com a fonte Courier indicam uma palavra-reservada da linguagem de programação.
3/292
Árvores
4/292
Introdução
5/292
Introdução
● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):
6/292
Introdução
● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.
7/292
Introdução
● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.
8/292
Introdução
● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.– Lista ligada.
9/292
Introdução
● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.– Lista ligada.– Pilhas.
10/292
Introdução
● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.– Lista ligada.– Pilhas.– Filas.
11/292
Introdução
● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.– Lista ligada.– Pilhas.– Filas.
● Todas têm uma noção de anterior e posterior.
12/292
Introdução
13/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados de maneira hierárquica.
14/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados de maneira hierárquica.
15/292
Introdução
16/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados em maneira hierárquica
17/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados em maneira hierárquica
● Útil para uma série de problemas:
18/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados em maneira hierárquica
● Útil para uma série de problemas:– Mineração de dados.
19/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados em maneira hierárquica
● Útil para uma série de problemas:– Mineração de dados.– Sistemas de banco de dados.
20/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados em maneira hierárquica
● Útil para uma série de problemas:– Mineração de dados.– Sistemas de banco de dados.– Inteligência artificial.
21/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados em maneira hierárquica
● Útil para uma série de problemas:– Mineração de dados.– Sistemas de banco de dados.– Inteligência artificial.– Sistemas operacionais.
22/292
Introdução
● A estrutura de dados do tipo árvore permite organizar os dados em maneira hierárquica
● Útil para uma série de problemas:– Mineração de dados.– Sistemas de banco de dados.– Inteligência artificial.– Sistemas operacionais.– Etc.
23/292
Introdução
24/292
Introdução
● Inteligência artificial
25/292
Introdução
● Inteligência artificial– Árvores de decisão
26/292
Introdução
● Inteligência artificial– Árvores de decisão
27/292
Introdução
28/292
Introdução
● Processamento de Linguagem Natural
29/292
Introdução
● Processamento de Linguagem Natural
30/292
Introdução
31/292
Introdução
● A estrutura de diretórios e arquivos de um sistema de arquivos é um exemplo de árvore:
32/292
Introdução
● A estrutura de diretórios e arquivos de um sistema de arquivos é um exemplo de árvore:
33/292
Estrutura de Dados
34/292
Estrutura de Dados
● Uma árvore é formada por:
35/292
Estrutura de Dados
● Uma árvore é formada por:– Nós (nodes)
36/292
Estrutura de Dados
● Uma árvore é formada por:– Nós (nodes)
● Armazenam os dados.
37/292
Estrutura de Dados
● Uma árvore é formada por:– Nós (nodes)
● Armazenam os dados.
– Vértices (edges)
38/292
Estrutura de Dados
● Uma árvore é formada por:– Nós (nodes)
● Armazenam os dados.
– Vértices (edges)● Par de nós são ligados por vértices.
39/292
Estrutura de Dados
40/292
Estrutura de Dados
● Definição formal:
41/292
Estrutura de Dados
● Definição formal:– Um conjunto de nós que pode ser vazio ou ter um
nó raiz que está conectado por vértices a zero ou mais subárvores para formar uma estrutura hierárquica.
42/292
Estrutura de Dados
● Definição formal:– Um conjunto de nós que pode ser vazio ou ter um
nó raiz que está conectado por vértices a zero ou mais subárvores para formar uma estrutura hierárquica.
43/292
Estrutura de Dados
44/292
Estrutura de Dados
● Cada subárvore é também considerada como uma árvore.
45/292
Estrutura de Dados
● Cada subárvore é também considerada como uma árvore.
46/292
Estrutura de Dados
● Cada subárvore é também considerada como uma árvore.
47/292
Estrutura de Dados
● Cada subárvore é também considerada como uma árvore.
É uma subárvore!
48/292
Estrutura de Dados
● Cada subárvore é também considerada como uma árvore.
É uma subárvore!
Mas também é uma árvore!
49/292
Elementos da Estrutura Árvore
50/292
Elementos da Estrutura Árvore
● Raiz (root)
51/292
Elementos da Estrutura Árvore
● Raiz (root)– O nó no nível mais alto é chamado de nó raiz (root
node).
52/292
Elementos da Estrutura Árvore
● Raiz (root)– O nó no nível mais alto é chamado de nó raiz (root
node).– Ele fornece o ponto de acesso para a estrutura.
53/292
Elementos da Estrutura Árvore
● Raiz (root)– O nó no nível mais alto é chamado de nó raiz (root
node).– Ele fornece o ponto de acesso para a estrutura.– É o único nó na árvore que não tem uma aresta de
entrada.
54/292
Elementos da Estrutura Árvore
● Raiz (root)– O nó no nível mais alto é chamado de nó raiz (root
node).– Ele fornece o ponto de acesso para a estrutura.– É o único nó na árvore que não tem uma aresta de
entrada.– Toda árvore não-vazia deve conter um nó raiz.
55/292
Elementos da Estrutura Árvore
56/292
Elementos da Estrutura Árvore
● Raiz (root)
57/292
Elementos da Estrutura Árvore
● Raiz (root)
58/292
Elementos da Estrutura Árvore
● Raiz (root)– 2 é o nó raiz.
59/292
Elementos da Estrutura Árvore
60/292
Elementos da Estrutura Árvore
● Caminho (path)
61/292
Elementos da Estrutura Árvore
● Caminho (path)– Os demais nós da árvores são acessados através
dos vértices.
62/292
Elementos da Estrutura Árvore
● Caminho (path)– Os demais nós da árvores são acessados através
dos vértices.– Os nós encontrados quando seguindo os vértices a
partir do nó raiz formam o caminho (path).
63/292
Elementos da Estrutura Árvore
64/292
Elementos da Estrutura Árvore
● Caminho (path)
65/292
Elementos da Estrutura Árvore
● Caminho (path)
66/292
Elementos da Estrutura Árvore
● Caminho (path)– Caminho do nó T até K: T → C → R → K
67/292
Elementos da Estrutura Árvore
68/292
Elementos da Estrutura Árvore
● Pais (parent)
69/292
Elementos da Estrutura Árvore
● Pais (parent)– Cada nó, com exceção da raiz, tem um nó pai.
70/292
Elementos da Estrutura Árvore
● Pais (parent)– Cada nó, com exceção da raiz, tem um nó pai.– Um nó pode ter apenas um nó pai.
71/292
Elementos da Estrutura Árvore
● Pais (parent)– Cada nó, com exceção da raiz, tem um nó pai.– Um nó pode ter apenas um nó pai.– Exemplo:
72/292
Elementos da Estrutura Árvore
● Pais (parent)– Cada nó, com exceção da raiz, tem um nó pai.– Um nó pode ter apenas um nó pai.– Exemplo:
73/292
Elementos da Estrutura Árvore
74/292
Elementos da Estrutura Árvore
● Filho (children)
75/292
Elementos da Estrutura Árvore
● Filho (children)– Cada nó pode ter um ou mais filhos.
76/292
Elementos da Estrutura Árvore
● Filho (children)– Cada nó pode ter um ou mais filhos.– Exemplo:
77/292
Elementos da Estrutura Árvore
● Filho (children)– Cada nó pode ter um ou mais filhos.– Exemplo:
78/292
Elementos da Estrutura Árvore
79/292
Elementos da Estrutura Árvore
● Nós
80/292
Elementos da Estrutura Árvore
● Nós– Nó que tem pelo menos 1 filho é chamado de nó
interior.
81/292
Elementos da Estrutura Árvore
● Nós– Nó que tem pelo menos 1 filho é chamado de nó
interior.– Nó que não tem filho é chamado de nó folha (leaf).
82/292
Elementos da Estrutura Árvore
● Nós– Nó que tem pelo menos 1 filho é chamado de nó
interior.– Nó que não tem filho é chamado de nó folha (leaf).– Exemplo:
83/292
Elementos da Estrutura Árvore
● Nós– Nó que tem pelo menos 1 filho é chamado de nó
interior.– Nó que não tem filho é chamado de nó folha (leaf).– Exemplo:
84/292
Elementos da Estrutura Árvore
85/292
Elementos da Estrutura Árvore
● Subárvores
86/292
Elementos da Estrutura Árvore
● Subárvores– Por definição, uma árvore é uma estrutura
recursiva.
87/292
Elementos da Estrutura Árvore
● Subárvores– Por definição, uma árvore é uma estrutura
recursiva.– Todo nó pode ser raiz da sua própria subárvore.
88/292
Elementos da Estrutura Árvore
● Subárvores– Por definição, uma árvore é uma estrutura
recursiva.– Todo nó pode ser raiz da sua própria subárvore.– Exemplo:
89/292
Elementos da Estrutura Árvore
● Subárvores– Por definição, uma árvore é uma estrutura
recursiva.– Todo nó pode ser raiz da sua própria subárvore.– Exemplo:
90/292
Elementos da Estrutura Árvore
● Grau– Representa o número de subárvores de um nó.
● Grau de uma árvore– É definido como sendo igual ao máximo dos graus
de todos os seus nós.
91/292
Árvores Binárias
92/292
Árvores Binárias
93/292
Árvores Binárias
● As árvores podem aparecer em vários formatos.
94/292
Árvores Binárias
● As árvores podem aparecer em vários formatos.
● Elas podem variar o número de filhos permitidos por nó.
95/292
Árvores Binárias
● As árvores podem aparecer em vários formatos.
● Elas podem variar o número de filhos permitidos por nó.
● Uma árvore bastante usada é a árvore binária, em que cada nó pode ter apenas dois filhos por nó.
96/292
Árvores Binárias
● As árvores podem aparecer em vários formatos.
● Elas podem variar o número de filhos permitidos por nó.
● Uma árvore bastante usada é a árvore binária, em que cada nó pode ter apenas dois filhos por nó.
● Os filhos podem ficar à esquerda ou à direita.
97/292
Árvores Binárias
● Propriedades– Árvores binárias podem aparecer em diferentes
formatos e tamanhos.
98/292
Árvores Binárias
● Propriedades– Exemplo de três formatos distintos para uma
árvores binária com 9 nós:
99/292
Árvores Binárias
100/292
Árvores Binárias
● Tamanho da árvore
101/292
Árvores Binárias
● Tamanho da árvore– Os nós em uma árvore binária são organizados em
níveis (levels), onde o nó raiz está no nível 0, os seus filhos no nível 1, etc.
102/292
Árvores Binárias
● Tamanho da árvore– Os nós em uma árvore binária são organizados em
níveis (levels), onde o nó raiz está no nível 0, os seus filhos no nível 1, etc.
103/292
Árvores Binárias
● Tamanho da árvore– Os nós em uma árvore binária são organizados em
níveis (levels), onde o nó raiz está no nível 0, os seus filhos no nível 1, etc.
Nível 0
104/292
Árvores Binárias
● Tamanho da árvore– Os nós em uma árvore binária são organizados em
níveis (levels), onde o nó raiz está no nível 0, os seus filhos no nível 1, etc.
Nível 0
Nível 1
105/292
Árvores Binárias
● Tamanho da árvore– Os nós em uma árvore binária são organizados em
níveis (levels), onde o nó raiz está no nível 0, os seus filhos no nível 1, etc.
Nível 0
Nível 1
Nível 2
106/292
Árvores Binárias
● Tamanho da árvore– Os nós em uma árvore binária são organizados em
níveis (levels), onde o nó raiz está no nível 0, os seus filhos no nível 1, etc.
Nível 0
Nível 1
Nível 2
Nível 3
107/292
Árvores Binárias
108/292
Árvores Binárias
● Profundidade (depth)
109/292
Árvores Binárias
● Profundidade (depth)– A profundidade de um nó é a sua distância até a
raiz.
110/292
Árvores Binárias
● Profundidade (depth)– A profundidade de um nó é a sua distância até a
raiz.– A profundidade do nó G:
111/292
Árvores Binárias
● Profundidade (depth)– A profundidade de um nó é a sua distância até a
raiz.– A profundidade do nó G:
112/292
Árvores Binárias
● Profundidade (depth)– A profundidade de um nó é a sua distância até a
raiz.– A profundidade do nó G:
2
113/292
Árvores Binárias
● Profundidade (depth)– A profundidade de um nó é a sua distância até a
raiz.– A profundidade do nó G:
23
114/292
Árvores Binárias
● Profundidade (depth)– A profundidade de um nó é a sua distância até a
raiz.– A profundidade do nó G:
23
5
115/292
Árvores Binárias
116/292
Árvores Binárias
● Altura (height)
117/292
Árvores Binárias
● Altura (height)– É o número de níveis de uma árvore.
118/292
Árvores Binárias
● Altura (height)– É o número de níveis de uma árvore.– Exemplo:
119/292
Árvores Binárias
● Altura (height)– É o número de níveis de uma árvore.– Exemplo:
120/292
Árvores Binárias
● Altura (height)– É o número de níveis de uma árvore.– Exemplo:
4
121/292
Árvores Binárias
● Altura (height)– É o número de níveis de uma árvore.– Exemplo:
4 6
122/292
Árvores Binárias
● Altura (height)– É o número de níveis de uma árvore.– Exemplo:
4 6 8
123/292
Árvores Binárias
124/292
Árvores Binárias
● Largura (width)– É o número de nós no nível que contém a maioria
dos nós.
125/292
Árvores Binárias
● Largura (width)– É o número de nós no nível que contém a maioria
dos nós.
126/292
Árvores Binárias
● Largura (width)– É o número de nós no nível que contém a maioria
dos nós.
4
127/292
Árvores Binárias
● Largura (width)– É o número de nós no nível que contém a maioria
dos nós.
4 3
128/292
Árvores Binárias
● Largura (width)– É o número de nós no nível que contém a maioria
dos nós.
4 3 1
129/292
Árvores Binárias
130/292
Árvores Binárias
● Tamanho (size)
131/292
Árvores Binárias
● Tamanho (size)– O tamanho máximo de uma árvore é o número de
nós da árvore.
132/292
Árvores Binárias
● Tamanho (size)– O tamanho máximo de uma árvore é o número de
nós da árvore.
133/292
Árvores Binárias
● Tamanho (size)– O tamanho máximo de uma árvore é o número de
nós da árvore.
Tamanho: 8
134/292
Árvores Binárias
● Tamanho (size)– O tamanho máximo de uma árvore é o número de
nós da árvore.
Tamanho: 8
135/292
Árvores Binárias
● Tamanho (size)– O tamanho máximo de uma árvore é o número de
nós da árvore.
Tamanho: 9Tamanho: 8
136/292
Árvores Binárias
137/292
Árvores Binárias
● Uma árvore binária de tamanho n pode ter uma altura máxima de n, quando existe um nó por nível.
138/292
Árvores Binárias
● Uma árvore binária de tamanho n pode ter uma altura máxima de n, quando existe um nó por nível.
● Exemplo:
139/292
Árvores Binárias
● Uma árvore binária de tamanho n pode ter uma altura máxima de n, quando existe um nó por nível.
● Exemplo:
140/292
Árvores Binárias
141/292
Árvores Binárias● Qual é a altura mínima de uma árvore binária
com n nós?
142/292
Árvores Binárias● Qual é a altura mínima de uma árvore binária
com n nós?– Cada nível i terá 2i nós.
143/292
Árvores Binárias● Qual é a altura mínima de uma árvore binária
com n nós?– Cada nível i terá 2i nós.
144/292
Árvores Binárias
145/292
Árvores Binárias
● Qual é a altura mínima de uma árvore binária com n nós?
146/292
Árvores Binárias
● Qual é a altura mínima de uma árvore binária com n nós?
n = 20 + 21 + 22 + … + 2d-1 + 2d
147/292
Árvores Binárias
● Qual é a altura mínima de uma árvore binária com n nós?
n = 20 + 21 + 22 + … + 2d-1 + 2d
n = 2d+1 – 1
148/292
Árvores Binárias
● Qual é a altura mínima de uma árvore binária com n nós?
n = 20 + 21 + 22 + … + 2d-1 + 2d
n = 2d+1 – 1
d = log (n + 1) - 1
149/292
Árvores Binárias
150/292
Árvores Binárias
● Árvore binária cheia (full binary tree)
151/292
Árvores Binárias
● Árvore binária cheia (full binary tree)– É uma árvore em que cada nó interior contém dois
filhos.
152/292
Árvores Binárias
● Árvore binária cheia (full binary tree)– É uma árvore em que cada nó interior contém dois
filhos.– Exemplos:
153/292
Árvores Binárias
● Árvore binária cheia (full binary tree)– É uma árvore em que cada nó interior contém dois
filhos.– Exemplos:
154/292
Árvores Binárias
155/292
Árvores Binárias
● Árvore binária perfeita (perfect binary tree)
156/292
Árvores Binárias
● Árvore binária perfeita (perfect binary tree)– É uma árvore binária em que todos os nós folhas
estão no mesmo nível.
157/292
Árvores Binárias
● Árvore binária perfeita (perfect binary tree)– É uma árvore binária em que todos os nós folhas
estão no mesmo nível.– Exemplo:
158/292
Árvores Binárias
● Árvore binária perfeita (perfect binary tree)– É uma árvore binária em que todos os nós folhas
estão no mesmo nível.– Exemplo:
159/292
Árvores Binárias
● Árvore binária completa (complete binary tree)– É uma árvore completa em todos os níveis, exceto
possivelmente o último.– Exemplo:
160/292
Árvores Binárias
161/292
Árvores Binárias
● Comparação
162/292
Árvores Binárias
● Comparação
163/292
Árvores Binárias
● Comparação
estritamente binária
164/292
Árvores Binárias
● Comparação
estritamente binária
binária completa
165/292
Árvores Binárias
● Comparação
estritamente binária
binária completa binária cheia
166/292
Árvores Binárias
167/292
Árvores Binárias
● Árvores binárias são comumente implementadas como estruturas dinâmicas, assim como fizemos com as listas ligadas.
168/292
Árvores Binárias
● Árvores binárias são comumente implementadas como estruturas dinâmicas, assim como fizemos com as listas ligadas.
● Uma árvore binária é uma estrutura de dados que pode ser usada para implementar diferentes tipos abstratos de dados (TAD).
169/292
Árvores Binárias
● Árvores binárias são comumente implementadas como estruturas dinâmicas, assim como fizemos com as listas ligadas.
● Uma árvore binária é uma estrutura de dados que pode ser usada para implementar diferentes tipos abstratos de dados (TAD).
● Para a sua implementação, nós devemos explicitamente armazenar em cada nó as ligações (links) para os dois nós filhos juntamente com os dados armazenados em cada nó.
170/292
Árvores Binárias
● Classe Nó
171/292
Árvores Binárias
● Exemplo de implementação física da AB:
172/292
Árvores Binárias - Varredura
173/292
Árvores Binárias - Varredura
● A operação de varredura é uma das mais importantes na manipulação de coleções de dados.
174/292
Árvores Binárias - Varredura
● A operação de varredura é uma das mais importantes na manipulação de coleções de dados.
● O objetivo aqui é percorrer toda a coleção, acessando um elemento de cada vez.
175/292
Árvores Binárias - Varredura
176/292
Árvores Binárias - Varredura
● Como seria a busca em uma lista ligada?
177/292
Árvores Binárias - Varredura
● Como seria a busca em uma lista ligada?– Bastaria iniciar do primeiro nó e percorrer a lista,
seguindo as ligações, até o último nó.
178/292
Árvores Binárias - Varredura
● Como seria a busca em uma lista ligada?– Bastaria iniciar do primeiro nó e percorrer a lista,
seguindo as ligações, até o último nó.● Mas seria possível visitar cada nó em uma
árvore binária?
179/292
Árvores Binárias - Varredura
● Como seria a busca em uma lista ligada?– Bastaria iniciar do primeiro nó e percorrer a lista,
seguindo as ligações, até o último nó.● Mas seria possível visitar cada nó em uma
árvore binária?– Não existe um único caminho que parta da raiz e
consiga visitar todos os nós.
180/292
Árvores Binárias - Varredura
● Como seria a busca em uma lista ligada?– Bastaria iniciar do primeiro nó e percorrer a lista,
seguindo as ligações, até o último nó.● Mas seria possível visitar cada nó em uma
árvore binária?– Não existe um único caminho que parta da raiz e
consiga visitar todos os nós.– As árvores podem ser percorridas de várias formas.
181/292
Árvores Binárias - Varredura
● Existem vários métodos de varredura (caminhamento) em árvores, que permitem percorrê-la de forma sistemática e de tal modo que cada nó seja visitado apenas uma vez.
182/292
Árvores Binárias - Varredura
183/292
Árvores Binárias - Varredura
● Existem 3 principais ordens de caminhamento:
184/292
Árvores Binárias - Varredura
● Existem 3 principais ordens de caminhamento:– Pré-fixado
185/292
Árvores Binárias - Varredura
● Existem 3 principais ordens de caminhamento:– Pré-fixado– Central
186/292
Árvores Binárias - Varredura
● Existem 3 principais ordens de caminhamento:– Pré-fixado– Central– Pós-fixado
187/292
Árvores Binárias - Varredura
188/292
Árvores Binárias - Varredura
● Pré-fixado
189/292
Árvores Binárias - Varredura
● Pré-fixado● Visita a raiz.
190/292
Árvores Binárias - Varredura
● Pré-fixado● Visita a raiz.● Percorre a subárvore da esquerda.
191/292
Árvores Binárias - Varredura
● Pré-fixado● Visita a raiz.● Percorre a subárvore da esquerda.● Percorre a subárvore da direita.
192/292
Árvores Binárias - Varredura
● Pré-fixado● Visita a raiz.● Percorre a subárvore da esquerda.● Percorre a subárvore da direita.
193/292
Árvores Binárias - Varredura
194/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
195/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
196/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
197/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
198/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
199/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
200/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
201/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
202/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
203/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
204/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
205/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
206/292
Árvores Binárias - Varredura
● Exemplo de pré-fixado:
A → B → D → E → H → C → F → G → I → J
207/292
Árvores Binárias - Varredura
208/292
Árvores Binárias - Varredura
● A função para caminho pré-fixado:
209/292
Árvores Binárias - Varredura
● A função para caminho pré-fixado:– Função recursiva.
210/292
Árvores Binárias - Varredura
● A função para caminho pré-fixado:– Função recursiva.
211/292
Árvores Binárias - Varredura
● A função para caminho pré-fixado:– Função recursiva.– O parâmetro será uma subárvore:
212/292
Árvores Binárias - Varredura
● A função para caminho pré-fixado:– Função recursiva.– O parâmetro será uma subárvore:
● Referência null (None) ou
213/292
Árvores Binárias - Varredura
● A função para caminho pré-fixado:– Função recursiva.– O parâmetro será uma subárvore:
● Referência null (None) ou● Referência para o nó raiz de uma subárvore.
214/292
Árvores Binárias - Varredura
215/292
Árvores Binárias - Varredura
● Caminhamento pré-fixado
216/292
Árvores Binárias - Varredura
● Caminhamento pré-fixado– Dada uma árvore binária de tamanho n, o
caminhamento completo dessa árvore visitará cada nó uma única vez.
217/292
Árvores Binárias - Varredura
● Caminhamento pré-fixado– Dada uma árvore binária de tamanho n, o
caminhamento completo dessa árvore visitará cada nó uma única vez.
– Se a operação de visita requerer tempo constante, então o tempo de caminhamento será feito em O(n).
218/292
Árvores Binárias - Varredura
219/292
Árvores Binárias - Varredura
● Central
220/292
Árvores Binárias - Varredura
● Central● Percorre a subárvore da esquerda.
221/292
Árvores Binárias - Varredura
● Central● Percorre a subárvore da esquerda.● Visita a raiz.
222/292
Árvores Binárias - Varredura
● Central● Percorre a subárvore da esquerda.● Visita a raiz.● Percorre a subárvore da direita.
223/292
Árvores Binárias - Varredura
224/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
225/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
226/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
227/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
228/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
229/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
230/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
231/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
232/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
233/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
234/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
235/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
236/292
Árvores Binárias - Varredura
● Exemplo de caminhamento central
D → B → H → E → A → F → C → I → G → J
237/292
Árvores Binárias - Varredura
238/292
Árvores Binárias - Varredura
● A função para caminho central:
239/292
Árvores Binárias - Varredura
● A função para caminho central:– Função recursiva.
240/292
Árvores Binárias - Varredura
● A função para caminho central:– Função recursiva.
241/292
Árvores Binárias - Varredura
● A função para caminho central:– Função recursiva.– O parâmetro será uma subárvore:
242/292
Árvores Binárias - Varredura
● A função para caminho central:– Função recursiva.– O parâmetro será uma subárvore:
● Referência null (None) ou
243/292
Árvores Binárias - Varredura
● A função para caminho central:– Função recursiva.– O parâmetro será uma subárvore:
● Referência null (None) ou● Referência para o nó raiz de uma subárvore.
244/292
Árvores Binárias - Varredura
245/292
Árvores Binárias - Varredura
● Pós-fixado
246/292
Árvores Binárias - Varredura
● Pós-fixado● Percorre a subárvore da esquerda.
247/292
Árvores Binárias - Varredura
● Pós-fixado● Percorre a subárvore da esquerda.● Percorre a subárvore da direita.
248/292
Árvores Binárias - Varredura
● Pós-fixado● Percorre a subárvore da esquerda.● Percorre a subárvore da direita.● Visita a raiz.
249/292
Árvores Binárias - Varredura
250/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
251/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
252/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
253/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
254/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
255/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
256/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
257/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
258/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
259/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
260/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
261/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
262/292
Árvores Binárias - Varredura
● Exemplo de caminhamento pós-fixado
D → H → E → B → F → I → J → G → C → A
263/292
Árvores Binárias - Varredura
264/292
Árvores Binárias - Varredura
● A função para caminho pós-fixado:
265/292
Árvores Binárias - Varredura
● A função para caminho pós-fixado:– Função recursiva.
266/292
Árvores Binárias - Varredura
● A função para caminho pós-fixado:– Função recursiva.
267/292
Árvores Binárias - Varredura
● A função para caminho pós-fixado:– Função recursiva.– O parâmetro será uma subárvore:
268/292
Árvores Binárias - Varredura
● A função para caminho pós-fixado:– Função recursiva.– O parâmetro será uma subárvore:
● Referência null (None) ou
269/292
Árvores Binárias - Varredura
● A função para caminho pós-fixado:– Função recursiva.– O parâmetro será uma subárvore:
● Referência null (None) ou● Referência para o nó raiz de uma subárvore.
270/292
Árvores Binárias - Varredura
● A função para caminho pós-fixado:– Função recursiva.– O parâmetro será uma subárvore:
● Referência null (None) ou● Referência para o nó raiz de uma subárvore.
– O nó raiz é sempre visitado por último.
271/292
Caminhamento em Largura
272/292
Caminhamento em Largura
● Os caminhamentos pré-fixado, central e pós-fixado são exemplos de busca em profundidade.
273/292
Caminhamento em Largura
● Os caminhamentos pré-fixado, central e pós-fixado são exemplos de busca em profundidade.
● Outra forma de pesquisa é o caminhamento em largura (breadth-first).
274/292
Caminhamento em Largura
275/292
Caminhamento em Largura
● No caminhamento em largura, os nós são visitados por nível, da esquerda para a direita.
276/292
Caminhamento em Largura
● No caminhamento em largura, os nós são visitados por nível, da esquerda para a direita.
● Exemplo:
277/292
Caminhamento em Largura
● No caminhamento em largura, os nós são visitados por nível, da esquerda para a direita.
● Exemplo:
278/292
Caminhamento em Largura
279/292
Caminhamento em Largura
● Não é possível usar funções recursivas nesse tipo de caminhamento.
280/292
Caminhamento em Largura
● Não é possível usar funções recursivas nesse tipo de caminhamento.
● Uma alternativa é usar uma estrutura do tipo Fila.
281/292
Caminhamento em Largura
● Não é possível usar funções recursivas nesse tipo de caminhamento.
● Uma alternativa é usar uma estrutura do tipo Fila.
● Algoritmo:
282/292
Caminhamento em Largura
● Não é possível usar funções recursivas nesse tipo de caminhamento.
● Uma alternativa é usar uma estrutura do tipo Fila.
● Algoritmo:– Inicia pelo nó raiz.
283/292
Caminhamento em Largura
● Não é possível usar funções recursivas nesse tipo de caminhamento.
● Uma alternativa é usar uma estrutura do tipo Fila.● Algoritmo:
– Inicia pelo nó raiz.– Durante cada iteração, nós removemos o nó da fila,
visitamos o nó, e então adicionamos os seus filhos à fila.
284/292
Caminhamento em Largura
● Não é possível usar funções recursivas nesse tipo de caminhamento.
● Uma alternativa é usar uma estrutura do tipo Fila.● Algoritmo:
– Inicia pelo nó raiz.– Durante cada iteração, nós removemos o nó da fila,
visitamos o nó, e então adicionamos os seus filhos à fila.– O algoritmo termina quando todos os nós tiverem sido
visitados.
285/292
Caminhamento em Largura
286/292
Caminhamento em Largura
● Exemplo de código:
287/292
Caminhamento em Largura
● Exemplo de código:
288/292
Para pensar...
Como seria possível representar uma expressão tal como (9 + 3) * (8 – 4)
em uma árvore binária?
289/292
Exercícios
● Dada uma árvore binária de tamanho 76, qual é o número mínimo de níveis que ela pode ter? E qual seria o número máximo de níveis?
● Qual é o número máximo de nós de uma árvore binária de 5 níveis?
290/292
Exercícios
● Considere a árvore abaixo e faça o que se pede:– Mostre a ordem em que os nós seria visitados para
cada caminhamento visto em sala de aula.– Identifique os nós folhas.– Identifique os nós internos.– Liste todos os nós do nível 4.– Identifique a profundidade do nó 2.– Quem são as ascendentes do nó 4?
291/292
Exercícios
● Considere as árvores binárias abaixo e responda ao que se pede:– Elas são balanceadas?– Elas são perfeitamente balanceadas?– Liste os nós conforme os vários tipos de
caminhamento vistos em sala de aula.
b) (A (B (D (F)) (E)) (C (G (H))));
a) (1 (2 (4) (5)) (3 (6) (7)));
292/292
Exercícios
● Implemente a função treeSize(root) para calcular o número de nós de uma árvore binária.
● Implemente a função treeHeight(root) para calcular a altura de uma árvore binária.
Recommended