292
Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo [email protected] www.tiagodemelo.info

Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo [email protected]

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

Algoritmos e Estruturas de Dados I

Árvores

Prof. Tiago Eugenio de [email protected]

www.tiagodemelo.info

Page 2: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 3: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

3/292

Árvores

Page 4: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

4/292

Introdução

Page 5: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

5/292

Introdução

● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):

Page 6: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

6/292

Introdução

● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.

Page 7: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

7/292

Introdução

● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.

Page 8: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

8/292

Introdução

● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.– Lista ligada.

Page 9: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

9/292

Introdução

● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.– Lista ligada.– Pilhas.

Page 10: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

10/292

Introdução

● São exemplos de estruturas que organizam os dados de maneira linear (sequencial):– Array.– Lista.– Lista ligada.– Pilhas.– Filas.

Page 11: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 12: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

12/292

Introdução

Page 13: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

13/292

Introdução

● A estrutura de dados do tipo árvore permite organizar os dados de maneira hierárquica.

Page 14: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

14/292

Introdução

● A estrutura de dados do tipo árvore permite organizar os dados de maneira hierárquica.

Page 15: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

15/292

Introdução

Page 16: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

16/292

Introdução

● A estrutura de dados do tipo árvore permite organizar os dados em maneira hierárquica

Page 17: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 18: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 19: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 20: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 21: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 22: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 23: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

23/292

Introdução

Page 24: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

24/292

Introdução

● Inteligência artificial

Page 25: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

25/292

Introdução

● Inteligência artificial– Árvores de decisão

Page 26: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

26/292

Introdução

● Inteligência artificial– Árvores de decisão

Page 27: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

27/292

Introdução

Page 28: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

28/292

Introdução

● Processamento de Linguagem Natural

Page 29: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

29/292

Introdução

● Processamento de Linguagem Natural

Page 30: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

30/292

Introdução

Page 31: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

31/292

Introdução

● A estrutura de diretórios e arquivos de um sistema de arquivos é um exemplo de árvore:

Page 32: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

32/292

Introdução

● A estrutura de diretórios e arquivos de um sistema de arquivos é um exemplo de árvore:

Page 33: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

33/292

Estrutura de Dados

Page 34: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

34/292

Estrutura de Dados

● Uma árvore é formada por:

Page 35: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

35/292

Estrutura de Dados

● Uma árvore é formada por:– Nós (nodes)

Page 36: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

36/292

Estrutura de Dados

● Uma árvore é formada por:– Nós (nodes)

● Armazenam os dados.

Page 37: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

37/292

Estrutura de Dados

● Uma árvore é formada por:– Nós (nodes)

● Armazenam os dados.

– Vértices (edges)

Page 38: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 39: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

39/292

Estrutura de Dados

Page 40: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

40/292

Estrutura de Dados

● Definição formal:

Page 41: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 42: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 43: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

43/292

Estrutura de Dados

Page 44: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

44/292

Estrutura de Dados

● Cada subárvore é também considerada como uma árvore.

Page 45: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

45/292

Estrutura de Dados

● Cada subárvore é também considerada como uma árvore.

Page 46: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

46/292

Estrutura de Dados

● Cada subárvore é também considerada como uma árvore.

Page 47: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

47/292

Estrutura de Dados

● Cada subárvore é também considerada como uma árvore.

É uma subárvore!

Page 48: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

48/292

Estrutura de Dados

● Cada subárvore é também considerada como uma árvore.

É uma subárvore!

Mas também é uma árvore!

Page 49: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

49/292

Elementos da Estrutura Árvore

Page 50: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

50/292

Elementos da Estrutura Árvore

● Raiz (root)

Page 51: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

51/292

Elementos da Estrutura Árvore

● Raiz (root)– O nó no nível mais alto é chamado de nó raiz (root

node).

Page 52: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 53: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 54: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 55: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

55/292

Elementos da Estrutura Árvore

Page 56: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

56/292

Elementos da Estrutura Árvore

● Raiz (root)

Page 57: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

57/292

Elementos da Estrutura Árvore

● Raiz (root)

Page 58: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

58/292

Elementos da Estrutura Árvore

● Raiz (root)– 2 é o nó raiz.

Page 59: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

59/292

Elementos da Estrutura Árvore

Page 60: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

60/292

Elementos da Estrutura Árvore

● Caminho (path)

Page 61: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

61/292

Elementos da Estrutura Árvore

● Caminho (path)– Os demais nós da árvores são acessados através

dos vértices.

Page 62: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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).

Page 63: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

63/292

Elementos da Estrutura Árvore

Page 64: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

64/292

Elementos da Estrutura Árvore

● Caminho (path)

Page 65: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

65/292

Elementos da Estrutura Árvore

● Caminho (path)

Page 66: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

66/292

Elementos da Estrutura Árvore

● Caminho (path)– Caminho do nó T até K: T → C → R → K

Page 67: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

67/292

Elementos da Estrutura Árvore

Page 68: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

68/292

Elementos da Estrutura Árvore

● Pais (parent)

Page 69: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

69/292

Elementos da Estrutura Árvore

● Pais (parent)– Cada nó, com exceção da raiz, tem um nó pai.

Page 70: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 71: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 72: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 73: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

73/292

Elementos da Estrutura Árvore

Page 74: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

74/292

Elementos da Estrutura Árvore

● Filho (children)

Page 75: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

75/292

Elementos da Estrutura Árvore

● Filho (children)– Cada nó pode ter um ou mais filhos.

Page 76: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

76/292

Elementos da Estrutura Árvore

● Filho (children)– Cada nó pode ter um ou mais filhos.– Exemplo:

Page 77: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

77/292

Elementos da Estrutura Árvore

● Filho (children)– Cada nó pode ter um ou mais filhos.– Exemplo:

Page 78: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

78/292

Elementos da Estrutura Árvore

Page 79: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

79/292

Elementos da Estrutura Árvore

● Nós

Page 80: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

80/292

Elementos da Estrutura Árvore

● Nós– Nó que tem pelo menos 1 filho é chamado de nó

interior.

Page 81: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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).

Page 82: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 83: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 84: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

84/292

Elementos da Estrutura Árvore

Page 85: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

85/292

Elementos da Estrutura Árvore

● Subárvores

Page 86: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

86/292

Elementos da Estrutura Árvore

● Subárvores– Por definição, uma árvore é uma estrutura

recursiva.

Page 87: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 88: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 89: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 90: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 91: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

91/292

Árvores Binárias

Page 92: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

92/292

Árvores Binárias

Page 93: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

93/292

Árvores Binárias

● As árvores podem aparecer em vários formatos.

Page 94: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

94/292

Árvores Binárias

● As árvores podem aparecer em vários formatos.

● Elas podem variar o número de filhos permitidos por nó.

Page 95: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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ó.

Page 96: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 97: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

97/292

Árvores Binárias

● Propriedades– Árvores binárias podem aparecer em diferentes

formatos e tamanhos.

Page 98: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

98/292

Árvores Binárias

● Propriedades– Exemplo de três formatos distintos para uma

árvores binária com 9 nós:

Page 99: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

99/292

Árvores Binárias

Page 100: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

100/292

Árvores Binárias

● Tamanho da árvore

Page 101: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 102: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 103: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 104: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 105: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 106: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 107: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

107/292

Árvores Binárias

Page 108: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

108/292

Árvores Binárias

● Profundidade (depth)

Page 109: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

109/292

Árvores Binárias

● Profundidade (depth)– A profundidade de um nó é a sua distância até a

raiz.

Page 110: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

110/292

Árvores Binárias

● Profundidade (depth)– A profundidade de um nó é a sua distância até a

raiz.– A profundidade do nó G:

Page 111: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

111/292

Árvores Binárias

● Profundidade (depth)– A profundidade de um nó é a sua distância até a

raiz.– A profundidade do nó G:

Page 112: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 113: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 114: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 115: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

115/292

Árvores Binárias

Page 116: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

116/292

Árvores Binárias

● Altura (height)

Page 117: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

117/292

Árvores Binárias

● Altura (height)– É o número de níveis de uma árvore.

Page 118: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

118/292

Árvores Binárias

● Altura (height)– É o número de níveis de uma árvore.– Exemplo:

Page 119: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

119/292

Árvores Binárias

● Altura (height)– É o número de níveis de uma árvore.– Exemplo:

Page 120: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

120/292

Árvores Binárias

● Altura (height)– É o número de níveis de uma árvore.– Exemplo:

4

Page 121: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

121/292

Árvores Binárias

● Altura (height)– É o número de níveis de uma árvore.– Exemplo:

4 6

Page 122: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

122/292

Árvores Binárias

● Altura (height)– É o número de níveis de uma árvore.– Exemplo:

4 6 8

Page 123: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

123/292

Árvores Binárias

Page 124: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

124/292

Árvores Binárias

● Largura (width)– É o número de nós no nível que contém a maioria

dos nós.

Page 125: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

125/292

Árvores Binárias

● Largura (width)– É o número de nós no nível que contém a maioria

dos nós.

Page 126: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 127: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 128: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 129: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

129/292

Árvores Binárias

Page 130: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

130/292

Árvores Binárias

● Tamanho (size)

Page 131: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

131/292

Árvores Binárias

● Tamanho (size)– O tamanho máximo de uma árvore é o número de

nós da árvore.

Page 132: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

132/292

Árvores Binárias

● Tamanho (size)– O tamanho máximo de uma árvore é o número de

nós da árvore.

Page 133: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

133/292

Árvores Binárias

● Tamanho (size)– O tamanho máximo de uma árvore é o número de

nós da árvore.

Tamanho: 8

Page 134: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

134/292

Árvores Binárias

● Tamanho (size)– O tamanho máximo de uma árvore é o número de

nós da árvore.

Tamanho: 8

Page 135: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 136: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

136/292

Árvores Binárias

Page 137: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 138: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 139: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 140: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

140/292

Árvores Binárias

Page 141: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

141/292

Árvores Binárias● Qual é a altura mínima de uma árvore binária

com n nós?

Page 142: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 143: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 144: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

144/292

Árvores Binárias

Page 145: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

145/292

Árvores Binárias

● Qual é a altura mínima de uma árvore binária com n nós?

Page 146: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 147: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 148: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 149: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

149/292

Árvores Binárias

Page 150: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

150/292

Árvores Binárias

● Árvore binária cheia (full binary tree)

Page 151: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

151/292

Árvores Binárias

● Árvore binária cheia (full binary tree)– É uma árvore em que cada nó interior contém dois

filhos.

Page 152: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

152/292

Árvores Binárias

● Árvore binária cheia (full binary tree)– É uma árvore em que cada nó interior contém dois

filhos.– Exemplos:

Page 153: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

153/292

Árvores Binárias

● Árvore binária cheia (full binary tree)– É uma árvore em que cada nó interior contém dois

filhos.– Exemplos:

Page 154: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

154/292

Árvores Binárias

Page 155: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

155/292

Árvores Binárias

● Árvore binária perfeita (perfect binary tree)

Page 156: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 157: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 158: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 159: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 160: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

160/292

Árvores Binárias

Page 161: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

161/292

Árvores Binárias

● Comparação

Page 162: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

162/292

Árvores Binárias

● Comparação

Page 163: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

163/292

Árvores Binárias

● Comparação

estritamente binária

Page 164: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

164/292

Árvores Binárias

● Comparação

estritamente binária

binária completa

Page 165: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

165/292

Árvores Binárias

● Comparação

estritamente binária

binária completa binária cheia

Page 166: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

166/292

Árvores Binárias

Page 167: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

167/292

Árvores Binárias

● Árvores binárias são comumente implementadas como estruturas dinâmicas, assim como fizemos com as listas ligadas.

Page 168: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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).

Page 169: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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ó.

Page 170: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

170/292

Árvores Binárias

● Classe Nó

Page 171: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

171/292

Árvores Binárias

● Exemplo de implementação física da AB:

Page 172: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

172/292

Árvores Binárias - Varredura

Page 173: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

173/292

Árvores Binárias - Varredura

● A operação de varredura é uma das mais importantes na manipulação de coleções de dados.

Page 174: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 175: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

175/292

Árvores Binárias - Varredura

Page 176: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

176/292

Árvores Binárias - Varredura

● Como seria a busca em uma lista ligada?

Page 177: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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ó.

Page 178: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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?

Page 179: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 180: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 181: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 182: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

182/292

Árvores Binárias - Varredura

Page 183: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

183/292

Árvores Binárias - Varredura

● Existem 3 principais ordens de caminhamento:

Page 184: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

184/292

Árvores Binárias - Varredura

● Existem 3 principais ordens de caminhamento:– Pré-fixado

Page 185: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

185/292

Árvores Binárias - Varredura

● Existem 3 principais ordens de caminhamento:– Pré-fixado– Central

Page 186: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

186/292

Árvores Binárias - Varredura

● Existem 3 principais ordens de caminhamento:– Pré-fixado– Central– Pós-fixado

Page 187: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

187/292

Árvores Binárias - Varredura

Page 188: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

188/292

Árvores Binárias - Varredura

● Pré-fixado

Page 189: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

189/292

Árvores Binárias - Varredura

● Pré-fixado● Visita a raiz.

Page 190: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

190/292

Árvores Binárias - Varredura

● Pré-fixado● Visita a raiz.● Percorre a subárvore da esquerda.

Page 191: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

191/292

Árvores Binárias - Varredura

● Pré-fixado● Visita a raiz.● Percorre a subárvore da esquerda.● Percorre a subárvore da direita.

Page 192: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

192/292

Árvores Binárias - Varredura

● Pré-fixado● Visita a raiz.● Percorre a subárvore da esquerda.● Percorre a subárvore da direita.

Page 193: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

193/292

Árvores Binárias - Varredura

Page 194: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

194/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 195: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

195/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 196: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

196/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 197: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

197/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 198: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

198/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 199: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

199/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 200: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

200/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 201: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

201/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 202: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

202/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 203: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

203/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 204: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

204/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 205: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

205/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

Page 206: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

206/292

Árvores Binárias - Varredura

● Exemplo de pré-fixado:

A → B → D → E → H → C → F → G → I → J

Page 207: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

207/292

Árvores Binárias - Varredura

Page 208: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

208/292

Árvores Binárias - Varredura

● A função para caminho pré-fixado:

Page 209: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

209/292

Árvores Binárias - Varredura

● A função para caminho pré-fixado:– Função recursiva.

Page 210: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

210/292

Árvores Binárias - Varredura

● A função para caminho pré-fixado:– Função recursiva.

Page 211: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

211/292

Árvores Binárias - Varredura

● A função para caminho pré-fixado:– Função recursiva.– O parâmetro será uma subárvore:

Page 212: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 213: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 214: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

214/292

Árvores Binárias - Varredura

Page 215: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

215/292

Árvores Binárias - Varredura

● Caminhamento pré-fixado

Page 216: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 217: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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).

Page 218: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

218/292

Árvores Binárias - Varredura

Page 219: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

219/292

Árvores Binárias - Varredura

● Central

Page 220: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

220/292

Árvores Binárias - Varredura

● Central● Percorre a subárvore da esquerda.

Page 221: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

221/292

Árvores Binárias - Varredura

● Central● Percorre a subárvore da esquerda.● Visita a raiz.

Page 222: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

222/292

Árvores Binárias - Varredura

● Central● Percorre a subárvore da esquerda.● Visita a raiz.● Percorre a subárvore da direita.

Page 223: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

223/292

Árvores Binárias - Varredura

Page 224: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

224/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 225: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

225/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 226: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

226/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 227: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

227/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 228: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

228/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 229: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

229/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 230: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

230/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 231: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

231/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 232: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

232/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 233: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

233/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 234: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

234/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 235: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

235/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

Page 236: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

236/292

Árvores Binárias - Varredura

● Exemplo de caminhamento central

D → B → H → E → A → F → C → I → G → J

Page 237: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

237/292

Árvores Binárias - Varredura

Page 238: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

238/292

Árvores Binárias - Varredura

● A função para caminho central:

Page 239: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

239/292

Árvores Binárias - Varredura

● A função para caminho central:– Função recursiva.

Page 240: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

240/292

Árvores Binárias - Varredura

● A função para caminho central:– Função recursiva.

Page 241: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

241/292

Árvores Binárias - Varredura

● A função para caminho central:– Função recursiva.– O parâmetro será uma subárvore:

Page 242: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 243: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 244: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

244/292

Árvores Binárias - Varredura

Page 245: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

245/292

Árvores Binárias - Varredura

● Pós-fixado

Page 246: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

246/292

Árvores Binárias - Varredura

● Pós-fixado● Percorre a subárvore da esquerda.

Page 247: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

247/292

Árvores Binárias - Varredura

● Pós-fixado● Percorre a subárvore da esquerda.● Percorre a subárvore da direita.

Page 248: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

248/292

Árvores Binárias - Varredura

● Pós-fixado● Percorre a subárvore da esquerda.● Percorre a subárvore da direita.● Visita a raiz.

Page 249: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

249/292

Árvores Binárias - Varredura

Page 250: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

250/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 251: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

251/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 252: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

252/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 253: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

253/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 254: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

254/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 255: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

255/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 256: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

256/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 257: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

257/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 258: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

258/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 259: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

259/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 260: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

260/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 261: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

261/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

Page 262: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

262/292

Árvores Binárias - Varredura

● Exemplo de caminhamento pós-fixado

D → H → E → B → F → I → J → G → C → A

Page 263: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

263/292

Árvores Binárias - Varredura

Page 264: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

264/292

Árvores Binárias - Varredura

● A função para caminho pós-fixado:

Page 265: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

265/292

Árvores Binárias - Varredura

● A função para caminho pós-fixado:– Função recursiva.

Page 266: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

266/292

Árvores Binárias - Varredura

● A função para caminho pós-fixado:– Função recursiva.

Page 267: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

267/292

Árvores Binárias - Varredura

● A função para caminho pós-fixado:– Função recursiva.– O parâmetro será uma subárvore:

Page 268: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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

Page 269: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 270: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 271: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

271/292

Caminhamento em Largura

Page 272: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

272/292

Caminhamento em Largura

● Os caminhamentos pré-fixado, central e pós-fixado são exemplos de busca em profundidade.

Page 273: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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).

Page 274: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

274/292

Caminhamento em Largura

Page 275: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

275/292

Caminhamento em Largura

● No caminhamento em largura, os nós são visitados por nível, da esquerda para a direita.

Page 276: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

276/292

Caminhamento em Largura

● No caminhamento em largura, os nós são visitados por nível, da esquerda para a direita.

● Exemplo:

Page 277: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

277/292

Caminhamento em Largura

● No caminhamento em largura, os nós são visitados por nível, da esquerda para a direita.

● Exemplo:

Page 278: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

278/292

Caminhamento em Largura

Page 279: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

279/292

Caminhamento em Largura

● Não é possível usar funções recursivas nesse tipo de caminhamento.

Page 280: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 281: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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:

Page 282: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 283: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 284: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.

Page 285: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

285/292

Caminhamento em Largura

Page 286: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

286/292

Caminhamento em Largura

● Exemplo de código:

Page 287: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

287/292

Caminhamento em Largura

● Exemplo de código:

Page 288: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

288/292

Para pensar...

Como seria possível representar uma expressão tal como (9 + 3) * (8 – 4)

em uma árvore binária?

Page 289: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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?

Page 290: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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?

Page 291: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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)));

Page 292: Árvores - Tiago de Melotiagodemelo.info/wp-content/uploads/2019/05/aula-arvores.pdf · Algoritmos e Estruturas de Dados I Árvores Prof. Tiago Eugenio de Melo tmelo@uea.edu.br

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.