Mooshak #04 - Árvores Binárias
(semana de 29/11 a 03/12)
Nota Inicial
Os exercício do Mooshak desta aula não contam para nota e são completamente opcionais (a vossa prioridade deve ser primeiro completar os exercícios base das aulas práticas). Os exercícios aqui colocados destinam-se a quem quer ir mais além do que requisitos mínimos e quiser ter uma camada de submissão com avaliação automática, sendo que todas as semanas iremos colocar disponíveis novos problemas.
Para tornar tudo um pouco mais interessante, eu (Pedro Ribeiro) deixo desde já prometido que irei pagar uma refeição na minha companhia (uma francesinha no Capa Negra II) a três estudantes desta UC:
Os 2 estudantes com mais problemas corretamente submetidos no final do semestre (sob um código de conduta de não tentarem simplesmente "copiar código").
Um outro estudante que se tenha destacado nesta componente, segundo a minha avaliação (ex: resolveu os problemas mais difíceis, teve o código mais criativo, etc).
Espero para ver os vosses "dotes" algorítmicos ao longo destas semanas! :)
Problemas para submissão
Nesta unidade curricular vamos usar o sistema Mooshak como uma maneira opcional e adicional para avaliar automaticamente código.
Nesta aula foram disponibilizados os seguintes problemas:
Não precisa de usar a classe de árvores para este problema (é um pouco overkill para algo tão simples), mas também não é proibido usá-la (note que no Mooshak só pode submeter um ficheiro, pelo que teria de ter todas as classes nesse mesmo ficheiro)
Para este problema basta por exemplo guardar os filhos de cada nó
Uma maneira simples de o resolver é fazer uma função recursiva simples que recebe um nó e devolve 1 + maximo(altura(filho_esquerdo), altura(filho_direito))
Como parar a recursão? Qual o caso base? Qual é por exemplo a altura de uma folha? E se o nó apenas tiver o filho esquerdo? (ou o filho direito?)
Exercício 2) Um segundo problema com árvores: número de nós em cada nível
O segundo problema é uma extensão do primeiro, com a árvore a ser dada da mesma forma, mas com o que é pedido a ser um pouco "menos simples".
Para resolver pode por exemplo criar um array do tamanho de 1+altura da árvore para guardar os resultados a imprimir (e pode calcular a altura... usando o método que escreveu para o exercício anterior!)
Tendo o array, pode fazer uma função recursiva para percorrer a árvore e passar como argumento a profundidade atual: desse modo pode incrementar o array na posição respetiva à medida que percorre a árvore
No final basta imprimir o array: tenha o cuidado de não imprimir espaços a mais no final do último número imprimido
Exercício 3) Um exercício sobre árvores binárias de pesquisa
Como ler o input? Pode ler recursivamente se por exemplo criar um método que devolve a árvore. Desse modo é só ler o valor e depois ler recursivamente a subárvore esquerda e a subáravore direita.
Os limites são pequenos pelo que pode resolver fazendo várias passagens pela árvore, mas é possível resolver com uma única passagem. Como?
Entre várias alternativas possíveis, pode percorrer a árvore mantendo como argumentos o intervalo [a,b] onde os números dessa (sub)árvore devem estar. Cada vez que vai para a direita ou esquerda apenas precisa de atualizar o intervalo respetivo tendo em conta o valor atual (que impõe novas restrições nos números abaixo).
Exercício de Desafio
Para esta semana o desafio é um pouco mais simples que os anteriores. Deve tentar resolver o seguinte problema, que está disponível para submissão no Mooshak:
