Next Up Previous Hi Index

Chapter 20

Árboles

Al igual que las listas enlazadas, los árboles están hechos de nodos. Un tipo común de árbol es un árbol binario, en el que cada nodo contiene una referencia a otros dos nodos (posiblemente nulo). Nombramos a estas referencias como subárboles izquierdo y derecho. Como los nodos de las listas, los nodos de los árboles también contienen un cargo. Un diagrama de estado deun árbol es así:

Para evitar apelotonar las cosas en la figura, solemos omitir los Nones. La parte superior del árbol (el nodo al que apunta tree) se llama raíz. Siguiendo con la metáfora del árbol, los otros nodos se llaman ramas y los nodos de los extremos con referencias nulas se llaman hojas. Puede parecer extraño que dibujemos la figura con la raíz arriba y las hojas abajo, pero eso no es lo más raro. Para empeorar las cosas, los científicos informáticos añaden a la mezcla otra metáfofa: el árbol genealógico. El nodo superior se llama a veces padre y los nodos a los que se refiere son sus hijos. Los nodos con el mismo padre se llaman hermanos. Para terminar, tenemos un vocabulario geométrico para hablar sobre los árboles. Ya hemos mencionado izquierda y derecha, pero también están "arriba" (hacia el padre/raíz) y "abajo" (hacia los hijos/hojas). También, todos los nodos que están a la misma distancia de la raíz forman un nivel del árbol. Probablemente no sean necesarias las metáforas arbóreas para hablar de árboles, pero ahí están. Igual que las listas enlazadas, los árboles son estructuras de datos recursivas porque se definen recursivamente. \begin{quote Un árbol es: \begin{itemize} \item el árbol vacío, representado por {\tt None}, o \item un nodo que contiene una referencia a un objeto y dos referencias a árboles. \end{itemize} \end{quote} \index{árbol!vacío} \section {Crear árboles} El proceso de montar un árbol es similar al proceso de montar una lista enlazada. Cada invocación del constructor crea un solo nodo. \beforeverb \begin{verbatim} class Arbol: def __init__(self, cargo, izquierda=None, derecha=None): self.cargo = cargo self.izquierda = izquierda self.derecha = derecha def __str__(self): return str(self.cargo) \end{verbatim} \afterverb % El {\tt cargo} puede ser de cualquier tipo, pero los parámetros {\tt izquierda} y {\tt derecha} deben ser árboles. Tanto {\tt izquierda} como {\tt derecha} son opcionales; el valor por omisión es {\tt None}. Para imprimir un nodo, simplemente imprimimos el cargo. Una forma de construir un árbol es del fondo hacia arriba. Asigne primero los nodos hijos: \beforeverb \begin{verbatim} izquierda = Arbol(2) derecha = Arbol(3) \end{verbatim} \afterverb % Luego cree el nodo padre y vincúlelo a los hijos: \beforeverb \begin{verbatim} arbol = Arbol(1, izquierda, derecha); \end{verbatim} \afterverb % Podemos escribir este códico más concisamente anidando las invocaciones al constructor: \beforeverb \begin{verbatim} >>> arbol = Arbol(1, Arbol(2), Arbol(3)) \end{verbatim} \afterverb % En cualquier caso, el resultado es el árbol del principio del capítulo. \section {Recorrer árboles} \index{árbol!recorrido} \index{recorrer} \index{recursión} Siempre que usted vea una nueva estructura de datos, su primera pregunta debería ser: "¿Cómo la recorro?" La forma más natural de recorrer un árbol es recursivamente. Por ejemplo, si el árbol contiene enteros como cargo, esta función nos devuelve su suma: \beforeverb \begin{verbatim} def total(arbol): if arbol == None: return 0 return total(arbol.izquierda) + total(arbol.derecha) + arbol.cargo \end{verbatim} \afterverb % El caso base es el árbol vacío, que no tiene cargo, así que la suma es 0. El paso recursivo hace dos llamadas recursivas para hallar la suma de los árboles hijos. Cuando terminan las llamadas recursivas, sumamos el cargo del padre y devolvemos el total. \section {Árboles de expresión} \index{árbol!expresión} \index{árbol de expresión} \index{posfijo} \index{infio} \index{operador binario} \index{operador!binario} Un árbol es un forma natural de representar la estructura de una expresión. Al contrario que otras notaciones, puede representar el cálculo de forma no ambigua. Por ejemplo, la expresión infija {\tt 1 + 2 * 3} es ambigua a no ser que sepamos que la multiplicación se realiza antes que la suma. Éste árbol de expresión representa el mismo cálculo: \beforefig \centerline{\psfig{figure=illustrations/tree2.eps,height=2in}} \afterfig Los nodos de un árbol de expresión pueden ser operandos como {\tt 1} y {\tt 2} u operadores como {\tt +} y {\tt *}. Los operandos son nodos hojas; los nodos operadores contienen referencias a sus operandos. (Todos estos operadores son {\bf binarios}, lo que sifnifica que tienen exactamente dos operandos.) Así podemos construir este árbol: \beforeverb \begin{verbatim} >>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3))) \end{verbatim} \afterverb % Mirando la figura, no hay duda del orden de las operaciones; la multiplicación se realiza antes para calcular el segundo operando de la suma. Los árboles de expresión tienen muchos usos. El ejemplo de este capítulo usa árboles para traducir expresiones a posfijo, prefijo e infijo. Árboles similares se usan dentro de los compiladores para analizar, optimizar y traducir programas. \section {Recorrido de un árbol} \index{árbol!recorrido} \index{recorrido} \index{recursión} \index{orden prefijo} \index{orden posfijo} \index{orden infijo} Podemos recorrer un árbol de expresión e imprimir el contenido así: \beforeverb \begin{verbatim} def imprimeArbol(arbol): if arbol == None: return print arbol.cargo, imprimeArbol(arbol.izquierda) imprimeArbol(arbol.derecha) \end{verbatim} \afterverb % \index{orden prefijo} \index{prefijo} En otras palabras, para imprimir un árbol imprima primero el contenido de la raíz, luego el subárbol izquierdo entero y después el subárbol derecho entero. Esta forma de recorrer un árbol se llama {\bf orden prefijo}, porque el contenido de la raíz aparece {\em antes} del contenido de los hijos. La salida del ejemplo anterior es: \beforeverb \begin{verbatim} >>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3))) >>> imprimeArbol(arbol) + 1 * 2 3 \end{verbatim} \afterverb % Este formato es diferente tanto del posfijo como del infijo; es otra notación llamada {\bf prefija}, en la que los operadores aparecen delante de sus operandos. Puede sospechar que si recorre el árbol en un orden diferente obtendrá la expresión en una notación diferente. Por ejemplo, si imprime primero los subárboles y luego la raíz, tendrá: \beforeverb \begin{verbatim} def imprimeArbolPosfijo(arbol): if arbol == None: return imprimeArbolPosfijo(arbol.izquierda) imprimeArbolPosfijo(arbol.derecha) print arbol.cargo, \end{verbatim} \afterverb % \index{orden postfijo} \index{orden infijo} ¡El resultado, {\tt 1 2 3 * +}, está en notación posfija! Este orden de recorrido se llama {\bf orden posfijo}. Finalmente, para recorrer un árbol en {\bf orden infijo}, usted imprime el árbol izquierdo, luego la raíz y después el árbol derecho: \beforeverb \begin{verbatim} def imprimeArbolInfijo(arbol): if arbol == None: return imprimeArbolInfijo(arbol.izquierda) print arbol.cargo, imprimeArbolInfijo(arbol.derecha) \end{verbatim} \afterverb % El resultado es {\tt 1 + 2 * 3}, que es la expresión en notación infija. Para ser justos debemos señalar que hemos omitido una importante complicación. A veces, al escribir una expresión infija, debemos usar paréntesis para preservar el orden de las operacioens. De modo que una exploración de orden infijo no es suficiente para generar una expresión infija. No obstante, con unas pequeñas mejoras, el árbol de expresión y los tres recorridos nos dan una forma general de traducr expresiones de un formato a otro. \begin{quote} {\em Como ejercicio, modifique {\tt imprimeArbolInfijo} de modo que ponga entre paréntesis cada operador con sus operandos. ¿La salida es correcta y sin ambigüedades? ¿Se necesitan siempre los paréntesis?} \end{quote} Si hacemos un recorrido en orden infijo y tomamos nota de en qué nivel del árbol estamos, podemos generar una representación gráfica de un árbol: \beforeverb \begin{verbatim} def imprimeArbolSangrado(arbol, nivel=0): if arbol == None: return imprimeArbolSangrado(arbol.derecha, nivel+1) print ' '*nivel + str(arbol.cargo) imprimeArbolSangrado(arbol.izquierda, nivel+1) \end{verbatim} \afterverb % El parámetro {\tt nivel} lleva la cuenta de dónde estamos en el árbol. Por omisión, incialmente es 0. Cada vez que hacemos una llamada recursiva, pasamos {\tt nivel+1} porque el nivel del hijo es siempre uno mayor que el del padre. Sangramos cada elemento con dos espacios por nivel. El resultado del árbol de ejemplo es: \beforeverb \begin{verbatim} >>> imprimeArbolSangrado(arbol) 3 * 2 + 1 \end{verbatim} \afterverb % Si mira la salida de lado, verá una versión simplificada de la figura original. \section{Construir un árbol de expresión} \index{árbol de expresión} \index{árbol!expresión} \index{analizar} \index{token} En esta sección analizamos expresiones infijas y formamos los correspondientes árboles de expresión. Por ejemplo, la expresión {\tt (3+7)*9} nos da el siguiente árbol: \beforefig \centerline{\psfig{figure=illustrations/tree3.eps}} \afterfig Fíjese en que hemos simplificando el diagrama omitiendo los nombres de los atributos. El analizador que vamos a escribir maneja expresiones que incluyen números, paréntesis y los operadores {\tt +} y {\tt *}. Suponemos que la cadena de entrada ya ha sido tokenizada (N. del T.: podríamos traducir "token" como "cospel" o "pieza", pero la expresión inglesa está tan introducida en el vocabulario informático que sólo añadiría confusión.) y almacenada en una lista de Python. La lista de tokens de {\tt (3+7)*9} es: \beforeverb \begin{verbatim} ['(', 3, '+', 7, ')', '*', 9, 'fin'] \end{verbatim} \afterverb % El token {\tt fin} es útil para evitar que el analizador lea más allá del final de la lista. \begin{quote} {\em A modo de ejercicio, escriba una función que tome una cadena conteniendo una expresión y devuelva una lista de tokens.} \end{quote} La primera función que vamos a escribir es {\tt tomaToken}, que toma como parámetros una lista de tokens y el token que esperamos. Compara el token esperado con el primer token de la lista: si coinciden, elimina el token de la lista y devuelve verdadero, en caso contrario, devuelve falso: \beforeverb \begin{verbatim} def tomaToken(listaToken, esperado): if listaToken[0] == esperado: del listaToken[0] return 1 else: return 0 \end{verbatim} \afterverb % Como {\tt listaToken} apunta a un objeto mutable, los cambios hechos aquí son visibles para cualquier otra variable que apunte al mismo objeto. La siguiente función, {\tt obtieneNumero}, maneja operandos. Is el siguiente token de {\tt listaToken} es un número, {\tt obtieneNumero} lo elimina y devuelve un nodo hoja que contiene el número; en caso contrario, devuelve {\tt None}. \beforeverb \begin{verbatim} def obtieneNumero(listaToken): x = listaToken[0] if type(x) != type(0): return None del listaToken[0] return Arbol (x, None, None) \end{verbatim} \afterverb % Antes de seguir, debemos probar {\tt obtieneNumero} aisladamente. Asignamos una lista de números a {\tt listaToken}, extraemos el primero, imprimimos el resultado e imprimimos lo que quede de la lista de tokens: \beforeverb \begin{verbatim} >>> listaToken = [9, 11, 'fin'] >>> x = obtieneNumero(listaToken) >>> imprimeArbolPosfijo(x) 9 >>> print listaToken [11, 'fin'] \end{verbatim} \afterverb % El siguiente método que necesitamos es {\tt obtieneProducto}, que construye un árbol de expresión para productos. Un producto simple tiene dos números como operandos, como {\tt 3 * 7}. Aquí tenemos una versión de {\tt obtieneProducto} que maneja productos simples. \beforeverb \begin{verbatim} def obtieneProducto(listaToken): a = obtieneNumero(listaToken) if tomaToken(listaToken, '*'): b = obtieneNumero(listaToken) return Arbol ('*', a, b) else: return a \end{verbatim} \afterverb % Suponiendo que {\tt obtieneNumero} se ejecuta con éxito y devuelve un árbol simple, asignamos el primer operando a {\tt a}. Si el siguiente carácter es {\tt *}, obtenemos el segundo número y construimos un árbol de expresión con {\tt a}, {\tt b}, y el operador. Si el siguiente carácter es cualquier otra cosa, simplemente devolvemos el nodo hoja con {\tt a}. Veamos dos ejemplos: \beforeverb \begin{verbatim} >>> listaToken = [9, '*', 11, 'fin'] >>> arbol = obtieneProducto(listaToken) >>> imprimeArbolPosfijo(arbol) 9 11 * \end{verbatim} \afterverb \beforeverb \begin{verbatim} >>> listaToken = [9, '+', 11, 'fin'] >>> arbol = obtieneProducto(listaToken) >>> imprimeArbolPosfijo(arbol) 9 \end{verbatim} \afterverb % El segundo ejemplo implica que entendemos un operando suelto como un tipo de producto. Esta definición de "producto" es contraria a la intuición, pero resulta ser útil. Ahora tenemos que vérnoslas con productos compuestos, como {\tt 3 * 5 * 13}. Tratamos esta expresión como un producto de productos, es decir, {\tt 3 * (5 * 13)}. El árbol resultante es: \beforefig \centerline{\psfig{figure=illustrations/tree4.eps}} \afterfig Con un pequeño cambio en {\tt obtieneProducto} podemos manejar productos arbitrariamente largos: \beforeverb \begin{verbatim} def obtieneProducto(listaToken): a = obtieneNumero(listaToken) if tomaToken(listaToken, '*'): b = obtieneProducto(listaToken) # cambiamos esta línea return Arbol ('*', a, b) else: return a \end{verbatim} \afterverb % En otras palabras, un producto puede ser bien un operando aislado o un árbol con {\tt *} en su raíz, un número en la derecha y un producto en la izquierda. Este tipo de definición recursiva debería empezar a resultar familiar. \index{producto} \index{definición!recursiva} \index{definición recursiva} Comprobemos la nuevar versión con un producto compuesto: \beforeverb \begin{verbatim} >>> listaToken = [2, '*', 3, '*', 5 , '*', 7, 'fin'] >>> arbol = obtieneProducto(listaToken) >>> imprimeArbolPosfijo(arbol) 2 3 5 7 * * * \end{verbatim} \afterverb % Ahora añadiremos la capacidad de analizar sumas. De nuevo, usamos una definición poco intuitiva de "suma". Para nosotros, una suma puede ser un árbol con {\tt +} en la raíz, un producto en la izquierda y una suma en la derecha. O también, una suma puede ser simplemente un producto. \index{suma} Si quiere seguir adelante con esta definición, tiene una bonita propiedad: podemos representar cualquier expresión (sin paréntesis) como una suma de productos. Esta propiedad es la base de nuestro algoritmo de análisis. {\tt obtieneSuma} intenta construir un árbol con un producto en la izquierda y una suma en la derecha. Pero si no encuentra un {\tt +}, simplemente construye un producto. \beforeverb \begin{verbatim} def obtieneSuma(listaToken): a = obtieneProducto(listaToken) if tomaToken(listaToken, '+'): b = obtieneSuma(listaToken) return Arbol ('+', a, b) else: return a \end{verbatim} \afterverb % Vamos a probarla con {\tt 9 * 11 + 5 * 7}: \beforeverb \begin{verbatim} >>> listaToken = [9, '*', 11, '+', 5, '*', 7, 'fin'] >>> arbol = obtieneSuma(listaToken) >>> imprimeArbolPosfijo(arbol) 9 11 * 5 7 * + \end{verbatim} \afterverb % Ya casi hemos acabado, pero todavía tenemos que manejar los paréntesis. En culaquier lugar de una expresión donde puede haber un número, puede haber también una suma entera entre paréntesis. Sólo necesitamos modificar {\tt obtieneNumero} para manejar {\bf subexpresiones}: \index{subexpresión} \beforeverb \begin{verbatim} def obtieneNumero(listaToken): if tomaToken(listaToken, '('): x = obtieneSuma(listaToken) # obtiene la subexpresión tomaToken(listaToken, ')') # elimina el cierre de paréntesis return x else: x = listaToken[0] if type(x) != type(0): return None listaToken[0:1] = [] return Arbol (x, None, None) \end{verbatim} \afterverb % Vamos a probar este código con {\tt 9 * (11 + 5) * 7}: \beforeverb \begin{verbatim} >>> listaToken = [9, '*', '(', 11, '+', 5, ')', '*', 7, 'fin'] >>> arbol = obtieneSuma(listaToken) >>> imprimeArbolPosfijo(arbol) 9 11 5 + 7 * * \end{verbatim} \afterverb % \adjustpage{-2} \pagebreak El analizador manejó correctamente los paréntesis; la suma ocurre antes de la multiplicación. En la versión final del programa, sería bueno dar a {\tt obtieneNumero} un nombtre más descriptivo de su nueva función. \section{Manejar errores} \index{manejar errores} \index{manejo de errores} En todo momento hemos supuesto que las expresiones estaban bien formadas. Por ejemplo, cuando alcanzamos el final de una subexpresión, suponemos que el carácter siguiente es un paréntesis cerrado. Si hay un error y el siguiente carácter es cualquier otra cosa, deberíamos ocuparnos de él. \beforeverb \begin{verbatim} def obtieneNumero(listaToken): if tomaToken(listaToken, '('): x = obtieneSuma(listaToken) if not tomaToken(listaToken, ')'): raise 'ExpresionErronea', 'falta un paréntesis' return x else: # omitido el resto de la función \end{verbatim} \afterverb % La sentencia {\tt raise} crea una excepción; en este caso creamos un nuevo tipo de excepción, llamado {\tt ExpresionErronea}. Si la función que llamó a {\tt obtieneNumero}, o alguna de las otras funciones de la pila de llamadas, maneja la expresión, el programa podrá continuar. En caso contrario, Python imprimirá un mensaje de error y saldrá. \begin{quote} {\em Como ejercicio, encuetnre otros lugares de estas funciones donde puedan ocurrir errores y añada las sentencias {\tt raise} adecuadas. Pruebe su código con expresiones formadas incorrectamente.} \end{quote} \section{El árbol de animales} \index{juego de los animales} \index{juego!animales} \index{base de conocimiento} En esta sección desarrollaremos un pequeño programa que usa un árbol para representar una base de conocimientos. El programa interactúa con el usuario para crear un árbol de preguntas y nombres de animales. Aquí tenemos un ejemplo de ejecución: \adjustpage{-3} \pagebreak \beforeverb \begin{verbatim} ¿Estás pensando en un animal? s ¿Es un pájaro? n ¿Cómo se llama el animal? perro ¿Qué pregunta distinguiría a un perro de un pájaro? Puede volar Si el animal fuera un perro, ¿cuál sería la respuesta? n ¿Estás pensando en un animal? s ¿Puede volar? n ¿Es un perro? n ¿Cómo se llama el animal? gato ¿Qué pregunta distinguiría a un gato de un perro? Ladra Si el animal fuera un gato, ¿cuál sería la respuesta? n ¿Estás pensando en un animal? s ¿Puede volar? n ¿Ladra? s ¿Es un perro? s ¡Soy el más grande! ¿Estás pensando en un animal? n \end{verbatim} \afterverb % Este es el árbol que construye este diálogo: \beforefig \centerline{\psfig{figure=illustrations/tree5.eps}} \afterfig Al principio de cada ronda, el programa empieza en lo alto del árbol y hace la primera pregunta. Dependiendo de la respuesta, se mueve al hijo de la izquierda o de la derecha y sigue hasta que llega a un nodo hoja. En ese momento, intenta adivinar. Si falla, pide al usuario el nombre del nuevo animal y una pregunta que distinga al intento fallido del nuevo animal. Entonces añade un nodo al árbol con la nueva pregunta y el nuevo animal. Éste es el código: \adjustpage{-2} \pagebreak \beforeverb \begin{verbatim} def animal(): # empezar con un nodo suelto raiz = Arbol("pájaro") # bucle hasta que el usuario salga while 1: print if not si("¿Estás pensando en un animal? "): break # recorrer el árbol arbol = raiz while arbol.tomaIzquierda() != None: indicador = "¿" + arbol.tomaCargo() + "? " if si(indicador): arbol = arbol.tomaDerecha() else: arbol = tarbol.tomaIzquierda() # intentar adivinar adivina = arbol.tomaCargo() indicador = "¿Es un " + adivina + "? " if si(indicador): print "¡Soy el más grande!" continue # obtener información nueva indicador = "¿Cómo se llama el animal? " animal = raw_input(indicador) indicador = "¿Qué pregunta distinguiría a un %s de un %s? " pregunta = raw_input(indicador % (animal,adivina)) # añadir información nueva al árbol arbol.ponCargo(pregunta) indicador = "Si el animal fuera un %s, ¿cuál sería la respuesta? " if si(indicador % animal): arbol.ponIzquierda(Arbol(adivina)) arbol.ponDerecha(Arbol(animal)) else: arbol.ponIzquierda(Arbol(animal)) arbol.ponDerecha(Arbol(adivina)) \end{verbatim} \afterverb % La función {\tt si} es un auxiliar; imprime un indicador y acepta una entrada del usuario. Si la respuesta comienza con {\em s} o {\em S}, la función devuelve verdadero: \beforeverb \begin{verbatim} def si(preg): from string import lower resp = lower(raw_input(preg)) return (resp[0] == 's') \end{verbatim} \afterverb % La condición del bucle externo es {\tt 1}, lo que significa que siguirá hasta que se ejecute la sentencia {\tt break} cuando el usuario ya no piense en ningún animal. El bucle {\tt while} interno recorre el árbol de arriba a abajo, guiado por las respuestas del usuario. Cuando se añade un nuevo nodo al árbol, la pregunta sustituye al cargo y los dos hijos son el animal nuevo y el cargo original. Una carencia del programa es que, al salir, ¡olvida todo lo que le había usted enseñado con tanto cuidado! \begin{quote} {\em Como ejercicio, piense en varias formas de en las que podría guardar el árbol de conocimiento en un archivo. Implemente la que piense que es más fácil.} \end{quote} \section{Glosario} \index{árbol binario} \index{nodo} \index{nodo raíz} \index{nodo hoja} \index{nodo padre} \index{nodo hijo} \index{nodo hermano} \index{nivel} \index{prefijo} \index{orden prefijo} \index{orden posfijo} \index{orden infijo} \index{operador binario} \index{operador!binario} \begin{description} \item[árbol binario:] Un árbol en el que cada nodo apunta a cero, uno o dos nodos dependientes. \item[raíz:] El nodo superior de un árbol, sin padre. \item[hoja:] Un nodo del extremo inferior de un árbol, sin hijos. \item[padre:] El nodo que apunta a un nodo dado. \item[hijo:] Uno de los nodos a los que apunta un nodo. \item[hermanos:] Nodos que tienen un padre común. \item[nivel:] El conjunto de nodos equidistante de la raíz. \item[operador binario:] Un operador que toma dos operandos. \item[subexpresión:] Una expresión entre paréntesis que actúa como un operando simple dentro de otra expresión mayor. \item[orden prefijo:] Una forma de recorrer un árbol, visitando cada nodo antes que a sus hijos. \item[notación prefija:] Una forma de escribir una expresión matemática en la que los operadores aparecen antes que sus operandos. \item[orden posfijo:] Una forma de recorrer un árbol, visitando los hijos de cada nodo antes del propio nodo. \item[orden infijo:] Una forma de recorrer un árbol, visitando el subárbol izquierdo, luego la raíz, y luego el subárbol derecho. \end{description}


Next Up Previous Hi Index