Sustitución en una posición
Los árboles binarios se pueden representar con el de dato algebraico
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
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
Para indicar las posiciones del árbol se define el tipo
type Posicion = [Direccion]
donde
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]
Definir la función
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))
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