Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 20 de Janeiro
(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 #12]
Neste problema deverá apenas submeter uma classe BTree<T> (e não um programa completo).
O código base são as classes de árvores binárias dadas nas aulas. Pode fazer download de um único ficheiro zip contendo todos os códigos-fonte (ficheiros .java) necessários. Use como base a classe BTree<T>, que é a única que deverá submeter.
As árvores são das mais antigas criaturas da Terra dos Dados, conhecidas por serem defensoras das florestas e do mundo livre, combatendo ferozmente o cruel Senhor das Trevas e da Ineficiência. A espécie mais conhecida destas criaturas é a árvore binária, que precisa da tua ajuda para aumentar o seu poder com novos métodos.
Deve acrescentar à classe BTree dada os seguintes métodos (não modificando nenhum dos métodos já existentes no código base):
Os 3 primeiros exemplos correspondem às três árvores da figura.
Árvore t em preorder | Valor devolvido por t.internal() |
---|---|
6 3 2 N N 5 N N 10 N 25 N N | 3 |
6 3 2 N N N 10 N N | 2 |
6 3 N N 10 N N | 1 |
6 N N | 0 |
N | 0 |
A árvore em todos os exemplos corresponde à árvore da figura.
Árvore t em preorder | Chamada | Estado da árvore depois da chamada, em preorder (com nulls) |
---|---|---|
6 3 2 1 N N N 5 N 7 N N 10 8 N 9 N N 25 N N | t.cut(3) | 6 3 2 N N 5 N N 10 8 N N 25 N N |
6 3 2 1 N N N 5 N 7 N N 10 8 N 9 N N 25 N N | t.cut(2) | 6 3 N N 10 N N |
6 3 2 1 N N N 5 N 7 N N 10 8 N 9 N N 25 N N | t.cut(1) | 6 N N |
6 3 2 1 N N N 5 N 7 N N 10 8 N 9 N N 25 N N | t.cut(0) | N |
6 3 2 1 N N N 5 N 7 N N 10 8 N 9 N N 25 N N | t.cut(-1) | N |
6 3 2 1 N N N 5 N 7 N N 10 8 N 9 N N 25 N N | t.cut(42) | 6 3 2 1 N N N 5 N 7 N N 10 8 N 9 N N 25 N N |
Os 4 primeiros exemplos correspondem às quatro árvores da figura.
Árvore t em preorder | Array devolvido por t.maxLevel() |
---|---|
6 3 2 1 N N N 5 N 7 N N 10 8 N 9 N N 25 N N | [4,1] |
6 3 2 N N 5 N N 10 N N | [2,2] |
6 3 N 5 N 7 N N 10 8 N 9 N N 25 N N | [3,1] |
6 3 2 1 N N N N N | [1,4] |
42 N N | [1,1] |
Estruturas de Dados (CC1007)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto