Elementos del nivel k de un árbol
Los árboles binarios con valores en las hojas y en los nodos se definen por
|
1 2 |
data Arbol a = H a | N a (Arbol a) (Arbol a) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
7 / \ / \ 2 9 / \ 5 4 |
se representa por
|
1 |
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
|
1 |
nivel :: Int -> Arbol a -> [a] |
tal que nivel k a es la lista de los elementos de nivel k del árbol a. Por ejemplo,
|
1 2 3 4 5 6 |
nivel 0 (H 5) == [5] nivel 1 (H 5) == [] 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)) == [] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 |
data Arbol a = H a | N a (Arbol a) (Arbol a) nivel :: Int -> Arbol a -> [a] nivel 0 (H x) = [x] nivel 0 (N x _ _) = [x] nivel _ (H _ ) = [] nivel k (N _ i d) = nivel (k-1) i ++ nivel (k-1) d |
|
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 27 28 29 30 |
from dataclasses import dataclass from typing import Generic, TypeVar A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): x: A @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def nivel(k: int, a: Arbol[A]) -> list[A]: match (k, a): case (0, H(x)): return [x] case (0, N(x, _, _)): return [x] case (_, H(_)): return [] case (_, N(_, i, d)): return nivel(k - 1, i) + nivel(k - 1, d) assert False |
To solve this problem, we can define a recursive function that traverses the tree and collects the elements of the desired level. We can implement this function using pattern matching on the tree.
Here is a possible solution in Haskell:
This function works as follows:
Falla en el primer ejemplo: nivel 0 (H 5) == [5]
You are right, the function I provided will not work for the case when the tree is a leaf and the desired level is 0.
Here is a revised version of the function that handles this case correctly:
This revised function correctly returns an empty list when the tree is a leaf and the desired level is greater than 0.
With this revised function, the following examples now produce the expected results: