Aula Prática #11 - Árvores Binárias
(semana de 11/05 a 15/05)

Nesta aula iremos abordar conceitos de árvores binárias. Será por isso conveniente ver o que foi falado nas teóricas:

Um 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

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.

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
Verificando se uma árvore é "estritamente binária".
Resolva e submeta o problema [ED205] Árvores estritamente binárias.
- Uma árvore é estritamente binária se ambas as suas subárvores (esquerda e direita) foram estritamente binárias.
- Em cada nó, deve verificar se este é válido, ou seja, se é folha ou se tem dois filhos:
Caminhos numa árvore
Resolva e submeta o problema [ED206] Percorrendo caminhos.
- 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? :)

Aqui ficam mais alguns problemas envolvendo árvores para resolver no Mooshak:
- [ED211] Contando os números pares
  - Este problema é muito semelhante a contar o número de nós
  - Ao invés de contar todos, conte apenas aqueles que são divisíveis por 2 (utilize o operador %, que devolve o resto da divisão inteira)
- [ED212] Soma de todos os níveis
  - 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.
- [ED213] Caminho de maior soma
  - Mais um problema sem dicas :) Se tiverem dificuldades usem o Piazza.
Mais alguns exercícios possíveis:
- Crie um método para contar o número de nós que não são folhas
- Crie um método para determinar a folha que fica a menor profundidade da árvore
- Crie um método para substituir todas as ocorrências de um valor na árvore por outro valor

O exercício de desafio desta semana envolve obviamente... árvores!

Não vou dizer mais para não tirar a piada a fazerem o problema, mas se precisarem de dicas, avisem-me.