Nodos con k sucesores
Los árboles se pueden representar mediante el siguiente tipo de datos
|
1 2 |
data Arbol a = N a [Arbol a] deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 |
1 1 1 / \ / \ / \ 8 3 8 3 8 3 | /|\ /|\ | 4 4 5 6 4 5 6 7 |
se representan por
|
1 2 3 4 |
ej1, ej2, ej3 :: Arbol Int ej1 = N 1 [N 8 [],N 3 [N 4 []]] ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]] ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]] |
Definir la función
|
1 |
nodos :: Int -> Arbol a -> [a] |
tal que (nodos k x) es la lista de los nodos del árbol x que tienen k sucesores. Por ejemplo,
|
1 2 3 4 5 |
nodos 0 ej1 == [8,4] nodos 1 ej1 == [3] nodos 2 ej1 == [1] nodos 3 ej1 == [] nodos 3 ej2 == [3] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 |
data Arbol a = N a [Arbol a] deriving Show ej1, ej2, ej3 :: Arbol Int ej1 = N 1 [N 8 [],N 3 [N 4 []]] ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]] ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]] nodos :: Int -> Arbol a -> [a] nodos k (N x ys) | k == length ys = x : concatMap (nodos k) ys | otherwise = concatMap (nodos k) ys |
3 Comentarios