Elementos del nivel k de un árbol

José A. Alonso

02-01-2023

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)

Por ejemplo, el árbol

se representa por

   N 7 (N 2 (H 5) (H 4)) (H 9)

Un elemento de un árbol se dirá de nivel k si aparece en el árbol a distancia k de la raíz.

Definir la función

   nivel :: Int -> Arbol a -> [a]

tal que nivel k a es la lista de los elementos de nivel k del árbol a. Por ejemplo,

   nivel 0 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [7]
   nivel 1 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [2,9]
   nivel 2 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [5,4]
   nivel 3 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  []

Existencia de elementos del árbol que verifican una propiedad

José A. Alonso

30-12-2022

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, el árbol

se representa por

   N 5 (N 3 (H 1) (H 4)) (H 2)

Definir la función

   algunoArbol :: Arbol t -> (t -> Bool) -> Bool

tal que algunoArbol a p se verifica si algún elemento del árbol a cumple la propiedad p. Por ejemplo,

   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4)  ==  True
   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7)  ==  False

Árboles con igual estructura

José A. Alonso

29-12-2022

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, los árboles

        5              8             5           5
       / \            / \           / \         / \
      /   \          /   \         /   \       /   \
     9     7        9     3       9     2     4     7
    / \   / \      / \   / \     / \               / \
   1   4 6   8    1   4 6   2   1   4             6   2

se pueden representar por

   ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int
   ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
   ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))
   ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)
   ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

Definir la función

   igualEstructura :: Arbol -> Arbol -> Bool

tal que igualEstructura a1 a2 se verifica si los árboles a1 y a2 tienen la misma estructura. Por ejemplo,

   igualEstructura ej3arbol1 ej3arbol2 == True
   igualEstructura ej3arbol1 ej3arbol3 == False
   igualEstructura ej3arbol1 ej3arbol4 == False

Árboles con bordes iguales

José A. Alonso

28-12-2022

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en las hojas se pueden definir por

   data Arbol a = H a
                | N (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, los árboles

   árbol1          árbol2       árbol3     árbol4
      o              o           o           o
     / \            / \         / \         / \
    1   o          o   3       o   3       o   1
       / \        / \         / \         / \
      2   3      1   2       1   4       2   3

se representan por

   arbol1, arbol2, arbol3, arbol4 :: Arbol Int
   arbol1 = N (H 1) (N (H 2) (H 3))
   arbol2 = N (N (H 1) (H 2)) (H 3)
   arbol3 = N (N (H 1) (H 4)) (H 3)
   arbol4 = N (N (H 2) (H 3)) (H 1)

Definir la función

   igualBorde :: Eq a => Arbol a -> Arbol a -> Bool

tal que igualBorde t1 t2 se verifica si los bordes de los árboles t1 y t2 son iguales. Por ejemplo,

   igualBorde arbol1 arbol2  ==  True
   igualBorde arbol1 arbol3  ==  False
   igualBorde arbol1 arbol4  ==  False

Árboles balanceados

José A. Alonso

27-12-2022

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en los nodos se pueden definir por

   data Arbol a = H
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Diremos que un árbol está balanceado si para cada nodo la diferencia entre el número de nodos de sus subárboles izquierdo y derecho es menor o igual que uno.

Definir la función

   balanceado :: Arbol a -> Bool

tal que (balanceado a) se verifica si el árbol a está balanceado. Por ejemplo,

   λ> balanceado (N 5 H (N 3 H H))
   True
   λ> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H))))
   False

Rama izquierda de un árbol binario.

José A. Alonso

26-12-2022

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en los nodos se pueden definir por

   data Arbol a = H
                | N a (Arbol1 a) (Arbol1 a)
     deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Definir la función

   ramaIzquierda :: Arbol a -> [a]

tal que ramaIzquierda a es la lista de los valores de los nodos de la rama izquierda del árbol a. Por ejemplo,

   λ> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H))
   [2,5,3]

<!-- TEASER_END -->~~~
# Soluciones

A continuación se muestran las [soluciones en Haskell](#haskell) y las [soluciones en Python](#python).

<a name="haskell"></a>
## Soluciones en Haskell

~~~haskell
data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)

ramaIzquierda :: Arbol a -> [a]
ramaIzquierda H         = []
ramaIzquierda (N x i _) = x : ramaIzquierda i

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    pass

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def ramaIzquierda(a: Arbol[A]) -> list[A]:
    match a:
        case H():
            return []
        case N(x, i, _):
            return [x] + ramaIzquierda(i)
    assert False

Suma de un árbol

José A. Alonso

23-12-2022

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en los nodos se pueden definir por

   data Arbol a = H
                | N a (Arbol1 a) (Arbol1 a)
     deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Definir por recursión la función

   sumaArbol :: Num a => Arbol1 a -> a

tal sumaArbol x es la suma de los valores que hay en el árbol x. Por ejemplo,

   sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21

El tipo de los árboles binarios con valores en los nodos

José A. Alonso

23-12-2022

Tipos definidos y tipos de datos algebraicos

1. El tipo de los árboles binarios con valores en los nodos en Haskell

El árbol, con valores en los nodos,

           9
          / \
         /   \
        /     \
       8       6
      / \     / \
     3   2   4   5
    /\  /\  /\   /\
   ·  ··  ··  · ·  ·

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

usando el tipo de los árboles con valores en los nodos definido como se muestra a continuación.

data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)

2. El tipo de los árboles binarios con valores en los nodos en Python

El árbol binario, con valores en los nodos,

           9
          / \
         /   \
        /     \
       8       6
      / \     / \
     3   2   4   5
    /\  /\  /\   /\
   ·  ··  ··  · ·  ·

se puede representar por

   N(9, N(8, N(3, H(), H()), N(2, H(), H())), N(6, N(4, H(), H()), N(5, H(), H())))

usando el tipo de los árboles binarios con valores en los nodos definido como se muestra a continuación.

from dataclasses import dataclass


@dataclass
class Arbol:
    pass

@dataclass
class H(Arbol):
    pass

@dataclass
class N(Arbol):
    x: int
    i: Arbol
    d: Arbol

Árbol de profundidad n con nodos iguales

José A. Alonso

22-12-2022

Tipos definidos y tipos de datos algebraicos

El árbol binario

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir las funciones

   repeatArbol    :: a -> Arbol a
   replicateArbol :: Int -> a -> Arbol a

tales que

repeatArbol x es es árbol con infinitos nodos x. Por ejemplo,

     takeArbol 0 (repeatArbol 3) == H 3
     takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)
     takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))

replicate n x es el árbol de profundidad n cuyos nodos son x. Por ejemplo,

     replicateArbol 0 5  ==  H 5
     replicateArbol 1 5  ==  N 5 (H 5) (H 5)
     replicateArbol 2 5  ==  N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))

Subárbol de profundidad dada

José A. Alonso

21-12-2022

Tipos definidos y tipos de datos algebraicos

El árbol binario

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

La función take está definida por

   take :: Int -> [a] -> [a]
   take 0            = []
   take (n+1) []     = []
   take (n+1) (x:xs) = x : take n xs

Definir la función

   takeArbol ::  Int -> Arbol a -> Arbol a

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

   takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9
   takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)
   takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
   takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)

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.