Renombramiento de un árbol

José A. Alonso

03-07-2014

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
             deriving Show

Por ejemplo, el árbol

      "C"
      / \
     /   \
    /     \
  "B"     "A"
  / \     / \
"A" "B" "B" "C"

se puede definir por

ej1 :: Arbol String
ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

Definir la función

renombraArbol :: Arbol t -> Arbol Int

tal que (renombraArbol a) es el árbol obtenido sustituyendo el valor de los nodos y hojas por números tales que tengan el mismo valor si y sólo si coincide su contenido. Por ejemplo,

λ> renombraArbol ej1
N 2 (N 1 (H 0) (H 1)) (N 0 (H 1) (H 2))

Gráficamente,

      2
     / \
    /   \
   /     \
  1       0
 / \     / \
0   1   1   2

Soluciones

import Data.List

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
             deriving (Show, Eq)

ej1 :: Arbol String
ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

renombraArbol :: Ord t => Arbol t -> Arbol Int
renombraArbol a = aux a
    where ys            = valores a
          aux (H x)     = H (posicion x ys)
          aux (N x i d) = N (posicion x ys) (aux i) (aux d)

-- (valores a) es la lista de los valores en los nodos y las hojas del
-- árbol a. Por ejemplo,
--    valores ej1  ==  ["A","B","C"]
valores :: Ord a => Arbol a -> [a]
valores a = sort (nub (aux a))
    where aux (H x)     = [x]
          aux (N x i d) = x : (aux i ++ aux d)

-- (posicion x ys) es la posición de x en ys. Por ejemplo.
--    posicion 7 [5,3,7,8]  ==  2
posicion :: Eq a => a -> [a] -> Int
posicion x ys = head [n | (y,n) <- zip ys [0..], y == x]