Ejercicio 5 (Árboles ternarios) F
Un árbol ternario está definido de la siguiente forma:
2Si no utilizó la función Espejo para describir EsSimétrico?, vuelva a pensar el ejercicio
Página 2 de ?? Algoritmos y Estructuras de Datos II
TAD Árbol Ternario(α)
géneros at(α)
igualdad observacional
(∀a1, a2 : at(α))
a1 =obs a2 ⇐⇒
nil?(a1) =obs nil?(a2) ∧L (¬ nil?(a1) ⇒Lraíz(a1) =obs raíz(a2) ∧ izq(a1) =obs izq(a2)
∧ med(a1) =obs med(a2) ∧ der(a1) =obs der(a2))

generadores
nil : −→ at(α)
tern : at(α) × at(α) × at(α) × α −→ at(α)
observadores básicos
nil? : at(α) −→ bool
raiz : at(α) a −→ α {¬nil?(a)}
izq : at(α) a −→ at(α) {¬nil?(a)}
med : at(α) a −→ at(α) {¬nil?(a)}
der : at(α) a −→ at(α) {¬nil?(a)}
Fin TAD
Escribir las siguientes funciones sobre árboles ternarios:
a) NivelNormal?, que dado un árbol ternario y un entero k devuelve verdadero si todos los nodos en el nivel k
tienen exactamente 3 hijos no nil . En caso contrario, esta función devuelve falso.
b) Acotado?, que dado un árbol ternario y un entero k devuelve verdadero si todo nivel en el árbol tiene como
máximo k nodos. Acotado? devuelve falso en caso contrario.