Bacharel

INF1010 – Lista de Exercícios 2 Árvores 1. Construir algoritmo para dada uma árvore n-ária, transformá-la em uma árvore binária. 2. Qual a maior e menor quantidade de nós que podem existir em uma árvore binária completa de altura h ?

3. Represente a sequência abaixo na forma de árvores binárias de alturas mínima e máxima. s = { 3, 5, 9, 12, 14, 6, 7, 15 }

4. Escrever uma rotina em C para buscar a informação em um nó de uma árvore binária de busca, sendo dada a sua chave. Cuide para que a rotina seja eficiente.

5. Achar o maior elemento (campo numérico) de uma árvore binária dada. 6. Uma árvore binária é zig-zag quando é vazia ou quando não possui nós cheios. Sem usar recursividade, escreva, em C, uma função que recebe o endereço do nó raiz de uma árvore binária e verifica se ela é zig-zag. Se a árvore dada for zig-zag, a função deverá retornar sua altura; caso contrário, deverá retornar –1. Não utilize estruturas de dados auxiliares (pilhas, filas, etc...); apenas variáveis locais dos tipos ponteiro ou inteiro.

7. Uma árvore binária cuja altura é igual ao número de nós pode possuir nós cheios ? Justifique. 8. Desenhe uma árvore estritamente binária com 7 nós para a qual os percursos em pré-ordem e inordem produzem a mesma sequência de visitas.

9. Toda árvore binária cheia é completa. 10. Dados os percursos abaixo, reconstruir a árvore original: pré-ordem: 1, 2, 3, 6, 8, 4, 9, 10, 12, 11, 5, 7, I simétrica (in-ordem) : 6, 3, 8, 2, 4, 9, 12, 10, 11, 1, I, 7, 5

11. Escrever rotina em pseudo-código e em C para percorrer uma árvore binária qualquer, em nível, das folhas para a raiz. Indique a complexidade do algoritmo.

12. Responda Certo ou Errado, justificando.

a. Qualquer que seja o número de chaves, é sempre possível construir com elas uma árvore binária completa. b. Qualquer que seja o número de chaves, é sempre possível construir com elas uma árvore binária cheia. c. Uma árvore binária que possui as folhas no