LISTA DE ATIVIDADES ARVORES

--LISTA DE ATIVIDADES ARVORES

1 Relacione a coluna da direita com a da esquerda:

2 Relacione a letra da figura com o tipo da árvore:

3 Transforme a árvore abaixo em árvore binária:

4 Determine os três tipos de percursos (InOrdem(Simétrica), PreOrdem e PosOrdem) das duas árvores binárias abaixo.

5 Uma Árvore de Busca Binária (ou árvore de pesquisa binária) é uma árvore binária onde todos os nós são valores, todo nó a esquerda contém uma sub-árvore com os valores menores ao nó raiz da sub-árvore e todos os nós da sub-árvore à direita contém somente valores maiores ao nó raiz. (Esta é a forma padrão, podendo ser invertida as sub-árvores dependendo da aplicação). Os valores são relevantes na árvore de busca binária. O objetivo desta árvore é estruturar os dados de forma flexível permitindo pesquisa binária. Vide exemplo abaixo.

Determine as Árvores de Busca Binária para as seguintes entradas abaixo:

a) E, A, S, Y, Q, U, E, S, T, I, O, N (chaves da árvore são caracteres)

b) 7 8 2 5 18 3 25 10 4 12 1 34 9 15 6

6 Em uma árvore binária completa com 20 nós e a raiz considerada como estando no nível 0, quantos nós existem no nível 4?

7

8
9
10
11
12 Suponha que você tenha os números de 1 a 1000 em uma árvore binária de busca, e quer localizar o número 363. Qual sequência abaixo não pode ser a sequência de nós examinados.

a) 2, 252, 401, 398, 330, 344, 397, 363.
b) 924, 220, 911, 244, 898, 258, 362, 363.
X c) 925, 202, 911, 240, 912, 245, 363.
d) 2, 399, 387, 219, 266, 382, 381, 278, 363.
e) 935, 278, 347, 621, 299, 392, 358, 363.