Lista de exercicios 8 Estrutura de Dados I

Prévia do material em texto

�PAGE �
�PAGE �1�
Universidade Estadual do Ceará
Bacharelado em Ciência da Computação
Disciplina de Estrutura de Dados I
Prof. Jorge Luiz de Castro e Silva
ATENÇÃO: esta lista é para ser resolvida e entregue até o dia 30/11/2017. NÃO RECEBEREI após esta data. Estes exercícios podem ser feitos manualmente, e depois de escaneados ou fotografados, devem ser enviados para meu e-mail (jlcs53@gmail.com). ATENÇÃO: Colocar no título do e-mail: “8ª Lista de ED I – Nome do Aluno”. 
8ª Lista de exercícios
Escreva uma função não recursiva que faça percurso ou varredura r-e-d (pré-ordem) de uma árvore binária. Dica: use uma pilha para varrer os nós visitados, (use as funções push e pop empilhar e desempilhar os nós visitados). 
Escreva uma função não recursiva que faça percurso ou varredura e-d-r (pós-ordem) de uma árvore binária. Obrigatório usar uma pilha para esta função (use as funções push e pop para empilhar e desempilhar os nós visitados). 
Dada uma ABB (Árvore binária de Busca) inicialmente vazia, insira (e DESENHE) os seguintes elementos (nessa ordem): M, F, S, D, J, P, U, A, E, H, Q, T, W, K.
Dada uma ABB inicialmente vazia, insira (e DESENHE) os seguintes elementos (nessa ordem): A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z.
Descreva a ordem de visita para um percurso em pré-ordem, em-ordem (simétrica) e pós-ordem na arvore abaixo
Qual a diferença de uma ABB (Árvore Binária de Busca) para uma AVL?
O que difere na implementação da função de busca de uma ABB e de uma AVL?
Obtenha a equação que relaciona a altura de uma árvore binária completa com o seu número de vértices.
Explique as vantagens e desvantagens de usar árvores binárias balanceadas?
Escreva uma função não recursiva que faça o percurso em nível em uma árvore binária. O percurso em nível (ou em largura) em uma árvore é um percurso que visita, em ordem crescente, todos os nós de um nível (mesma altura) antes de continuar a visita no nível seguinte. Uma das formas de implementar é utilizar uma fila (FIFO) para guardar quais serão os próximos nós a serem visitados. Portanto, use estrutura de fila para esta função.
BOM ESTUDO