|
|
|
|
|
|
|
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 nula). Nombramos a estas referencias como subárboles izquierdo y derecho. Como los nodos de las listas, los nodos de los árboles también contienen una carga. Un diagrama de estado de un á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.
Un árbol es:
- el árbol vacío, representado por None, o
- un nodo que contiene una referencia a un objeto y dos referencias a á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.
class Arbol:
def __init__(self, carga, izquierda=None, derecha=None):
self.carga = carga
self.izquierda = izquierda
self.derecha = derecha
def __str__(self):
return str(self.carga)
La carga puede ser de cualquier tipo, pero los parámetros izquierday derecha deben ser árboles. Tanto izquierda como derecha son opcionales; el valor por omisión es None.
Para imprimir un nodo, simplemente imprimimos la carga.
Una forma de construir un árbol es del fondo hacia arriba. Asigne primero los nodos hijos:
izquierda = Arbol(2)
derecha = Arbol(3)
Luego cree el nodo padre y vincúlelo a los hijos:
arbol = Arbol(1, izquierda, derecha);
Podemos escribir este código más concisamente anidando las invocaciones al constructor:
>>> arbol = Arbol(1, Arbol(2), Arbol(3))
En cualquier caso, el resultado es el árbol del principio del capítulo.
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 carga, esta función nos devuelve su suma:
def total(arbol):
if arbol == None: return 0
return total(arbol.izquierda) + total(arbol.derecha) +\
arbol.carga
El caso base es el árbol vacío, que no tiene carga, 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 la carga del padre y devolvemos el total.
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 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:
Los nodos de un árbol de expresión pueden ser operandos como 1 y 2u operadores como + y *. Los operandos son nodos hojas; los nodos operadores contienen referencias a sus operandos. (Todos estos operadores son binarios, lo que significa que tienen exactamente dos operandos.)
Así podemos construir este árbol:
>>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3)))
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 postfijo, prefijo e infijo. Árboles similares se usan dentro de los compiladores para analizar, optimizar y traducir programas.
Podemos recorrer un árbol de expresión e imprimir el contenido así:
def imprimeArbol(arbol):
if arbol == None: return
print arbol.carga,
imprimeArbol(arbol.izquierda)
imprimeArbol(arbol.derecha)
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 orden prefijo, porque el contenido de la raíz aparece antes del contenido de los hijos. La salida del ejemplo anterior es:
>>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3)))
>>> imprimeArbol(arbol)
+ 1 * 2 3
Este formato es diferente tanto del postfijo como del infijo; es otra notación llamada 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á:
def imprimeArbolPostfijo(arbol):
if arbol == None: return
imprimeArbolPostfijo(arbol.izquierda)
imprimeArbolPostfijo(arbol.derecha)
print arbol.carga,
¡El resultado, 1 2 3 * +, está en notación posfija! Este orden de recorrido se llama orden postfijo.
Finalmente, para recorrer un árbol en orden infijo, usted imprime el árbol izquierdo, luego la raíz y después el árbol derecho:
def imprimeArbolInfijo(arbol):
if arbol == None: return
imprimeArbolInfijo(arbol.izquierda)
print arbol.carga,
imprimeArbolInfijo(arbol.derecha)
El resultado es 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.
Como ejercicio, modifique 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?
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:
def imprimeArbolSangrado(arbol, nivel=0):
if arbol == None: return
imprimeArbolSangrado(arbol.derecha, nivel+1)
print ' '*nivel + str(arbol.carga)
imprimeArbolSangrado(arbol.izquierda, nivel+1)
El parámetro 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 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:
>>> imprimeArbolSangrado(arbol)
3
*
2
+
1
Si mira la salida de lado, verá una versión simplificada de la figura original.
En esta sección analizamos expresiones infijas y formamos los correspondientes árboles de expresión. Por ejemplo, la expresión (3+7)*9 nos da el siguiente árbol:
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 + y *. Suponemos que la cadena de entrada ya ha sido tokenizada y almacenada en una lista de Python. La lista de tokens de (3+7)*9 es:
['(', 3, '+', 7, ')', '*', 9, 'fin']
El token fin es útil para evitar que el analizador lea más allá del final de la lista.
A modo de ejercicio, escriba una función que tome una cadena conteniendo una expresión y devuelva una lista de tokens.
La primera función que vamos a escribir es 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:
def tomaToken(listaToken, esperado):
if listaToken[0] == esperado:
del listaToken[0]
return 1
else:
return 0
Como 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, obtieneNumero, maneja operandos. Si el siguiente token de listaToken es un número, obtieneNumero lo elimina y devuelve un nodo hoja que contiene el número; en caso contrario, devuelve None.
def obtieneNumero(listaToken):
x = listaToken[0]
if type(x) != type(0): return None
del listaToken[0]
return Arbol (x, None, None)
Antes de seguir, debemos probar obtieneNumero aisladamente. Asignamos una lista de números a listaToken, extraemos el primero, imprimimos el resultado e imprimimos lo que quede de la lista de tokens:
>>> listaToken = [9, 11, 'fin']
>>> x = obtieneNumero(listaToken)
>>> imprimeArbolPostfijo(x)
9
>>> print listaToken
[11, 'fin']
El siguiente método que necesitamos es obtieneProducto, que construye un árbol de expresión para productos. Un producto simple tiene dos números como operandos, como 3 * 7.
Aquí tenemos una versión de obtieneProducto que maneja productos simples.
def obtieneProducto(listaToken):
a = obtieneNumero(listaToken)
if tomaToken(listaToken, '*'):
b = obtieneNumero(listaToken)
return Arbol ('*', a, b)
else:
return a
Suponiendo que obtieneNumero se ejecuta con éxito y devuelve un árbol simple, asignamos el primer operando a a. Si el siguiente carácter es *, obtenemos el segundo número y construimos un árbol de expresión con a, b, y el operador.
Si el siguiente carácter es cualquier otra cosa, simplemente devolvemos el nodo hoja con a. Veamos dos ejemplos:
>>> listaToken = [9, '*', 11, 'fin']
>>> arbol = obtieneProducto(listaToken)
>>> imprimeArbolPostfijo(arbol)
9 11 *
>>> listaToken = [9, '+', 11, 'fin']
>>> arbol = obtieneProducto(listaToken)
>>> imprimeArbolPostfijo(arbol)
9
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 3 * 5 * 13.
Tratamos esta expresión como un producto de productos, es decir, 3 * (5 *
13). El árbol resultante es:
Con un pequeño cambio en obtieneProducto podemos manejar productos arbitrariamente largos:
def obtieneProducto(listaToken):
a = obtieneNumero(listaToken)
if tomaToken(listaToken, '*'):
b = obtieneProducto(listaToken) # cambiamos esta línea
return Arbol ('*', a, b)
else:
return a
En otras palabras, un producto puede ser bien un operando aislado o un árbol con * 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.
Comprobemos la nueva versión con un producto compuesto:
>>> listaToken = [2, '*', 3, '*', 5 , '*', 7, 'fin']
>>> arbol = obtieneProducto(listaToken)
>>> imprimeArbolPostfijo(arbol)
2 3 5 7 * * *
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 + 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.
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.
obtieneSuma intenta construir un árbol con un producto en la izquierda y una suma en la derecha. Pero si no encuentra un +, simplemente construye un producto.
def obtieneSuma(listaToken):
a = obtieneProducto(listaToken)
if tomaToken(listaToken, '+'):
b = obtieneSuma(listaToken)
return Arbol ('+', a, b)
else:
return a
Vamos a probarla con 9 * 11 + 5 * 7:
>>> listaToken = [9, '*', 11, '+', 5, '*', 7, 'fin']
>>> arbol = obtieneSuma(listaToken)
>>> imprimeArbolPostfijo(arbol)
9 11 * 5 7 * +
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 obtieneNumero para manejar subexpresiones:
def obtieneNumero(listaToken):
if tomaToken(listaToken, '('):
x = obtieneSuma(listaToken) # obtiene la subexpresión
tomaToken(listaToken, ')') # quita 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)
Vamos a probar este código con 9 * (11 + 5) * 7:
>>> listaToken = [9, '*', '(', 11, '+', 5, ')', '*', 7, 'fin']
>>> arbol = obtieneSuma(listaToken)
>>> imprimeArbolPostfijo(arbol)
9 11 5 + 7 * *
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 obtieneNumero un nombre más descriptivo de su nueva función.
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.
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
La sentencia raise crea una excepción; en este caso creamos un nuevo tipo de excepción, llamado ExpresionErronea. Si la función que llamó a 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á.
Como ejercicio, encuentre otros lugares de estas funciones donde puedan ocurrir errores y añada las sentencias raise adecuadas. Pruebe su código con expresiones formadas incorrectamente.
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:
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
Este es el árbol que construye este diálogo:
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:
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.tomaCarga() + "? "
if si(indicador):
arbol = arbol.tomaDerecha()
else:
arbol = arbol.tomaIzquierda()
# intentar adivinar
adivina = arbol.tomaCarga()
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.ponCarga(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))
La función si es un auxiliar; imprime un indicador y acepta una entrada del usuario. Si la respuesta comienza con s o S, la función devuelve verdadero:
def si(preg):
from string import lower
resp = lower(raw_input(preg))
return (resp[0] == 's')
La condición del bucle externo es 1, lo que significa que seguirá hasta que se ejecute la sentencia break cuando el usuario ya no piense en ningún animal.
El bucle 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 a la carga y los dos hijos son el animal nuevo y la carga original.
Una carencia del programa es que, al salir, ¡olvida todo lo que usted le había enseñado con tanto cuidado!
Como ejercicio, piense en varias formas en las que podría guardar el árbol de conocimiento en un archivo. Implemente la que piense que es más fácil.
|
|
|
|
|
|
|