Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 17 de Dezembro
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #10]
Neste problema deverá apenas submeter uma classe BTree<T> (e não um programa completo).
Use como base a classe BTree<T> (ver código | download de BTNode.Java e BTree.Java), que representa uma árvore binária, tal como dada nas aulas).
Acrescente à classe dada um novo método public int nodesLevel(int k) que devolve o número de nós num dado nível de profundidade. É garantido que k é um nível de profundidade válido (ou seja, com pelo menos um nó da árvore nesse nível).
A figura seguinte ilustra uma árvore e o número de nós que tem em cada nível de profundidade:
Deverá submeter apenas a classe BTree<T>, acrescentando o método nodesLevel como pedido (e sem apagar ou modificar nenhum dos outros métodos dados como base). Pode assumir que terá acesso no Mooshak à classe BTNode<T> (não a pode mudar) e se precisar pode criar outros métodos auxiliares. O Mooshak irá criar várias instâncias da sua classe e irá fazer uma série de testes ao método por si implementado.
Os exemplos correspondem à arvore da figura, ou seja, t = 6 3 2 N 1 N N 5 N 7 N N 10 8 N 9 N N 25 N N
Chamada | Valor de retorno |
---|---|
t.nodesLevel(0) | 1 |
t.nodesLevel(1) | 2 |
t.nodesLevel(2) | 4 |
t.nodesLevel(3) | 3 |
Estruturas de Dados (CC1007)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto