62
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up

Devemos desenhar as árvores livres, enraizadas ordenadas e binárias, com os nós x, y e z.

Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up

Aqui estão as de vértices livres, isto é, aquelas que não tem uma raiz:

Picture 1 Picture 3 Picture 4

Picture 5 Picture 6 Picture 7

Picture 9

Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up

Aqui estão as árvores com raiz x (raiz marrom e folha verde):

Picture 14 Picture 16

Picture 36

Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up

Aqui estão as árvores ordenadas, isto é, árvores onde as sub-árvores formam conjuntos ordenados, ou seja, os filhos de um nó estão ordenados da esquerda para a direita:

Picture 37 Picture 39 Picture 40

Picture 41 Picture 43

Picture 42 Picture 44

Picture 45 Picture 46

Note que podemos trocar y e z ou os valores de cada vértice para obtermos mais árvores análogas.

Aqui estão as árvores binárias, isto é, aquelas em que cada nó tem no máximo dois filhos:

Picture 27 Picture 32 Picture 33

Picture 34 Picture 35

Note que devemos trocar y e z para obter as árvores restantes.

Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up

Desenhamos, portanto, cada uma das árvores pedidas, sendo que suas definições estão ao longo da resolução.

Navegar por capítulo