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.

Arboles de Expresiones

ARBOLES DE EXPRESIONES (TEORÍA)

Los árboles de expresiones representan el código de nivel del lenguaje en forma de datos. Los datos se almacenan en una estructura con forma de árbol. Cada nodo del árbol de expresión representa una expresión, por ejemplo, una llamada al método o una operación binaria, como x < y. En la ilustración siguiente se muestra un ejemplo de una expresión y su representación en forma de un árbol de expresión. Las diferentes partes de la expresión tienen un color distinto para hacerlas coincidir con el nodo correspondiente del árbol de expresión. También se muestran los diferentes tipos de los nodos del árbol de expresión. REGLAS PARA LA CONSTRUCCION DE ARBOLES DE EXPRESION Para contruir el árbol de expresiones que represente nuestra expresión matemática es necesario construir primero la misma expresión pero en la notación polaca correspondiente y a partir de esta es que se construye el árbol. El algoritmo usado para transformar una expresión infija a prefija es explicado a continuación. Sea A una expresión infija cualquiera, formada por operadores, paréntesis (izquierdos y derechos) y operandos, también se usará una pila para los operadores. El procedimiento seguido es el siguiente: Se lee un elemento de A, si este es un operador o un paréntesis izquierdo, entonces se actúa según la regla I y si es un operando entonces se envía directamente a la expresión de notación polaca. Si el elemento leído de A es un paréntesis derecho, entonces se desapilarán elementos de la pila de operadores hasta encontrar el correspodiente paréntesis izquierdo. Cada elemento desapilado pasa a formar parte de la notación polaca, excepto los paréntesis. Cuando no queden elementos en A, entonces se desapilan operadores de la pila, hasta que esta quede vacía. Regla I: Existe un orden de prioridad para los operadores, que de menor a mayor es el siguiente: suma (+) y resta (-), multiplicación (*) y división (/), exponenciación (^), operadores unarios. El paréntesis izquierdo lo trataremos como un operador (aunque no lo es) cuyo orden de prioridad es el mayor de todos cuando se quiera apilar y el menor de todos cuando esté en la cima de la pila. Cuando se intente apilar algún operador se hará lo siguiente: si es un operador unario entonces se apila, si es un operador binario, se comparará su prioridad con el último insertado en la pila (el de la cima), si su prioridad es mayor, entonces se apilará. Si ocurre lo contrario (su prioridad es menor o igual) entonces el operador de la cima de la pila se desapilará y pasará a formar parte de la notación polaca. Se volverá a intentar apilar el operador siguiendo la misma regla, hasta que se pueda apilar, si la pila queda vacía también se apila. El paréntesis izquierdo siempre se apilará y no podrá ser desapilado por ningún operador y por tanto no formará parte de la notación polaca inversa. El siguiente ejemplo, ayudará a entender mejor lo dicho anteriomente. Sea la siguiente expresión infija: 2^sin(y+x)–ln(x). En la siguiente tabla se muestra paso a paso la conversión a notación postfija. Se usa el color rojo para señalar los casos en que es necesario desapilar operadores de la pila. Construccion del árbol binario de expresiones Una vez obtenida la expresión en notación postfija, se puede evaluar mediante el uso nuevamente de una pila. Sin embargo, en nuestro caso se trabaja con una árbol binario de expresiones, así que lo que se hace es construir el árbol. El algoritmo usado para construir el árbol no usa como tal la expresión postfija ya conformada, sino que el árbol se va construyendo usando las mismas reglas con las que se construye la notación postfija, una pila para los operadores y otra para los nodos del árbol, ambas no son necesitadas al terminar el árbol. El algoritmo es el siguiente: Se siguen las mismas reglas expuestas anteriormente usando la pila de operadores, pero cuando se encuentra un operando o un operador es desapilado, entonces se crea el nodo correspondiente y se actúa según la regla II. Al finalizar el algoritmo solo debe quedar un nodo apilado en la pila de nodos, el que constituye el nodo raíz de nuestro árbol de expresiones. Regla II. Si el nodo corresponde a un operando, entonces se apila. Si el nodo corresponde a una operador unario entonces se desapila un nodo de la pila de nodos y es enlazado a la rama izquierda del nodo correspondiente al operador unario y este último es apilado. Si el nodo corresponde a un operador binario entonces dos nodos son desapilados de la pila de nodos, el primero es enlazado a la rama derecha del nodo binario y el segundo a la rama izquierda, nuevamente este nodo es apilado. En el siguiente ejemplo se usa la misma expresión infija anterior (2^sin(y+x) – ln (x)) para ilustrar el procedimiento para construir el árbol: Recorrido en preorden En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha. En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4. void preorden(tArbol *a) {   if (a != NULL) {     tratar(a);                        //Realiza una operación en nodo     preorden(a->hIzquierdo);     preorden(a->hDerecho);   } } Implementación en pseudocódigo de forma iterativa: push(s,NULL);       //insertamos en una pila (stack) el valor NULL, para asegurarnos de que esté vacía push(s,raíz);                       //insertamos el nodo raíz MIENTRAS (s <> NULL) HACER     p = pop(s);                     //sacamos un elemento de la pila     tratar(p);                      //realizamos operaciones sobre el nodo p     SI (D(p) <> NULL)               //preguntamos si p tiene árbol derecho          ENTONCES push(s,D(p));     FIN-SI     SI (I(p) <> NULL)               //preguntamos si p tiene árbol izquierdo          ENTONCES push(s,I(p));     FIN-SI

1 ÁRBOLES DE EXPRESION  2 Un árbol de expresión sirve para evaluar expresiones del tipo:(a+b)*c/dPara que un árbol represente una expresión se deben tomar en cuenta 2 características muy importantes:Cualquier hoja está etiquetada sólo con un operando.Cualquier nodo interior n está etiquetado por un operador. 3 Por ejemplo, para representar una expresion el arbol  quedaria como sigue:a+(b-c)*d/c+ / a c * - d b  4 Otro ejemplo:(a+b)*(c+d)* + + a b d c  5 Al introducir la expresión debemos de tomar en cuenta las siguientes características: La raíz siempre debe ser un operadorLas hojas siempre deben ser operandosLos nodos deben estar etiquetados por operadoresSi un operador tiene mayor prioridad que la raiz se coloca como hijo.Si un operador tiene igual o menor prioridad que un nodo se coloca como padre.Un nodo puede contener como hijo otro subarbol que contiene un pequeña expresion. 6 En los árboles de expresión, la sucesión del preorden de etiquetas nos da lo que se conoce como la forma prefijo de una expresiónAnálogamente, la sucesión postorden de las etiquetas de un árbol expresión nos da lo que se conoce como la representación postfijo de una expresiónFinalmente, el inorden de una expresión en un árbol de expresión nos da la expresión infijo en sí misma, pero sin paréntesis 7 CONSTRUCCION DE UN ARBOL DE EXPRESION Agoritmo:Mientras carácter diferente de nuloLeer carácter de la listaSi es paréntesis pasar al siguiente carácterCrear un nodo nuevo que contenga ese carácterSi el carácter que tiene nuevo es un:Operandosi el árbol esta vacío hacer raíz a nuevosi no recorrer el árbol por la derecha hasta llegar a un nodo con hojassi la hoja izquierda, no esta etiquetada colocar operandosi no colocarlo en la hoja derecha.Operadorsi la raíz es un operandoinsertar nuevo en ese nodo, y convertir el operandoen el hijo izq.si nosi hay un paréntesis abiertoinsertar nuevo en la ultima hoja derecha y colocar operandocomo hijo izquierdo

Ejercicio Maquina de Turing