Estruturas de Dados - Lista de exercícios 4

1. Desenhe a árvore binária cuja pré-ordem é

         A B C E F G I H J D

   e cuja in-ordem é

         A C E I G F H J B D

   Mostre como você chegou a resposta.

2. Ache todas as árvores binárias cujos nós aparecem na mesma sequência em ambas as ordens seguintes:
   1. pré-ordem e in-ordem
   2. pré-ordem e pós-ordem
   3. pós-ordem e in-ordem
3. Usando alocação ligada, uma árvore binária é facilmente representada usando nós com campos llink, info, rlink. Apresente alguma(s) outra(s) maneira(s) de se representar árvores genéricas cujos nós podem ter um número variados de filhos. Discuta as vantagens e desvantagens de cada representação, quanto ao espaço utilizado e tempo para sua manipulação.
4. Escreva um algoritmo breadthfirst(T) que percorre uma árvore binária T em ordem ``breadth-first'' ou ``por alargamento'', visitando primeiro a raiz (nível 1), em seguida os seus filhos (nível 2) da esquerda para a direita, e assim sucessivamente. Caso precise de alguma estrutura de dado auxiliar, especifique qual, e suponha existentes rotinas para a sua manipulação.
5. Tente (sem entregar) os exercícios referentes a árvores binárias do livro de Knuth.

 
• About this document ...