Rama izquierda de un árbol binario
Los árboles binarios con valores en los nodos se pueden definir por
1 2 3 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Por ejemplo, el árbol
1 2 3 4 5 6 |
9 / \ / \ 8 6 / \ / \ 3 2 4 5 |
se puede representar por
1 |
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
1 |
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,
1 2 |
λ> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) [2,5,3] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 |
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 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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 |
Para resolver este problema, podemos utilizar una función recursiva que, para cada nodo del árbol, devuelva la lista de los valores de los nodos de la rama izquierda de su hijo izquierdo y, además, añada el valor del propio nodo a la lista.
Así, podemos implementar la función de la siguiente manera:
La función primero comprueba si el árbol es un nodo nulo (caso base). Si es así, devuelve la lista vacía. En caso contrario, añade el valor del nodo a la lista y llama a sí misma recursivamente para calcular la rama izquierda del hijo izquierdo del nodo.
Por ejemplo, si queremos calcular la rama izquierda del árbol que has mencionado como ejemplo, la función se ejecutaría de la siguiente manera: