Funciones de árboles en Ocaml

Continuando con mi entrada sobre tipos y árboles en Ocaml, hoy revisaré algunas funciones sencillas sobre cómo trabajar con árboles.
Me centraré en los binarios, pero toda la información es fácilmente extrapolable a otros tipos de árboles si los has entendido en el post anterior.
Voy a definir un tipo para representar arboles binarios y luego un arbol que represente la siguiente figura:

El tipo, como ya sabemos, es:
# type 'a bintree =
        Empty
      | Node of 'a * 'a bintree * 'a bintree;;

Y el arbol binario viene dado por:
# let t = Node (5, Node(2,Empty,Empty), Node(7, Node(6,Empty,Empty), Node(8,Empty,Empty)) );;

Operaciones que devuelven una parte del arbol
Estas operaciones son las más sencillas de programar. Como devuelven una parte de un arbol dado, basta con retornar el valor correspondiente en la tupla que conforma el arbol, a no ser que se trate de un árbol vacío (en este caso sería conveniente levantar una excepción). Veamos un ejemplo con la raiz:
# let raiz = function
        Empty -> raise (Invalid_argument "raiz")
      | Node (r, _, _) -> r;;

Como vemos, al arbol vacío (Empty) se le asigna la excepción de argumento inválido en la función “raiz”, pero en el caso de Nodos con raiz y otras dos componentes, se devuelve la raiz. No es preciso identificar las componentes hijo izquierdo e hijo derecho, ya que no las necesitamos para dar el resultado.
Las otras dos operaciones que podría haber (ramaizda y ramadcha) no son más que extensiones de esta idea. Eso sí, habrá una diferencia de tipos y es fácil entender porqué, ya que cuando devolvemos la raiz estamos devolviendo un dato de tipo alpha (‘a) y cuando devolvemos una de las ramas hijas estaremos devolviendo un subárbol (es decir, un ‘a bintree).
La raiz de nuestro arbol t es 5.
La rama izquierda de t es: Node(2,Empty,Empty)
La rama derecha de t es: Node(7, Node(6,Empty,Empty), Node(8,Empty,Empty))

Operaciones que contabilizan los elementos del arbol
Hay dos operaciones de este tipo que resultan enormemente útiles: el número de nodos de un árbol y su altura. Vamos con el primero.
El número de nodos de un árbol vacio es obviamente cero, así que podemos empezar la definición como:
# let numnodos = function
        Empty -> 0
        ...

En el caso de que tenga elementos, debemos contar 1 por la raiz y sumarle el numero de elementos de los subárboles que tiene como hijos. Es decir, esta funcion debe ser recursiva, así que…
let rec numnodos = function
        Empty -> 0
      | Node (_,i,d) -> 1 + numnodos i + numnodos d;;

Es decir, el total de nodos de un arbol es: los nodos de su subarbol hijo por la izquierda más los nodos de su subárbol hijo por la derecha más uno, correspondiente a la raiz.

La altura de un árbol se calcula de forma muy semejante. En el caso del vacío, la altura es cero de nuevo; y en el caso del árbol con elementos, su altura es 1 más el máximo de comparar la altura de sus dos hijos (uno puede ser más alto que el otro). Sencillamente:
let rec altura = function
        Empty -> 0
      | Node (_,i,d) -> 1 + max (altura i) (altura d);;

Operaciones que presentan el arbol en un orden concreto
Aquí encontramos el recorrido en anchura, la imagen especular, el preorden, el posorden y el inorden. Uno de los más sencillos es el inorden. Lista el árbol empezando por los hijos de la izquierda, luego las raices y luego los hijos por la derecha PARA CADA NODO. Así que es fácil entender que el recorrido inorden de nuestro árbol de ejemplo debería devolver la siguiente lista: [2;5;6;7;8].
Para conseguirlo, desecharemos el caso del árbol vacío asignándole una lista vacía, el árbol que solo tiene raiz con una lista en la que solo figura la raiz, y el árbol con elementos será la concatenacion de: el inorden del hijo izquierdo, la lista con el elemento raiz y el inorden del hijo derecho (función obviamente recursiva, por lo tanto)…
let rec inorden = function
        Empty -> []
      | Node (r,Empty,Empty) -> [r]
      | Node (r,i,d) -> inorden i @ [r] @ inorden d;;

Ahora, desarrollar el posorden y el preorden debe ser coser y cantar… casi como el recorrido en anchura 🙂
Otras operaciones similares podrían ser las que muestran las hojas de un árbol, las que nos dan su elemento máximo o mínimo… Pero esa, a fin de cuentas, es otra historia…

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s