Lista de Exercicios Resolvidos - Arvores Binarias - IFPR

Estrutura de Dados Arvores Binarias Professor Aleffer Rocha Instituto Federal do Parana Campus Telˆemaco Borba Lista de exercıcios Observacoes os exercıcios devem ser realizados no caderno Apos o termino dos exercıcios tire uma foto de cada pagina que vocˆe utilizou do seu caderno para a resolucao dos exercıcios e poste no classroom da disciplina na atividade Arvores Binarias E valido ressaltar que a nao entrega da lista de exercıcios implicara diretamente em conceito D nela Alunos que entregarem a atividade com atraso poderao atingir conceito maximo B nela 1 Ao remover um no em uma arvore binaria de pesquisa considerase trˆes casos 1 o no a ser removido e um no folha 2 o no a ser removido e um no com um unico filho e o caso em que o no a ser removido tem dois filhos Apresente um pseudocodigo para cada um desses casos 2 Utilizando a estrutura de dados pilha escreva um pseudocodigo de uma versao nao re cursiva dos seguintes algoritmos a Preordem b Em Ordem c Posordem 3 Considerando a seguinte sequˆencia de numeros inteiros 65 32 72 54 89 21 78 42 65 10 99 32 54 realize as operacoes listadas a seguir a todos os estados da arvore binaria de pesquisa apos a insercao de cada um dos numeros observe que serao 13 arvores apresentadas neste item b apresente a sequˆencia de nos impressos na tela quando executado o algoritmo Pos ordem na ultima arvore binaria apresentada por vocˆe no item a c remova um no cujo valor inteiro seja um numero par da ultima arvore binaria de pesquisa apresentada por vocˆe no item a Indique em qual dos trˆes casos da remocao de acordo com o Exercıcio 1 esta remocao se aplica Por fim apresente a arvore binaria de pesquisa resultante apos a remocao deste no d apresente a sequˆencia de nos impressos na tela quando executado o algoritmo Pre ordem na ultima arvore apresentada por vocˆe no item c e remova um no cujo valor inteiro seja um numero ımpar da ultima arvore binaria de pesquiisa apresentada por vocˆe no item c Indique em qual dos trˆes casos da remocao de acordo com o Exercıcio 1 esta remocao se aplica Por fim apresente a arvore binaria de pesquisa resultante apos a remocao deste no f apresente a sequˆencia de nos impressos na tela quando executado o algoritmo Em Ordem na ultima arvore apresentada por vocˆe no item e 4 A respeito de arvores binarias de pesquisa balanceadas a O que e uma arvore binaria de pesquisa balanceada b Quando utilizar uma arvore binaria de pesquisa balanceada c Quais as vantagens de uma arvore binaria de pesquisa balanceada d A ultima arvore apresentada por vocˆe nos Exercıcios 3a 3c e 3e sao arvores balanceadas Por quˆe e Apresente uma arvore binaria de pesquisa balanceada utilizando como nos os inteiros 23 32 10 73 37 13 31 e 8 Ao final diga qual arvore binaria de pesquisa balanceada que vocˆe utilizou para representar a sua arvore