Clojure - Arbre binari Z92223

Statement

thehtml

[r]

Aquest problema planteja el treball amb arbres binaris.

Penseu un tipus en clojure per guardar arbres binaris de nombres naturals.

Definiu, amb la funció def, t1 com l’arbre que mostra la figura.

Feu el mateix amb t2 i t3 tenin en compte que són els seu dos fills.

Feu una funció size que, donat un arbre, retorni la seva talla, és a dir, el nombre de nodes que conté.
Feu una funció height que, donat un arbre, retorni la seva alçada, assumint que els arbres buits tenen alçada zero.
Feu una funció equal que, donat dos arbres, indiqui si són el mateix.
Feu una funció pre-order que, donat un arbre, retorni el seu recorregut en pre-ordre.
Feu una funció post-order que, donat un arbre, retorni el seu recorregut en post-ordre.
Feu una funció in-order que, donat un arbre, retorni el seu recorregut en in-ordre.
Feu una funció breadth-first que, donat un arbre, retorni el seu recorregut per nivells.
Feu una funció build que, donat el recorregut en pre-ordre d’un arbre i el recorregut en in-ordre del mateix arbre, retorni l’arbre original. Assumiu que l’arbre no té elements repetits.

Puntuació

Cada apartat puntua 12,5 punts.

Public test cases

Input

(size t1)
(height t1)
(equal t2 t3)
(pre-order t1)
(post-order t1)
(in-order t1)
(breadth-first t1)
(post-order (build (pre-order t1) (in-order t1)))

Output

7
3
false
(1 2 4 5 3 6 7)
(4 5 2 6 7 3 1)
(4 2 5 1 6 3 7)
(1 2 3 4 5 6 7)
(4 5 2 6 7 3 1)

Information