20.4. Recorrido de un árbol

Podemos recorrer un árbol de expresión e imprimir el contenido así:

   1: def imprimeArbol(arbol):

   2:     if arbol == None: return

   3:         print arbol.carga,

   4:         imprimeArbol(arbol.izquierda)

   5:         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:

   1: >>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3)))

   2: >>> imprimeArbol(arbol)

   3: + 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á:

   1: def imprimeArbolPostfijo(arbol):

   2:     if arbol == None: return

   3:         imprimeArbolPostfijo(arbol.izquierda)

   4:         imprimeArbolPostfijo(arbol.derecha)

   5:         print arbol.carga

¡El resultado, 1 2 3 * +, esta 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:

   1: def imprimeArbolInfijo(arbol):

   2:     if arbol == None: return

   3:         imprimeArbolInfijo(arbol.izquierda)

   4:         print arbol.carga,

   5:         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 operaciones. 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 traducir expresiones de un formato a otro.

Como ejercicio, modifique imprimeArbolInfijo de modo que pon-
ga 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 que nivel del árbol estamos, podemos generar una representación grafica de un árbol:

   1: def imprimeArbolSangrado(arbol, nivel=0):

   2:     if arbol == None: return

   3:         imprimeArbolSangrado(arbol.derecha, nivel+1)

   4:         print ' '*nivel + str(arbol.carga)

   5:         imprimeArbolSangrado(arbol.izquierda, nivel+1)

 

El parámetro nivel lleva la cuenta de donde estamos en el árbol. Por omisión,
inicialmente 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:

   1: >>> imprimeArbolSangrado(arbol)

   2:     3

   3:    *

   4:   2

   5:  +

   6:   1

 

Si mira la salida de lado, vera una versión simplificada de la figura original.