É encorajado que vão falando com os docentes e outros colegas se tiverem dificuldades. No entanto, qualquer ajuda mais direta que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem. Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota.
Cada aula vale 10% da nota desta componente. Como existem 12 aulas com submissões, pode ter pontuação máxima mesmo sem ter feito tudo.
Para um problema contar tem acertar todos os testes (ou seja, ter accepted). Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Para ter 100% bastará sempre resolver os exercícios do guião principal.
Conteúdos das teóricas
Nesta aula iremos abordar conceitos de árvores binárias. Será por isso conveniente ver o que foi falado nas teóricas:
Uma primeira árvore binária.
Uma maneira de descrever uma árvore é usar uma das seguintes representações:
preorder: raíz, seguida da representação prenorder da subárvore esquerda, seguida da representação preorder da subárvore direita.
inorder: representação inorder da subárvore esquerda, seguida da raíz, seguida da representação inorder da subárvore direita.
postorder: representação postorder da subárvore esquerda, seguida da representação postorder da subárvore direita, seguida da raíz.
em largura: nós por ordem crescente de profundidade (de cima para baixo) e no mesmo nível da esquerda para a direita
Considere a árvore binária da figura seguinte:
Nas 4 representações anteriores, a árvore da figura seria descrita do seguinte modo:
preorder: 5 1 8 6 7 2
inorder: 8 1 6 5 2 7
postorder: 8 6 1 2 7 5
em largura: 5 1 7 8 6 2
Percebendo as várias ordens de visita aos nós
Para garantir que percebeu, procure agora escrever no seu caderno as 4 representações como descritas para a seguinte árvore (preorder, inorder, postorder, em largura):
preorder: 6 8 4 3 5 1 7
inorder: 8 4 6 1 5 3 7
postorder: 4 8 1 5 7 3 6
em largura: 6 8 3 4 5 7 1
Exercício 2) Introdução à implementação de Árvores Binárias
Código de Árvores Binárias.
Faça download do código dado nas teóricas e compile-o:
BTree - Árvore binária simples (exemplo de métodos: número de nós, altura, contains; impressões preorder, inorder, postorder, em largura)
Espreite o ficheiro BTNode.java para ver como um nó é descrito por três atributos: value, left e right. Veja também no ficheiro BTree.java como o único atributo de uma árvore é a sua raíz (root)
Um primeiro teste.
Crie um ficheiro input.txt contendo a seguinte linha: 5 1 8 N N 6 N N 7 2 N N N. Esta é a representação preorder da árvore binária da figura seguinte (onde N representa explicitamente um nó nulo).
(as duas representações da imagems referem-se à mesma árvore)
Agora execute a classe de teste das árvores dando como input o ficheiro que criou:
$ java TestBTree < input.txt
Procure acompanhar cada uma das linhas de código de TestBTree.java e o seu efeito, usando os slides para cimentar o seu vocabulário de árvores. Espreite também Para os métodos numberNodes, depth e contains
Um segundo teste.
Crie um ficheiro input2.txt contendo a descrição preorder da árvore binária de 7 nós descrita na figura da pergunta 1.2. Execute novamente TestBTree, agora com este novo input, e verifique se os resultados são os esperados.
Exercício 3) Vários exercícios de árvores
Contando o número de folhas.
O método numberNodes conta o número de nós. Para garantir que percebeu como funciona, vamos agora fazer um exercício parecido. Resolva e submeta o problema [ED204] Contando folhas.
O número de folhas de uma árvore é igual ao número de folhas da subárvore esquerda mais o número de folhas da subárvore direita
Um caso base é quando o nó é uma folha... nesse caso devemos devolver 1
Outro caso base é quando a árvore é nula... nessa caso devemos devolver 0
Olhar para a primeira letra permite decidir se devemos ir para a esquerda ou para a direita. Qual o método da classe String para ver um caracter numa dada posição?
Depois de avançar, falta processar o resto do caminho (tudo excepto a primeira letra). Consegue ver um método da classe String que lhe permite obter todos os caracteres excepto o primeiro?
Número de nós a uma dada profundidade
Resolva e submeta o problema [ED207] Nós profundos.
E que tal resolverem um problema sem ser dada nenhuma dica? :)
Exercícios extra para consolidação de conhecimentos
Aqui ficam mais alguns problemas envolvendo árvores para resolver no Mooshak:
Comece por criar um array com tamanho igual à altura + 1 (note que já tem disponível um método para ver a altura)
Faça um método auxiliar para contar a soma apenas de um dado nível
Faça um ciclo para passar por todos os níveis, chamando para cada um o método auxiliar que criou anteriorment e colocando o resultado na posição respectiva do array.
