Menu Close

Sustitución en una posición

José A. Alonso,

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
Inicial
, ,

4 soluciones de “Sustitución en una posición”

  1. Responder
    paumacpar 
    sustitucion :: Posicion -> a -> Arbol a -> Arbol a
sustitucion [] z (N a i d) = (N z i d)
sustitucion (x:xs) z (N a i d)
  | x == I    = N a (sustitucion xs z i) d
  | otherwise = N a i (sustitucion xs z d)
  2. Responder
    enrnarbej 
    sustitucion :: Posicion -> a -> Arbol a -> Arbol a
sustitucion (I:xs) n (N a is ds) = N a (sustitucion xs n is) ds
sustitucion (D:xs) n (N a is ds) = N a is (sustitucion xs n ds)
sustitucion []     n (N a is ds) = N n is ds
sustitucion _      _ H           = H
  3. Responder
    albcercid 
    sustitucion _ _ H = H
sustitucion [] z (N a b c) = N z b c
sustitucion (d:ds) z (N a b c)
  | d == D    = N a b (sustitucion ds z c)
  | otherwise = N a (sustitucion ds z b) c
  4. Responder
    natmarmar2 
    sustitucion :: Posicion -> a -> Arbol a -> Arbol a
sustitucion (I:xs) z (N v i d) = N v (sustitucion xs z i) d
sustitucion (D:xs) z (N v i d) = N v i (sustitucion xs z d)
sustitucion []     z (N v i d) = N z i d

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.