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}