Haskell --- Diàmetre d'Arbre Binari T29164


Statement
 

pdf   zip   main.hs

Donat un arbre binari a, volem obtenir el seu diàmetre.

El diàmetre d’un arbre binari es defineix com el nombre d’arestes del camí més llarg entre dos nodes qualsevol. El diàmetre de l’arbre buit és 0. És irrellevant el contingut (el valor) dels nodes, aquesta propietat és una propietat exclusivament de l’estructura de l’arbre.

Per exemple:

image

Escriviu un programa que llegeixi una seqüència d’arbres binaris (donats per un recorregut en preordre amb -11 per a arbres buits) i escrigui el seu diàmetre. Per fer-ho, descarregueu-vos el fitxer code.hs que conté l’esquelet del programa.

El arbres binaris de naturals venen donats per aquest tipus:

data Arbin = Buit | Node Int Arbin Arbin    deriving Show

La funció diametre té tipus Arbin -> (Int, Int). Fixeu-vos que cal retornar el diàmetre de l’arbre i la seva alçada (nombre de nodes entre l’arrel i alguna de les fulles més profundes, ambdós inclosos). Amb aquesta informació de cada fill n’hi ha prou per poder calcular el diàmetre i l’alçada de l’arbre. Així la implementació resulta molt més senzilla i eficient.

Un exemple:

diametre (Node 1 (Node 2 Buit Buit) (Node 3 Buit Buit))

ha de retornar (2,2)

Un altre exemple:

diametre (Node 1 Buit (Node 2 (Node 3 (Node 5 Buit Buit) Buit) (Node 4 Buit (Node 6 Buit Buit))))

ha de retornar (4,4)

La funció convertirEnArbin és de tipus [Int] -> Arbin. Per exemple,

convertirEnArbin [2, 3, -1, -1, -1]

ha de retornar

Node 2 (Node 3 Buit Buit) Buit

Un altre exemple:

convertirEnArbin [11, 2, 3, -1, -1, 10, -1, -1, 3, 5, -1, -1, 4, -1, -1]

ha de retornar

Node 11 (Node 2 (Node 3 Buit Buit) (Node 10 Buit Buit)) (Node 3 (Node 5 Buit Buit) (Node 4 Buit Buit))

Entrada

L’entrada és una seqüència d’arbres binaris, donats pel seu recorregut en preordre i amb la marca −1-1 per indicar els arbres buits. Hi ha un arbre per línia.

Sortida

Per cada arbre de l’entrada, el programa ha d’escriure el seu diàmetre.

Observacions

La correcció valorarà l’eficiència, l’elegància, la senzillesa i la qualitat general de la solució lliurada.

Public test cases

  • Input

    11 2 3 -1 -1 10 -1 -1 3 5 -1 -1 4 -1 -1
5 2 10 -1 -1 8 -1 -1 20 -1 -1
5 2 -1 -1 -1
10 2 3 -1 -1 5 -1 -1 2 3 -1 -1 5 -1 -1 
10 -1 -1
0 0 -1 -1 0 -1 -1
0 -1 0 0 0 -1 -1 -1 0 -1 0 -1 -1

    Output

    4
3
1
4
0
2
4
    • Information
    Author
    Jordi Delgado
    Language
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell