Subárbol de profundidad dada

El árbol binario

se puede representar por

El tipo de los árboles binarios se puede definir por

La función take está definida por

Definir la función

tal que takeArbol n t es el subárbol de t de profundidad n. Por ejemplo,

Comprobar con QuickCheck que la profundidad de takeArbol n x es menor o igual que n, para todo número natural n y todo árbol x.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Un comentario

  1. Podemos definir la función takeArbol de la siguiente manera:

    La idea es que si el número de profundidad es 0, entonces devolvemos el nodo actual como hoja (H x). Si no, continuamos recursivamente con los hijos izquierdo y derecho, disminuyendo en 1 el número de profundidad restante.

    Para comprobar con QuickCheck que la profundidad del subárbol resultante es menor o igual que n, podemos definir la función profundidad que calcula la profundidad de un árbol, y luego escribir la propiedad que queremos probar:

    Para comprobar esta propiedad con QuickCheck, podemos usar la siguiente función:

    Ejecutando este código, QuickCheck generará aleatoriamente valores de n y árboles x, y comprobará que la propiedad se cumple para todos ellos. Si QuickCheck no encuentra ningún caso en el que la propiedad no se cumpla, entonces podemos estar seguros de que la función takeArbol está implementada correctamente.

    Pregunta ¿Se puede reducir el número de ecuaciones de takeArbol?

    Respuesta Sí, es posible reducir el número de ecuaciones de takeArbol a una sola, usando una condición if para decidir si devolver el nodo actual como hoja (H x) o continuar recursivamente con los hijos. La definición de la función quedaría de la siguiente manera:

    En este caso, la propiedad que queremos comprobar con QuickCheck sigue siendo válida,

Escribe tu solución