Los árboles binarios se pueden representar con el de dato algebraico
data Arbol a = H
| N a (Arbol a) (Arbol a)
deriving Show |
data Arbol a = H
| N a (Arbol a) (Arbol a)
deriving Show
Por ejemplo, los árboles
9 9
/ \ /
/ \ /
8 6 8
/ \ / \ / \
3 2 4 5 3 2 |
9 9
/ \ /
/ \ /
8 6 8
/ \ / \ / \
3 2 4 5 3 2
se pueden representar por
ej1, ej2:: Arbol Int
ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H |
ej1, ej2:: Arbol Int
ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H
Para indicar las posiciones del árbol se define el tipo
type Posicion = [Direccion] |
type Posicion = [Direccion]
donde
data Direccion = D | I
deriving Eq |
data Direccion = D | I
deriving Eq
representa un movimiento hacia la derecha (D) o a la izquierda. Por ejemplo, las posiciones de los elementos del ej1 son
9 []
8 [I]
3 [I,I]
2 [I,D]
6 [D]
4 [D,I]
5 [D,D] |
9 []
8 [I]
3 [I,I]
2 [I,D]
6 [D]
4 [D,I]
5 [D,D]
Definir la función
sustitucion :: Posicion -> a -> Arbol a -> Arbol a |
sustitucion :: Posicion -> a -> Arbol a -> Arbol a
tal que (sustitucion ds z x) es el árbol obtenido sustituyendo el elemento de x en la posición ds por z. Por ejemplo,
λ> sustitucion [I,D] 7 ej1
N 9 (N 8 (N 3 H H) (N 7 H H)) (N 6 (N 4 H H) (N 5 H H))
λ> sustitucion [D,D] 7 ej1
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 7 H H))
λ> sustitucion [I] 7 ej1
N 9 (N 7 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
λ> sustitucion [] 7 ej1
N 7 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H)) |
λ> sustitucion [I,D] 7 ej1
N 9 (N 8 (N 3 H H) (N 7 H H)) (N 6 (N 4 H H) (N 5 H H))
λ> sustitucion [D,D] 7 ej1
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 7 H H))
λ> sustitucion [I] 7 ej1
N 9 (N 7 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
λ> sustitucion [] 7 ej1
N 7 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
Soluciones
data Arbol a = H | N a (Arbol a) (Arbol a)
deriving (Eq, Show)
ej1, ej2:: Arbol Int
ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H
data Direccion = D | I
deriving Eq
type Posicion = [Direccion]
sustitucion :: Posicion -> a -> Arbol a -> Arbol a
sustitucion (I:ds) z (N x i d) = N x (sustitucion ds z i) d
sustitucion (D:ds) z (N x i d) = N x i (sustitucion ds z d)
sustitucion [] z (N _ i d) = N z i d |
data Arbol a = H | N a (Arbol a) (Arbol a)
deriving (Eq, Show)
ej1, ej2:: Arbol Int
ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H
data Direccion = D | I
deriving Eq
type Posicion = [Direccion]
sustitucion :: Posicion -> a -> Arbol a -> Arbol a
sustitucion (I:ds) z (N x i d) = N x (sustitucion ds z i) d
sustitucion (D:ds) z (N x i d) = N x i (sustitucion ds z d)
sustitucion [] z (N _ i d) = N z i d
Se puede imprimir o compartir con
4 soluciones de “Sustitución en una posición”