Sustitución en una posición
Los árboles binarios se pueden representar con el de dato algebraico
|
1 2 3 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
9 9 / \ / / \ / 8 6 8 / \ / \ / \ 3 2 4 5 3 2 |
se pueden representar por
|
1 2 3 |
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
|
1 |
type Posicion = [Direccion] |
donde
|
1 2 |
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
|
1 2 3 4 5 6 7 |
9 [] 8 [I] 3 [I,I] 2 [I,D] 6 [D] 4 [D,I] 5 [D,D] |
Definir la función
|
1 |
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,
|
1 2 3 4 5 6 7 8 |
λ> 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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 |