Construcción del árbol a partir de los recorridos preorden e inorden

Los árboles binarios con valores en las hojas y en los nodos se pueden representar con el siguiente tipo

Por ejemplo, el árbol

se representa por

Definir las siguientes funciones

tales que

  • (preorden x) es la lista correspondiente al recorrido preorden del árbol x; es decir, primero visita la raíz del árbol, a continuación recorre el subárbol izquierdo y, finalmente, recorre el subárbol derecho. Por ejemplo,

  • (inorden x) es la lista correspondiente al recorrido inorden del árbol x; es decir, primero recorre el subárbol izquierdo, a continuación visita la raíz del árbol y, finalmente, recorre el subárbol derecho. Por ejemplo,

  • (arboles xs ys) es la lista de los árboles con recorrido preorden xs y recorrido inorden de ys. Por ejemplo,

Comprobar con QuickCheck, que para todo árbol x se verifican las siguientes propiedades

Nota: Para la comprobación, se usa el siguiente generador

Soluciones

[schedule expon=’2016-06-02′ expat=»06:00″]

  • Las soluciones se pueden escribir en los comentarios hasta el 02 de junio.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2016-06-02′ at=»06:00″]

[/schedule]

Un comentario

Leave a Reply to abrdelrodCancel reply