|
|
|
|
|
|
|
Al igual que las listas enlazadas, los árboles están hechos de nodos. Un tipo común de árbol es el árbol binario, en el cual cada nodo contiene una referencia a otros dos nodos (posiblemente nulos). Estas referencias se denominan subárboles izquierdos y derechos. Al igual que las listas de nodos, los árboles de nodos también llevan datos. El diagrama de un árbol se representa de esta manera:
Para evitar la confusión en el dibujo, a menudo se omiten los None.
La zona superior del árbol (el nodo al que el árbol se refiere) se denomina raíz. Para seguir con la metáfora del árbol, los demás nodos se llaman ramas y los nodos de los extremos con referencias nulas se llaman hojas. Puede parecer extraño que se dibuje un árbol con la raíz en la parte superior y las hojas en la parte inferior, aunque esto no es lo más curioso.
Para empeorar las cosas, los ingenieros informáticos introducen otra metáfora: el árbol familiar. La parte superior del nodo se suele llamar padre y los nodos que salen de él son los hijos. Los nodos con el mismo padre se llaman hermanos.
Finalmente, hay un vocabulario geométrico para hablar sobre árboles. Ya se han mencionado los izquierdos y los derechos, pero también hay "superiores" (cerca del padre o raíz) e "inferiores" (cerca de los hijos u hojas). Además, todos los nodos que están a la misma distancia de la raíz comprenden un nivel del árbol.
Probablemente no se necesitan tres metáforas para hablar de árboles, pero ahí están.
Al igual que las listas enlazadas, los árboles son estructuras de datos recurrentes por su naturaleza repetitiva.
Un árbol es
- un árbol vacío, representado por None, o
- un nodo que contiene una referencia de objeto y dos referencias de árbol.
El proceso de diseñar un árbol es similar al proceso de diseñar una lista enlazada. Cada invocación del constructor diseña un solo nodo .
class Arbol:
def __init__(self, datos, izquierda=None, derecha=None):
self.datos = datos
self.izquierda = izquierda
self.derecha = derecha
def __str__(self):
return str(self.datos)
Los datos pueden ser de cualquier tipo, pero los parámetros izquierdo y derecho deben ser nodos de árboles. izquierdo y derecho son opcionales; el valor predeterminado es None.
Para mostrar un nodo, simplemente se muestran los datos.
Una forma de diseñar un árbol es desde la parte superior. Primero hay que localizar los nodos hijos:
izquierda = Arbol(2)
derecha = Arbol(3)
Luego crear el nodo padre y unirlo al del hijo:
arbol = Arbol(1, izquierda, derecha);
Se puede escribir este código de manera más concisa uniendo las invocaciones del constructor.
>>> arbol = Arbol(1, Arbol(2), Arbol(3))
De todas maneras, el resultado es el árbol que hay al principio del capítulo.
Comentarios
Cada vez que veas una nueva estructura de datos, tu primera pregunta debería ser "¿Cómo lo recorro?" La forma más normal de recorrer un árbol es de forma recurrente. Por ejemplo, si el árbol contiene enteros como datos, esta función devuelve su suma:
def total(arbol):
if arbol == None: return 0
return total(arbol.izquierdo) + total(arbol.derecho) + arbol.datos
El caso base es un árbol vacío, que no contiene datos, así que la suma es 0. El paso recurrente hace dos llamadas recursivas para encontrar la suma total de los árboles hijos. Cuando las llamadas recurrentes concluyen, añadimos los datos del padre y devolvemos al total.
Comentarios
Un árbol es la forma natural de representar la estructura de una expresión. A diferencia de otras anotaciones, puede representar el cómputo sin ambigüedad. Por ejemplo, la expresión infija 1 + 2 * 3 es ambigua a menos que sepamos que la multiplicación se hace antes que la suma.
Este árbol de expresión representa el mismo cómputo:
Los nodos de un árbol de expresión pueden ser operandos como 1 y 2 u 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).
Podemos diseñar el árbol de esta manera:
>>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3)))
Al mirar la imagen, no hay duda de cuál es el orden de las operaciones; la multiplicación se hace primero para calcular el segundo operando de la suma.
Los árboles de expresión tienen muchos usos. El ejemplo de este capítulo usa los árboles para trasladar las expresiones a sufijos, prefijos e infijos. Los árboles similares se usan dentro de compiladores para analizar, optimizar y traducir programas.
Comentarios
Podemos recorrer un árbol de expresión y mostrar los resultados de la siguiente manera:
def mostrarArbol(arbol):
if arbol == None: return
print arbol.datos,
mostrarArbol(arbol.izquierdo)
mostrarArbol(arbol.derecho)
En otras palabras, para mostrar un árbol primero hay que mostrar el contenido de la raíz, después el subárbol izquierdo entero y seguidamente el subárbol derecho entero. Esta forma de recorrer un árbol se denomina preorden, porque el contenido de la raíz aparece antes que el contenido de los nodos hijos. Para el ejemplo anterior, el resultado es el siguiente:
>>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3)))
>>> mostrarArbol(arbol)
+ 1 * 2 3
Este formato es diferente al posfijo y al infijo, ésta es otra notación llamada prefijo, en la que los operadores aparecen antes que los operandos.
Puede que pienses que si recorres un árbol en un orden diferente, obtendrás la expresión con una notación diferente. Por ejemplo, si muestras los subárboles primero y la raíz después, obtendrás lo siguiente:
def mostrarArbolPostorden(arbol):
if arbol == None: return
mostrarArbolPostorden(arbol.izquierdo)
mostrarArbolPostorden(arbol.derecho)
print arbol.datos,
¡El resultado, 1 2 3 * +, se muestra en posfijos! Este orden de recorrido se llama postorden.
Finalmente, para recorrer un árbol de forma inorden, muestras el árbol izquierdo, después la raíz y seguidamente, el árbol derecho:
def mostrarArbolInorden(arbol):
if arbol == None: return
mostrarArbolInorden(arbol.izquierdo)
print arbol.datos,
mostrarArbolInorden(arbol.derecho)
El resultado es 1 + 2 * 3, que es la expresión en forma infija.
Para ser sinceros, deberíamos señalar que hemos omitido una complicación importante. A veces, cuando escribimos una expresión en infijo, tenemos que usar paréntesis para mantener el orden de las operaciones. Así que un recorrido inorden no es suficiente para generar una expresión infija.
Sin embargo, con algunas mejoras, el árbol de expresión y los tres recorridos recursivos proporcionan una forma general de pasar expresiones de un formato a otro.
Como ejercicio, modifica mostrarArbolInorden para que ponga paréntesis alrededor de todos los operadores y pares de operandos. ¿Es el resultado correcto y claro? ¿Son los paréntesis siempre necesarios?
Si hacemos un recorrido inorden y seguimos el nivel del árbol en el que estamos, podemos generar una representación gráfica de un árbol:
def mostrarArbolSangrado(arbol, nivel=0):
if arbol == None: return
mostrarArbolSangrado(arbol.derecho, nivel+1)
print ' '*nivel + str(arbol.datos)
mostrarArbolSangrado(arbol.izquierdo, nivel+1)
El parámetro nivel nos dice el nivel en el que estamos dentro del árbol. Por defecto, inicialmente es 0. Cada vez que hagamos una llamada recursiva, pasamos nivel+1 porque el nivel del nodo hijo es siempre uno mayor que el del nodo padre.Cada elemento se sangra con dos espacios por nivel. El resultado del ejemplo del árbol es el siguiente:
>>> mostrarArbolSangrado(arbol)
3
*
2
+
1
Si miras el resultado de lado, verás una versión simplificada de la figura original.
Comentarios
En esta sección, vamos a analizar expresiones infijas y a construir sus correspondientes árboles de expresión. Por ejemplo, la expresión (3+7)*9 da como resultado el árbol siguiente:
Ten en cuenta que hemos simplificado el diagrama eliminando los nombres de los atributos.
El analizador que vamos a escribir trabaja con expresiones que incluyen números, paréntesis y los operadores + y *. Damos por hecho que la cadena de entrada ya se ha introducido en una lista de Python. La lista de elementos para (3+7)*9 es la siguiente:
['(', 3, '+', 7, ')', '*', 9, 'end']
El elemento end se utiliza para evitar que el analizador lea más allá del final de la lista.
Como actividad, escribe una función que acepte una cadena de expresión y que devuelva una lista de elementos.
La primera función que vamos a escribir es obtenerElemento, que acepta una lista de elementos y un elemento supuesto como parámetros. Compara el elemento supuesto con el primer elemento de la lista: Si coinciden, elimina el elemento de la lista y devuelve verdadero; si no, devuelve falso:
def obtenerElementos(listaElemento, supuesto):
if listaElemento[0] == supuesto:
del listaElemento[0]
return 1
else:
return 0
Como listaElemento se refiere a un objeto mutable, los cambios que se han hecho aquí son visibles para cualquier otra variable que se refiera al mismo objeto.
La siguiente función, obtenerNumero, trabaja con operandos. Si el próximo elemento en listaElemento es un número, obtenerNumero lo borra y devuelve un nodo terminal que contenga el número; si no, devuelve None.
def obtenerNumero(listaElemento):
x = listaElemento[0]
if type(x) != type(0): return None
del listaElemento[0]
return Arbol (x, None, None)
Antes de continuar, deberíamos probar obtenerNumero de forma aislada. Asignamos una lista de números a listaElemento, extraemos el primero, lo mostramos en la pantalla y mostramos lo que queda de la lista de elementos:
>>> listaElemento = [9, 11, 'end']
>>> x = obtenerNumero(listaElemento)
>>> mostrarArbolPostorden(x)
9
>>> print listaElemento
[11, 'end']
El siguiente método que necesitamos es obtenerProducto, que construye un árbol de expresión para los productos. Un producto simple tiene dos números como operandos, como 3 * 7.
Esta es una versión de obtenerProducto que trabaja con productos simples.
def obtenerProducto(listaElemento):
a = obtenerNumero(listaElemento)
if obtenerElemento(listaElemento, '*'):
b = obtenerNumero(listaElemento)
return Arbol ('*', a, b)
else:
return a
Si asumimos que obtenerNumero logra su objetivo y devuelve un árbol de instancia única, asignamos el primer operando a a. Si el siguiente carácter es *, tomamos el segundo número y construimos un árbol de expresión con a, b y el operador.
Si el siguiente carácter es cualquier otro, simplemente devolvemos el nodo terminal con a. Aquí tenemos dos ejemplos:
>>> listaElemento = [9, '*', 11, 'end']
>>> arbol = obtenerProducto(listaElemento)
>>> mostrarArbolPostorden(arbol)
9 11 *
>>> listaElemento = [9, '+', 11, 'end']
>>> arbol = obtenerProducto(listaElemento)
>>> mostrarArbolPostorden(arbol)
9
El segundo ejemplo implica que consideramos que un solo operando es un tipo de producto. Esta definición de "producto" es engañosa, pero resulta útil.
Ahora tenemos que trabajar 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 obtenerProducto, podemos trabajar arbitrariamente con un producto largo:
def obtenerProducto(listaElemento):
a = obtenerNumero(listaElemento)
if obtenerElemento(listaElemento, '*'):
b = obtenerProducto(listaElemento) # esta línea cambió
return Arbol ('*', a, b)
else:
return a
En otras palabras, un producto puede ser un singleton o un árbol con un * en la raíz, un número a la izquierda y un producto a la derecha. Este tipo de definición repetitiva debe empezar a sernos familiar.
Vamos a probar la nueva versión con un producto compuesto:
>>> listaElemento = [2, '*', 3, '*', 5 , '*', 7, 'end']
>>> arbol = obtenerProducto(listaElemento)
>>> mostrarArbolPostorden(arbol)
2 3 5 7 * * *
A continuación, añadiremos la posibilidad de analizar sumas. De nuevo, usamos una definición de "suma" ligeramente engañosa. Para nosotros, una suma puede ser un árbol con un + en la raíz, un producto a la izquierda y una suma a la derecha. O una suma puede ser sólo un producto.
Si quieres seguir utilizando esta definición, tiene una buena propiedad: Podemos representar cualquier expresión (sin paréntesis) como una suma de productos. Esta propiedad es la base de nuestro algoritmo analizador.
obtenerSuma intenta construir un árbol con un producto a la izquierda y una suma a la derecha. Pero si no encuentra una +, simplemente hace un producto.
def obtenerSuma(listaElemento):
a = obtenerProducto(listaElemento)
if obtenerElemento(listaElemento, '+'):
b = obtenerSuma(listaElemento)
return Arbol ('+', a, b)
else:
return a
Vamos a probarlo con 9 * 11 + 5 * 7:
>>> listaElemento = [9, '*', 11, '+', 5 , '*', 7, 'end']
>>> arbol = obtenerSuma(listaElemento)
>>> mostrarArbolPostorden(arbol)
9 11 * 5 7 * +
Casi hemos terminado, pero todavía tenemos que trabajar los paréntesis. En cualquier parte de una expresión en la que pueda haber un número, también puede haber una suma completa entre paréntesis. Solamente tenemos que modificar obtenerNumero para trabajar con subexpresiones:
def obtenerNumero(listaElemento):
if obtenerElemento(listaElemento, '('):
x = obtenerSuma(listaElemento) # tomar la subexpresión
obtenerElemento(listaElemento, ')') # eliminar los paréntesis
return x
else:
x = listaElemento[0]
if type(x) != type(0): return None
listaElemento[0:1] = []
return Arbol (x, None, None)
Vamos a probar este código con 9 * (11 + 5) * 7:
>>> listaElemento = [9, '*', '(', 11, '+', 5, ')', '*', 7, 'end']
>>> arbol = obtenerSuma(listaElemento)
>>> mostrarArbolPostorden(arbol)
9 11 5 + 7 * *
El analizador trabajó con los paréntesis correctamente; la suma se produce antes de la multiplicación.
En la versión final del programa, sería una buena idea dar a obtenerNumero un nombre más descriptivo de su nueva función.
Comentarios
Durante el análisis, hemos asumido que las expresiones están bien hechas. Por ejemplo, cuando llegamos al final de una subexpresión, asumimos que el siguiente carácter es un paréntesis cerrado. Si hay algún error y el siguiente carácter es otra cosa, deberíamos ocuparnos de él.
def obtenerNumero(listaElemento):
if obtenerElemento(listaElemento,'('):
x = obtenerSuma(listaElemento)
if not obtenerElemento(listaElemento, ')'):
raise 'ErrorMalaExpresion', 'faltan paréntesis'
return x
else:
# resto de la función omitida
La acción de raise crea una excepción; en este caso se crea un nuevo tipo de excepción llamado ErrorMalaExpresion. Si la función que llamó a obtenerNumero, o a cualquiera de las otras funciones del traceback, se encarga de la excepción, entonces el programa puede continuar. De lo contrario, Python mostrará un mensaje de error y se cerrará.
Como ejercicio, encuentra otros lugares en estas funciones donde pueda haber errores y añade una sentenciaraise adecuada. Prueba tu código con expresiones formadas incorrectamente.Comentarios
En esta sección, vamos a hacer un pequeño programa que utiliza un árbol para representar una base de datos de conocimiento.
El programa interactúa con el usuario para crear un árbol de preguntas y nombres de animales. Aquí tenemos un ejemplo:
¿Estás pensando en un animal? si
¿Es un pájaro? no
¿Cuál es el nombre del 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? no
¿Estás pensando en un animal? si
¿Puede volar? no
¿Es un perro? no
¿Cuál es el nombre del 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? no
¿Estás pensando en un animal? si
¿Puede volar? no
¿Ladra? si
¿Es un perro? si
¡Me salgo!
¿Estás pensando en un animal? no
Aquí está el árbol que este diálogo construye:
Al principio de cada ronda, el programa va al comienzo del árbol y hace la primera pregunta. Según la respuesta, se mueve al hijo de la izquierda o de la derecha y continúa hasta que llega a un nodo terminal. En ese momento, da un resultado. Si el resultado no es el correcto, pregunta al usuario el nombre del animal nuevo y una pregunta que distingue al mal resultado del nuevo animal. Después, añade un nodo al árbol con la nueva pregunta y el nuevo animal.
Aquí está el código:
def animal():
# comenzar con un singleton
raiz = Arbol("pájaro")
# Haz un bucle hasta que el usuario pare
while 1:
print
if not si("¿Estás pensando en un animal? "): break
# sigue el árbol
arbol = raiz
while arbol.obtenerIzquierda() != None:
mostrar = arbol.obtenerDatos() + "? "
if si(mostrar):
arbol = arbol.obtenerDerecha()
else:
arbol = arbol.obtenerIzquierda()
# dar un resultado
resultado = arbol.obtenerDatos()
mostrar = "¿Es un " + resultado + "? "
if si(mostrar):
print "¡Me salgo!"
continue
# mostrar nueva información
mostrar = "¿Cuál es el nombre del animal? "
animal = raw_input(apuntar)
mostrar = "¿Qué pregunta distinguiría un %s de un %s? "
pregunta = raw_input(apuntar % (animal,resultado))
# agregar nueva información al árbol
arbol.iniciarDatos(pregunta)
mostrar = "Si el animal fuera %s ¿cuál sería la respuesta? "
if si(mostrar % animal):
arbol.iniciarIzquierda(Arbol(resultado))
arbol.iniciarDerecha(Arbol(animal))
else:
arbol.iniciarIzquierda(Arbol(animal))
arbol.iniciarDerecha(Arbol(resultado))
La función si es un ayudante, muestra una pregunta y luego recopila información del usuario. Si la respuesta es si o Si, la función devuelve verdadero:
def si(preg):
from string import lower
ans = bajo(raw_input(preg))
return (res[0] == 'si')
La condición del bucle de salida es 1, lo que significa que continuará hasta que la sentencia break se ejecute, si el usuario no está pensando en un animal.
El bucle interior whilerecorre el árbol de arriba abajo, guiándose por las respuestas del usuario.
Cuando se añade un nuevo nodo al árbol, la nueva pregunta sustituye los datos, y los dos hijos son el nuevo animal y el dato original.
Uno de los defectos del programa es que cuando se cierra, ¡se borra todo lo que le enseñaste cariñosamente!
Como actividad, piensa en varias maneras en las que puedas guardar el árbol de conocimientos en un archivo. Implementa la que creas más sencilla.Comentarios
|
|
|
|
|
|
|