Recorridos de árboles Binarios

Hay tres patrones de uso común para visitar todos los nodos de un árbol. La diferencia entre estos patrones es el orden en que es visitado cada nodo. Llamamos a estas visitas de los nodos un “recorrido”. Los tres recorridos que vamos a ver se llaman preorden, inorden y postorden. Comencemos definiendo estos tres recorridos con más cuidado, para luego mirar algunos ejemplos donde estos patrones son útiles.

preorden

En un recorrido en preorden, visitamos primero el nodo raíz, luego recursivamente realizamos un recorrido en preorden del subárbol izquierdo, seguido de un recorrido recursivo en preorden del subárbol derecho.

inorden

En un recorrido en inorden, realizamos recursivamente un recorrido en inorden en el subárbol izquierdo, visitamos el nodo raíz, y finalmente hacemos un recorrido recursivo en inorden del subárbol derecho.

postorden

En un recorrido en postorden, realizamos recursivamente recorridos en postorden del subárbol izquierdo y del subárbol derecho seguidos de una visita al nodo raíz.

Veamos algunos ejemplos que ilustran cada uno de estos tres tipos de recorridos. Primero veamos el recorrido en preorden. Como ejemplo de un árbol a recorrer, representaremos este libro como un árbol. El libro es la raíz del árbol, y cada capítulo es un hijo de la raíz. Cada sección dentro de un capítulo es un hijo del capítulo, y cada subsección es un hijo de su sección, y así sucesivamente. La Figura 5 muestra una versión limitada de un libro con sólo dos capítulos. Tenga en cuenta que el algoritmo de recorrido funciona para árboles con cualquier número de hijos, pero nos limitaremos a los árboles binarios por ahora.

Figura 5: Representación de un libro como un árbol

Figura 5: Representación de un libro como un árbol

Supongamos que usted quería leer este libro de adelante hacia atrás. El recorrido en preorden le da a usted exactamente ese orden. A partir de la raíz del árbol (el nodo Libro) seguiremos las instrucciones del recorrido en preorden. Recursivamente llamamos a preorden sobre el hijo izquierdo, en este caso Capítulo 1. De nuevo recursivamente llamamos a preorden sobre el hijo izquierdo para llegar a Sección 1.1. Como Sección 1.1 no tiene hijos, no realizamos llamadas recursivas adicionales. Cuando terminemos con Sección 1.1, subiremos por el árbol hasta Capítulo 1. En este punto todavía necesitamos visitar el subárbol derecho de Capítulo 1, que es Sección 1.2. Visitamos como antes el subárbol izquierdo, lo cual nos lleva a Sección 1.2.1, luego visitamos el nodo para Sección 1.2.2. Habiendo terminado con Sección 1.2, regresamos a Capítulo 1. Luego regresamos al nodo Libro y seguimos el mismo procedimiento para Capítulo 2.

El código para escribir los recorridos de árboles es sorprendentemente elegante, en gran medida porque los recorridos se escriben recursivamente. El Programa 2 muestra el código en Python para un recorrido en preorden de un árbol binario.

Usted podría preguntarse, ¿cuál es la mejor manera de escribir un algoritmo como el del recorrido en preorden? ¿Debería ser una función que simplemente usa un árbol como estructura de datos, o debería ser un método de la propia estructura de datos árbol? El Programa 2 muestra una versión del recorrido en preorden escrito como una función externa que recibe un árbol binario como parámetro. La función externa es particularmente elegante porque nuestro caso base es simplemente comprobar si el árbol existe. Si el parámetro arbol es None, entonces la función retorna sin tomar ninguna acción.

Programa 2

def preorden(arbol):
    if arbol:
        print(arbol.obtenerValorRaiz())
        preorden(arbol.obtenerHijoIzquierdo())
        preorden(arbol.obtenerHijoDerecho())

También podemos implementar preorden como un método de la clase ArbolBinario. El código para implementar preorden como método interno se muestra en el Programa 3. Observe lo que ocurre cuando cambiamos el código de interno a externo. En general, solo reemplazamos arbol con self. Sin embargo, también necesitamos modificar el caso base. El método interno debe comprobar la existencia de los hijos izquierdo y derecho antes de hacer la llamada recursiva a preorden.

Programa 3

def preorden(self):
    print(self.clave)
    if self.hijoIzquierdo:
        self.hijoIzquierdo.preorden()
    if self.hijoDerecho:
        self.hijoDerecho.preorden()

¿Cuál de estas dos formas de implementar a preorden es mejor? La respuesta es que la implementación de preorden como una función externa es probablemente mejor en este caso. La razón es que usted muy rara vez sólo querrá recorrer el árbol. En la mayoría de los casos usted va a querer lograr algo más mientras usa uno de los patrones básicos de recorrido. De hecho, veremos en el siguiente ejemplo que el patrón de recorrido en postorden sigue muy de cerca el código que escribimos anteriormente para evaluar un árbol de análisis. Por lo tanto, escribiremos el resto de los recorridos como funciones externas.

El algoritmo para el recorrido en postorden, que se muestra en el Programa 4, es casi idéntico al de preorden, excepto que trasladamos la llamada a print al final de la función.

Programa 4

def postorden(arbol):
    if arbol != None:
        postorden(arbol.obtenerHijoIzquierdo())
        postorden(arbol.obtenerHijoDerecho())
        print(arbol.obtenerValorRaiz())

Ya hemos visto un uso común para el recorrido en postorden, a saber, la evaluación de un árbol de análisis. Vuelva a mirar el Programa 1. Lo que estamos haciendo es evaluar el subárbol izquierdo, evaluar el subárbol derecho, y combinarlos en la raíz a través de la llamada de función a un operador. Supongamos que nuestro árbol binario sólo va a almacenar datos de árboles de expresiones. Vamos a reescribir la función de evaluación, pero modelándola aún más parecida al código postorden del Programa 4 (ver el Programa 5).

Programa 5

def evalPostorden(arbol):
    operadores = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
    res1 = None
    res2 = None
    if arbol:
        res1 = evalPostorden(arbol.obtenerHijoIzquierdo())
        res2 = evalPostorden(arbol.obtenerHijoDerecho())
        if res1 and res2:
            return operadores[arbol.obtenerValorRaiz()](res1,res2)
        else:
            return arbol.obtenerValorRaiz()

Note que la forma del Programa 4 es la misma forma del Programa 5, excepto que en lugar de imprimir la clave al final de la función, la devolvemos. Esto nos permite guardar los valores devueltos de las llamadas recursivas en las líneas 6 y 7. A continuación, usamos estos valores guardados junto con el operador en la línea 9.

El recorrido final que veremos en esta sección es el recorrido en inorden. En el recorrido en inorden visitamos el subárbol izquierdo, seguido por la raíz, y finalmente el subárbol derecho. El Programa 6muestra nuestro código para el recorrido en inorden. Observe que en las tres funciones de recorridos simplemente estamos cambiando la posición de la instrucción print con respecto a las dos llamadas de función recursivas.

Programa 6

def inorden(arbol):
  if arbol != None:
      inorden(arbol.obtenerHijoIzquierdo())
      print(arbol.obtenerValorRaiz())
      inorden(arbol.obtenerHijoDerecho())

Si realizamos un simple recorrido en inorden de un árbol de análisis, recuperamos nuestra expresión original, sin paréntesis. Vamos a modificar el algoritmo básico de inorden para permitirnos recuperar la versión completamente agrupada de la expresión. Las únicas modificaciones que haremos en la plantilla básica son las siguientes: imprimir un paréntesis izquierdo antes la llamada recursiva al subárbol izquierdo, e imprimir un paréntesis derecho después de la llamada recursiva al subárbol derecho. El código modificado se muestra en el Programa 7.

Programa 7

def imprimirExpresion(arbol):
  valorCadena = ""
  if arbol:
      valorCadena = '(' + imprimirExpresion(arbol.obtenerHijoIzquierdo())
      valorCadena = valorCadena + str(arbol.obtenerValorRaiz())
      valorCadena = valorCadena + imprimirExpresion(arbol.obtenerHijoDerecho())+')'
  return valorCadena

Note que la función imprimirExpresion, tal como la hemos implementado, pone paréntesis alrededor de cada número. Aunque no es incorrecto, los paréntesis claramente no son necesarios. En los ejercicios al final de este capítulo se le pedirá a usted que modifique la función imprimirExpresion para eliminar dicho conjunto de paréntesis.