CAPÍTULO III.
ÁRBOLES BINARIOS
En la vida cotidiana, muchas vedes sin saberlo, trabajamos en ocasiones con los árboles. Por ejemplo: árboles genealógicos, organigramas, directorios en los discos de un computador, etc. Cada uno de estos conceptos representa un árbol.
ORGANIGRAMA DE UNA EMPRESA
ORGANIZACIOND E UN DIRECTORIO EN UN COMPUTADOR
3.1.DEFINICIONES
En el área de la computación también se conoce una materia que trata de los árboles. Este tema es muy extenso y para su estudio vamos a dividirlo en varios capítulos.
En este capitulo nos vamos a circunscribir solamente en el estudio de los árboles binarios. Este tipo de árbol se caracteriza porque tiene un vértice principal y de él se desprende dos ramas. La rama izquierda y la rama derecha.
La rama izquierda y la derecha, también son dos árboles binarios. El vértice principal se denomina raíz y cada una de las ramas se denomina árbol izquierdo y árbol derecho. Por ejemplo:
La raíz de este árbol es A y el árbol izquierdo esta conformado por otro árbol.
Que a su vez tiene como raíz B. el árbol derecho esta conformado también por otro árbol.
DEFINICIONES
NODO
Un árbol binario es un conjunto de elementos cada uno de los cuales se denomina nodo. Un árbol binario puede tener cero nodos y en este se dice que esta vació. Puede tener un solo nodo, y en este caso existe solamente la raíz del árbol o puede tener un número finito de nodos. Cada nodo que esta ramificado por la izquierda o por la derecha o puede no tener ninguna ramificación. La anatomía de un nodo en un árbol binario es la siguiente:
Información del nodo
Apuntador al árbol de la derecha
Apuntador al árbol de la izquierda
Raíz en un árbol binario se pueden distinguir la raíz principal y las raíces de los demás subárboles. Por ejemplo:
La raíz principal es el nodo cuya información es A. podemos distinguir también el árbol.
Cuya raíz es el nodo con información D. Este nodo es la raíz del árbol de la derecha. El Árbol de la izquierda
Tiene como raíz el nodo cuya información es B y tiene solamente una ramificación.
PADRE
Un padre es un nodo que puede o no tener ramificaciones. Por ejemplo:
Caso 1 caso 2 caso3
En los tres casos el nodo A es un padre. En el caso 1 es un padre que no tiene hijos. En el caso 2, el nodo A es el padre del nodo B. en el caso 3 el nodo A es padre de los nodos By C peo no es padre del nodo D.
HIJO
Nos referimos al ejemplo anterior. En el caso 1 el nodo A no tiene hijos. En el caso 2, B es un hijo del nodo A y en el caso 3, D es hijo de B y el padre de B es el nodo A
HERMANO
Nos referimos al caso 3 del ejemplo anterior. Los hermanos son los hijos de un mismo padre. Los nodos B y C son hermanos. El nodo D no tiene hermanos
HOJA
Una hoja es un nodo que no tiene ramificaciones. Por ejemplo
El nodo C es una hoja mientras que el nodo B no se puede considerar como hoja porque tiene una ramificación por la derecha. El nodo D también es una hoja
NODO NO TERMINAL
Un nodo no Terminal es aquel que posee por lo menos una ramificación. En el ejemplo anterior, el nodo A o el B son nodos no terminales, mientras el nodo D o el nodo C son nodos terminales.
CAMINO
Un árbol siempre se examina hacia abajo. Por ejemplo:
Al nodo C podemos llegar desde el nodo B. Nunca se puede examinar el nodo B a partir del nodo C. Los apuntadores derecho o izquierdo de cualquier nodo apuntan al árbol derecho o izquierdo que siguen a ese nodo. Nunca apuntan a los nodos precedentes. Un camino es el conjunto de nodos que tenemos que visitar con el propósito de llegar a un nodo específico. Por ejemplo para llegar al nodo F es necesario recorrer el camino
A D F
Del mismo nodo, para llegar al nodo G debemos recorrer el camino
A D E G
Obsérvese que los caminos se configuran siempre hacia abajo. Nunca se puede hablar de un camino para llegar al nodo C así:
G E D A B C
Este camino se puede configurar.
LONGITUD
Longitud es el número de nodos que se deben recorrer para pasar de un nodo a otro. Por ejemplo:
La longitud entre A y E es 3. La longitud entre G y G es 0. La longitud entre A y B es 1 Obsérvese que no podemos calcular la longitud entre B y G ya que el camino B A G no existe.
DESCENDIENTE
El nodo C es descendiente del nodo A si a partir de A podemos llegar a C a través de un camino. Por ejemplo:
El nodo C es descendiente de A ya que a C podemos llagar por el camino
A B C
Siempre que exista un camino para llegar de un nodo V a un nodo X, el nodo X es un descendiente de V. pAra el ejemplo anterior, el nodo E es descendiente de D pero el nodo no es descendiente de B
ANCESTRO
El nodo A es un ancestro del nodo C si existe un camino entre A y C. basándonos en el ejemplo anterior. A es un ancestro de C ya que existe un camino entre los nodos. No se puede hablar de que D sea ancestro de ya que el camino D A B no existe
NIVEL
Cada nodo tiene un nivel dentro de un árbol binario. Por definición el nodo raíz tiene un nivel y de los demás nodos tienen el nivel de su padre más 1. Por esto los nodos que son hijos del nodo raíz tienen un nivel 1. Veamos este ejemplo
NIVEL 0
NIVEL 1
NIVEL 2
NIVEL 3
Los nodos A, M y S tienen un nivel 0 en tanto que los nodos G y V tienen un nivel 3. Obsérvese que le nivel del nodo G es la longitud del camino desde la raíz hasta el nodo.
GRADO DE UN NODO
El grado de un nodo es el número de hijos. Por ejemplo el grado del nodo A es 2, el grado del nodo T es 1. El grado de un nodo Terminal siempre es 0.en los árboles binarios, el grado de un nodo fluctúa entre 0 y 2. Existen otros tipos de árboles, (árbol n_ario), en los cuales esta restricción no existe. Estos arboles serán estudiados en el segundo tomo de este libro
ALTURA
La altura de un árbol binario es el nivel de la hoja o de las hojas que están más distantes de la raíz. Basándonos en el ejemplo anterior, la altura del árbol cuya raíz es A, corresponde a la longitud del camino para llegar a la hoja más distante de la raíz. En este caso será 3. La altura cuya raíz es M, corresponde al nivel de la hoja P.
ARBOL BINARIO COMPLETO
Un árbol binario completo es aquel en el que todo nodo no Terminal tiene sus dos hijos. El siguiente es un árbol binario de nivel 3:
NIVEL 0
NIVEL 1
NIVEL 2
NIVEL 3
Obsérvese que todos los nodos no terminales tienen sus dos hijos. El máximo número de nodos que puede tener un árbol de nivel n es:
20 + 21 + 22 + 23….+ 2n
Si n es 3 entonces
20 + 21 + 22 + 23 =15
Este árbol es un árbol binario completo de nivel 3 y este es el máximo número de nodos que puede tener un árbol de nivel 3.
ARBOL BINARIO IGUAL
Dos árboles son iguales si los dos son vacíos. Existe otro caso ene. Cual dos árboles son iguales:
Estos árboles son iguales porque sus raíces son iguales y también lo son su respectivo árbol izquierdo y derecho. Para que un árbol sea igual a otro, es necesario que el contenido de cada uno de sus respectivos nodos sea el mismo y que legan las mismas relaciones de parentesco. Por ejemplo los siguientes árboles
Son diferentes porque el contenido de sus respectivos nodos es diferente. Obsérvese que sus nodos tienen las mismas relaciones de parentesco.
ARBOL BINARIO SEMEJANTE
Dos árboles son semejantes si tienen el mismo número de nodos y los valores de los nodos del primer árbol son los mismos que los valores de los nodos del segundo, sin importar la relación de parentesco entre ellos. Por ejemplo:
Estos árboles son semejantes. Contienen los mismos valores en cada uno de sus nodos.
ARBOL BINARIO ISOMORFO
Dos árboles binarios son isomorfos si tienen la misma estructura aunque el contenido de cada uno e sus nodos sea diferente. Por ejemplo los siguientes árboles son isomorfos.
PESO
El peso de un árbol en un nodo dado es el número de nodos en el árbol sin contarse el mismo. Por ejemplo:
El peso del árbol cuya raíz es A corresponde al número de nodos de ese árbol: los nodos Q,C y R tienen un peso de 2
FORMAS DE RECORRER UN ARBOL BINARIO
Universalmente existen 3 formas de recorrer un árbol binario:
Preorden
Inorden
Posorden
Si logramos construir un árbol como este:
Podemos extraer sus datos de 3 maneras. Veamos cada una. Recorrer un árbol en preorden consiste en:
Examinar el ato del nodo raíz
Recorrer el árbol izquierdo en preorden
Recorrer el árbol derecho en preorden
Si deseamos recorrer todo el árbol, evidentemente debemos comenzar por el nodo raíz. Este método exige examinar primero el nodo raíz debemos entender como examinar un nodo, el hecho de efectuar sobre su información cualquier acción: por ejemplo escribirla, efectuar alguna operación matemática sobre ella o con ella, modificarla. También en la gran mayoría de los textos de estructuras de información, se utiliza el termino visitar un nodo. Entre la palabra examinar y la palabra visitar existe una diferencia. Examinar un nodo es revisar su contenido y eventualmente modificarlo en tanto que visitar un nodo es utilizar la dirección de ese nodo con el propósito de seguir explorando el árbol hacia abajo. Si deseamos recorrer un árbol en preorden, con el propósito de escribir su contenido, debemos examinar el contenido de cada uno se sus nodos, mientras si deseamos contar sus nodos, es necesario visitar cada nodo.
Supongamos que deseamos escribir un árbol en preorden. Para hacerlo, se debe examinar el nodo raíz y luego recorrer el árbol de la izquierda en preorden.
ARBOL A LA IZQUIERDA DE A
Recorrer este árbol en preorden es examinar su nodo raíz y recorrer de nuevo el árbol de la izquierda preorden.
ARBOL A LA IZQUIERDA DE B
Recorrer este árbol en preorden es examinar su nodo raíz. Como ya no existen nodos por la izquierda, debemos empezar a recorrer el árbol D por la derecha. Como ya no existen nodos por la derecha, debemos recorrer el árbol.
Por la derecha. El árbol de la derecha lo debemos recorrer también en preorden.
ARBOL A LA DERECHA DE B
Recorrer este árbol en preorden, es examinar su nodo raíz y recorrer el árbol por la izquierda en preorden y luego recorrerlo por la derecha. Como no existen árboles ni por la izquierda ni por la derecha, debemos recorrer el árbol.
En preorden. El orden en el cual debemos examinar estos nodos es: primero el nodo C, luego F y luego G. por lo tanto al imprimir el árbol anterior en preorden, los resultados deben ser:
A B D E C F G
Antes de seguir adelante, el lector debe certificar que el árbol:
Al imprimirlo recorriéndolo en Preorden debe generar los siguientes resultados:
10 5 3 1 4 7 9 15 14 17 16 20
Ahora veamos la segunda forma de recorrer un árbol binario. Recorrer un árbol en inorden, consiste en:
Recorrer el árbol izquierdo en inorden
Examinar la raíz
Recorrer el árbol derecho en inorden.
Por ejemplo:
Si queremos imprimir este árbol en inorden, debemos primero recorrer el árbol izquierdo en inorden:
Al tratar de recorrer este árbol en inorden y no existe árbol por su izquierda debemos examinar el nodo y luego recorrer el árbol de su derecha. Al no existir árbol por su derecha, entonces el árbol a la izquierda del nodo A ha sido totalmente recorrido. Siguiendo con las normas establecidas inicialmente, debemos examinar el nodo A y luego recorrer el árbol a la derecha del nodo A
ARBOL DERECHO DE A
Para recorrer este árbol en inorden primero debemos recorrer el árbol izquierdo. Al no existir árbol izquierdo, se debe examinar este nodo y luego recorrer el árbol derecho. Al no existir árbol derecho, el árbol ya ha sido recorrido en su totalidad. Por lo tanto los datos impresos serán:
B A C
Observemos este otro ejemplo
Debemos recorrer en inorden el árbol a la izquierda de la raíz:
Al recorrer este árbol en inorden ya sabemos, de acuerdo a la explicación del ejemplo anterior, que los resultados son:
3 5 7
Al terminar de recorrer el árbol a la izquierda de la raíz, debemos examinar la raíz y luego recorrer en inorden el árbol a la derecha de la raíz
Sabemos que al recorrer este árbol en inorden, los resultados son:
11 12 15
Con lo cual al examinar todo el árbol en inorden, los datos impresos serán:
3 5 7 10 11 12 15
Se invita al lector a certificar que al recorrer el siguiente árbol binario en inorden los resultados son:
H D I B E A J F C K G L
Veamos el árbol
Por ultimo estudiemos la tercera forma de recorrer un árbol binario. Examinar un árbol binario en posorden consiste en:
Recorrer el árbol izquierdo posorden
Recorrer el árbol derecho en posorden
Examinar la raíz.
Veamos un ejemplo:
Al recorrer el árbol izquierdo en posorden, el único dato impreso será B. después de haber recorrido todo el árbol de la izquierda en posorden, se debe recorrer todo el árbol de la derecha en posorden. Al recorrer el árbol de la derecha en posorden, el único dato impreso será C. una vez recorridos los árboles izquierdo y derecho, debemos examinar la raíz. Según esto los datos impresos serán.
B C A
Ejercicios
1. Elaborar un programa que cree en la memoria del computador el siguiente árbol binario:
2. Dado el siguiente árbol binario:
Certificar que al recorrer el árbol, los siguientes resultados son correctos:
Preorden ABCDFGEIJ
Inorden BAFDGCIEJ
Posorden BFGDIJECA
3. Suponga que en memorial del computador existe el siguiente árbol:
Escriba un conjunto de instrucciones que cree un nodo X a la derecha de B y un nodo Y a la derecha de E.
4. dado el siguiente árbol: raíz
Cuales serian los datos impresos si se recorre en:
Preorden
Inorden
Posorden
MANTENIMIENTO DE UN CONJUNTO DE NUMEROS CLASIFICADOS ASCENDENTEMENTE, UTILIZANDO UN ARBOL BINARIO ORDENADO.
Utilizando un árbol binario, es posible mantener un conjunto de números clasificados ascendentemente sin necesidad de rutinas de ordenamiento. Se plantea el problema de leer un conjunto de enteros y listarlos clasificados ascendentemente.
Los números repetidos deben ser rechazados. Por ejemplo si la entrada es:
87 25 23 25 48 8 92
El programa debe generar los siguientes resultados:
8 23 25 48 87 92
Este problema se puede resolver fácilmente utilizando un árbol binario ordenado. Solamente es necesario ir leyendo cifra por cifra e ir adicionándola en el árbol así: si es menor al contenido del nodo analizado la instemos por la izquierda de ese nodo y se es mayor por la derecha. Veamos: al leer el número 87, creamos con este dato el nodo raíz. Luego al leer el 25, como 25 es menor que 87, creamos un nuevo nodo a la izquierda de 87. Visualmente el árbol creado hasta el momento sería:
Luego al leer el número 23, como este dato es menor a 87, nos debemos desplazar hacia abajo por la izquierda. Al llegar al 25, debemos crear un nuevo nodo a la izquierda por el hecho de que 23 es menor que 25, así:
Al leer el siguiente dato este debe ser rechazado porque ya existe en el árbol. Al leer el 48, debemos desplazarnos por la izquierda y al compararlo con 25, se debe crear un nuevo nodo a la derecha del 25, así:
Siguiendo este mismo procedimiento, enumero 8 debe insertarse a la izquierda del 23 así
Por ultimo al leer el numero 92 este debe insertarse a la derecha del 87. Los datos en el. Árbol quedan, finalmente, distribuidos así:
Si imprimimos el contenido del árbol, recorriéndolo en inorden. Tendremos la lista pedida:
8 23 25 48 87 92
IMPRESIÓN DE UN ARBOL EN INORDEN
Observemos el siguiente árbol:
Raíz
Al escribir este árbol en inorden los resultados serán:
3 5 6 7 8 10 15 20
Observando el proceso, lo primero que se escribe siempre es el contenido del nodo de la extrema izquierda del árbol. Luego debemos escribir el contenido del nodo padre para luego escribir en inorden el árbol de la derecha.
IMPRESIÓN DE UN ARBOL EN PREORDEN USANDO UNA PILA
Deseamos escribir un árbol en preorden. Veamos esta estructura:
R
A
G
B I
E
H
D F J
La función que vamos a elaborar debe escribir:
100 50 30 10 40 60 65 150 120 160 180
Esta nueva función se diferencia de a función inorden ( ), en que en aquella primero se recorría el árbol izquierdo y luego si se escribía el contenido del padre de ese árbol. En esta nueva rutina primero se debe escribir el contenido del padre del árbol y luego se recorrer en preorden la rama izquierda.
El siguiente paso consiste en retirar de la pila la dirección C y determinar si existe un árbol por la derecha del nodo indicado por C. siguiendo el comportamiento de la pila, podemos por esto, deducir que esta función es muy parecida a la función inorden ( ). La diferencia radica en que antes de analizar el árbol izquierdo, la información del nodo ya ha sido escrita. Veamos el comportamiento del proceso:
Contenido la pila numero escrito
100
50
30
10
-
-
40
-
60
65
-
-
150
120
-
180
-
IMPRESIÓN DE UN ARBOL EN POSORDEN USANSO UNA PILA
La impresión de un árbol en posorden, es un poco más compleja y requiere de modificaciones en el manejo de la pila Veamos este árbol:
La impresión en posorden es:
3 7 5 20 40 30 10
Antes de imprimir el nodo, debemos recorrer el árbol izquierdo y luego el derecho. Es claro que primero debemos llegar hasta la hoja de la extrema izquierda del árbol, guardando los apuntes en una pila para luego poder recuperar las direcciones de todos los ancestros de esa hoja. Se llegamos a la hoja:
Antes de escribir el contenido del nodo debemos certificar que ya han sido recorridos en posorden los árboles izquierdo y derecho.
IMPRESIÓN DE UN ARBOL POR NIVELES USANDO UNA COLA
Imprimir un árbol por niveles, es imprimir primero su raíz, luego los contenidos de los nodos del nivel 1, luego los contenidos de los nodos del nivel 2, y así sucesivamente hasta imprimir el contenido de los nodos del ultimo nivel. Por ejemplo:
Al imprimir este árbol por niveles, los resultados serán:
20 10 30 5 15 25 40 7 50
Aprovechando una estructura FIFO, podemos efectuar esta impresión sin ningún problema.
Al comenzar almacenamos en una cola la dirección del nodo raíz:
Ahora mientras la cola no este vacía, retiramos el primer elemento de la cola y escribimos el contenido de la dirección del elemento retirado e insertamos en la cola las direcciones izquierda y derecha almacenadas en el contenido de la dirección retirada de la cola
Siguiendo este mismo procedimiento, tendríamos los siguientes estados de la cola:
10
30
5
15
25
40
7
50
Revisando el proceso anterior, observamos dos cosas: la primera es que cuando un apuntador es NULL, a la cola no se adiciona ningún elemento y la segunda es que este proceso repetitivo se debe efectuar mientras la cola no esté vacía.
RECONSTRUCCION DE UNA RBOL BINARIO
Se plantea el problema de reconstruir un árbol binario dados sus recorridos en preorden y en inorden. Por ejemplo, si un árbol genera lo siguiente: al recorrerse en preorden:
G E A I B M C L D F K J H
Y genera lo siguiente al recorrerse en inorden:
I A B E G L D C F M K H J
Se requiere de un programa que a partir de estos datos, genere un árbol binario al cual correspondan las dos impresiones. Vamos a considerar que a la función que elabora este trabajo entran dos arreglos. El método es muy sencillo y consiste en utilizar una estructura LIFO como la herramienta fundamental. Lo más sencillo del proceso es determinar la raíz del árbol. Para el caso que nos ocupa la raíz será:
Vamos a utilizar los apuntadores p y q como auxiliares de trabajo.
Pre G E A I B M C L D F K J H
In I A B E G L D C F M K H J
Si se recorre este árbol en Preorden, el primer nodo que visita es G y al recorrerlo en inorden el nodo del extremo izquierdo es I. en este lugar podemos afirmar que los nodos EAIB, forman el sub.-árbol izquierdo de G y los nodos MCLDFKJH el sub.-árbol derecho q
Raíz p
El problema esta dividido en dos. Ya sabemos que la raíz es G y también sabemos los componentes de la izquierda y de la derecha. Ahora podemos guardar en una pila los componentes del árbol derecho y seguir trabajando sobre el árbol izquierdo. Es decir tratar de organizar el árbol izquierdo.
La pila quedara así:
Vamos a considerar la G del recuadro como un apuntador que esta en la pila que nos indica la dirección del nodo padre de este sub.-árbol derecho. Ahora debemos seguir trabajando con el sub.-árbol izquierdo.
EAIB
IABE
De la misma forma, el nodo raíz de este nuevo árbol es E. este nodo debe conectarse al nodo G así
Q
El apuntador que siempre debe estar dirigido al nodo al cual se conectara el nuevo nodo posteriormente. Siempre el nuevo nodo será indicado por el apuntador p. con lo anterior el árbol estará organizado así:
Obsérvese con cuidado porque el nodo E no tiene sub-árbol derecho. Siguiendo el mismo orden, debemos crear un nodo A, el cual conectara por la izquierda con E y este nodo si tendrá sub- árbol por la derecha, así:
Como siempre que aparezca un sub-árbol derecho debemos actualizar la pila , su nueva información será:
Siguiendo por la izquierda, ahora podemos conectar el nodo I, quedando el árbol así:
En este lugar debemos efectuar un retiro de la pila y conectar el nuevo nodo por la dercha del nodo indicado por el apuntador que estaba almacenando en el primer elemento de la pila.
Con esto, el arbol queda así:
Y la pila contendrá solamente un elemento. Como ya se distribuyo la información el árbol izquierdo, debemos retirar de la pila el elemento y conectar por la derecha un nuevo nodo M, quedando el árbol así:
La nueva información de la pila será.
Y continuamos trabajando con el árbol izquierdo. Siguiendo hacia la solución, debemos crear un nodo C y guardar en la pila el sub-árbol derecho que se conectara al nodo C posteriormente.
La pila hasta el momento tendrá estos datos:
Acercándonos un poco mas hacia la solución, el árbol se puede ver así:
Y la pila almacenara la siguiente información:
Obsérvese que siempre que se identifique un sub-árbol derecho, la pila debe ser actualizada. Como ya se acabo la información a distribuir por la izquierda, debemos efectuar un retiro de la pila, con el propósito de seguir el proceso. Efectuando este retiro y sabiendo el nodo al cual debemos conectar el nuevo nodo por la derecha, podemos hacer adecuadamente la inserción del nuevo nodo. El primer elemento de la pila es:
Esto quiere decir que el nodo D se debe conectar a la derecha del nodo L, así:
De la misma manera, el nodo F debe conectarse a la derecha del nodo C. Después de conectar el nodo F, debemos retirar de la pila el último elemento y comenzar a distribuir por la izquierda la nueva informaron. Veamos el arbol hasta este momento:
Y la pila contendrá la siguiente información
Ahora al haber distribuido la rama izquierda (no existe rama izquierda e K ), podemos retirar de la pila su único elemento y crear un nodo J e insertar en la pila su rama derecha, ( no existe rama derecha), así:
Al observar el proceso, vemos que la pila queda vacía y falta adicionar al árbol el nodo H. con esto podemos afirmar que el proceso se debe efectuar mientras la pila no este vacía o exista información para distribuir por la rama izquierda. Por lo tanto el árbol final será:
Existe un buen número de formas para construir una función que efectué el proceso anterior. A continuación presentamos una de estas versiones codificada en lenguaje C.
NOTACIONES INFIJO, POSFIJO Y PREFIJO
Cuando se nos pregunta, por ejemplo, cuanto es el resultado de 5 multiplicado por 8 más 3, la respuesta automática que se da es 43. No se da el caso de que la respuesta dad sea 55. Ahora si pregunta es: cual es la respuesta de 3 mas 5 multiplicado por 8, también volveremos a dar la misma respuesta: 43. No se nos ocurre sumas 3 y 5 luego multiplicar la respuesta por 8 para que nos de 64. Se nos pregunta cual es la respuesta de 5 por 2 mas 8 por 3, la respuesta dada es 34. Nos hemos acostumbrado a través del tiempo a que el operador * tiene mas prioridad que el operador + y así lo trabaja cerebro. La notación con la cual trabajamos los humanos este tipo de expresiones se denomina infijo, donde la presencia de los operadores es:
* /
- +
=
Los humanos trabajamos con notación infijo. De la misma manera los computadores están diseñados para que reconozcan la misma prioridad que reconocemos los humanos. La instrucción:
Resol = 5 * 2 + 8 * 3;
Deja almacenada, por ello, la cifra 34, ya que la asociación automática es:
(result: (5 * 2)+(8 * 3));
Si deseamos que un computador, o un ser humano, calcule:
Resul= 5 * 2 + 8 * 3;
Pero sumando 2 y 8 primero, debemos diseñar la instrucción así:
Result= 5 * (2 + 8) * 3:
Se utilizan los paréntesis para modificar la prioridad de los operadores.
Un programador al indicarle esta instrucción a un computador:
Resul= 5 * 2 + 8 * 3;
Espera la respuesta 34 pero no le interesa como lo hizo la maquina. Internamente, esta operación la ejecuta utilizando una pila. La operación la ejecuta reconociendo objeto a objeto. Vamos a ilustrar la transformación que debe hacer la maquina con el propósito de efectuar la operación anterior. De lo único que esta enterada tanto la maquina como el programador, es que el operador * tiene mas prioridad que el operador +. La transformación que se realiza es convertir la expresión de notación infijo a notación posfijo lo cual se estudiará en el siguiente numeral. A continuación estudiaremos que es la notación posfijo.
La notación posfijo, es otra manera de escribir una expresión aritmética. La notación posfijo, se caracteriza por la ausencia de paréntesis. Esta notación, aunque nunca utiliza paréntesis, es presentada sin ningún tipo de ambigüedad. Veamos su naturaleza. Si tenemos una expresión en notación infijo. Por ejemplo:
a +b
Para escribir esa misma expresión en posfijo. Se debe ejecutar los siguientes pasos:
1. agrupar utilizando paréntesis, de acuerdo a la prioridad de los operadores, así:
(a+b)
2. escribir en posfijo la expresión, así:
ab+
Obsérvese que en la notación posfijo, el operador se escribe después de los operadores . Veamos otro ejemplo:
a + b * c
Agrupando tenemos:
a + ( b * c )
Convirtiendo a posfijo la expresión entre paréntesis resulta:
a + ( b c * )
Ahora tratando la expresión entre paréntesis como un operador tenemos
a ( b c * )+
y destruyendo los paréntesis, nos queda la expresión escrita en posfijo:
a b c * +
Veamos este ejemplo;
( x * y ) + ( v * w )
Primero debemos convertir las expresiones encerradas entre paréntesis a notación posfijo, así:
( x y * ) + ( v w * )
Y luego toda la expresión a notación posfijo, así
x y * v w * +
Veamos estos ejemplos:
1. (a+b)*( c+d) ( a b + ) * ( c d + ) a b + c d + *
2. a+b-c ( a b + ) - c a b + c -
3. (a+b)*(c-d)*e*f ((( a b + ) * ( c d - )) * e ) * f
(( a b + c d - * ) * e ) * f
( a b + c d - * e * ) * f
a b + c d - * e * f *
4. (a+b)*(c/(d-e)+f)-g
( a b + ) * ( c / ( d e - ) + f ) - g
( a b + ) * ( ( cd e - / )+ f ) – g
( a b + ) * ( c d e - / f + ) - g
a b + c d e - / f * g –
5. vamos a suponer que la operación exponenciación esta definida y la representamos así: además, tiene la mayor prioridad de todos los operadores. Veamos estos ejemplos, usando este nuevo operador:
(a b c) (a b) c ab c
6. a b * c – d + e / f/ (g+h) ((a b) * c – d ) + ( e / f ) / ( g+ h )
(ab c * d - ) + ( ef / gh + / )
ab c * d – ef / gh + / +
7. a + ((( b – c ) * ( d – e ) + f ) / g ) (h – j )
a + ((( bc - de - * f + ) / g ) (hj - )
a + (( bc – de - * f + a / hj- )
abc – de - * f + g / hj- +
Existe otro tipo de notación para escribir las expresiones aritméticas. Esta nueva notación recibe el nombre de prefijo y recaracteriza porque los operadores se escriben primero que los operadores. Por ejemplo la expresión:
a+b
Escrita en notación prefijo, sería:
-ab
En general todas las reglas para convertir infijo a posfijo, se aplican para efectuar las conversiones infijo a prefijo, tendiendo en cuenta que los operadores se escriben antes que los operadores. Veamos estos ejemplos:
1. a+b+c (a-b)+ (+ab)+c
++abc
2. a+b-c (a-b)-c (+ab)-c
-+abc
3. (a+b)*(c-d) (+ab)*(-cd)
*+ab-cd
4. a+b/c-d a+(b/c)-d
(a+(/bc))-d
(+a/bc)-d
- + a / bcd
5. a b*c-d+e/f/(g+h)
(((a b) * c ) – d ) + ( e/f ) / (g+h)
( - * abcd) + ( / ef ) / ( + gh)
- * abcd + (//ef + gh)
+ - * abad //ef+gh
Podemos también plantear algunos ejemplos para convertir de posfijo a prefijo o infijo. Veamos primero algunos ejemplos para convertir de posfijo a infijo:
1. ab+
El operador se debe aplicar a los últimos dos operandos, quedando así:
a+b
2. ab+c-
El análisis se comienza por la izquierda de la expresión. Se debe recorrer la expresión hasta que encontremos un operador, así:
ab+c-
Una vez hayamos encontrado el primer operador, debemos aplicar ese operador a los dos últimos operandos que lo precedan, así
(a+b)c-
Y luego debemos seguir analizando la expresión hasta encontrar el próximo operador:
(a+b)c-
Una vez hayamos encontrando el próximo operador debemos aplicar ese operador a los últimos dos operandos. Obsérvese que la expresión encerrada entre paréntesis, se debe trabajar como un solo operando.
(a+b)-c
3. ab+cd-*
Siguiendo el proceso anterior, tenemos:
(a+b)cd-*
(a+b)(c-d)
(a+b)*(c-d)
4. ab+cd-*e*f* (a+b)cd - * e * f *
(a+b)(c-d)e * f *
((a+b)*(c-d)*e) f *
((a+b)*(c-d)*e) * f
(a+b)*(c-d) * e * f
5. ab c (a b)c
(a b)c a b c
6. ab c*d-ef / gh+/+
(a b*c)d-ef / gh + / +
(a b*c-d)ef / gh + / +
(a b* c-d)(e/f) gh + / +
(a b*c-d)(e/f)(g+h) / +
(a b*c-d)((e/f)/(g+h)) +
(a b*c-d)+(e/f)/(g+h)
A b*c-d+e / f / (g+h)
De la misma manera, podemos pasar de la notación prefijo a la notación infijo; veamos un ejemplo
+ab
En este caso debemos analizar la expresión de derecha a izquierda hasta que encontremos el primer operador. Una vez lo hayamos encontramos, aplicamos este operador a los dos operandos que le siguen, así:
a+b
Veamos algunos ejemplos:
1. -+abc -(a+b)c
(a+b)-c a+b-c
2. *+ab - cd * + ab(c-d)
* (a+b) (c-d)
(a+b) * (c-d)
3. -*+abc - de -fg -*+abc – de (f-g)
-*+abc (d-e) (f-g)
-*(a+b)c(d-e)(f-g
-((a+b)*c)(d-e)(f-g)
(((a+b)*c)-(d-e))(f-g)
((a+b)*c-(d-e)) (f-g)
EJERCICIOS
1. cada una de las siguientes expresiones escritas en fijo convertirlas a posfijo
a) (x+y)*(z (s+t)+u)-v
b) a+((x+y)*(w+v)) (i+j)
2. Convertir las expresiones del ejercicio anterior a prefijo
3. Convertir las siguientes expresiones de prefijo a infijo:
a) + - xyz*i**klm
b) ++1-* mno/+pq*rst
4. Convertir las siguientes expresiones en posfijo a infijo
a) pqrst-+ *uv*-
b) lm-n+opq-+
REPRESENTACION DE EXPRESIONES ARITMETICAS EN ÁRBOLES BINARIOS
Una expresión aritmética puede expresarse utilizando un árbol binario. Por ejemplo la expresión:
a+b
Expresada en un árbol binario es:
El operador +aplica a los operandos de la rama izquierda y la rama derecha. La expresión:
a+b*c
Quedara expresada así:
El árbol queda organizado así ya que la expresión implícitamente esta asociada así:
a+(b*c)
Porque por definición el operador * es de mayor jerarquía que el operador +
Vamos a construir un árbol par ala expresión:
a / b * c + d e * f
para defecto esta expresión escrita en infijo, asocia sus operandos así:
(( a / b ) * c ) + (( d e ) * f )
Esto indica que la raíz del árbol contiene el operador+. La rama izquierda contiene la expresión (a / b ) * c y la rama derecha la expresión (d e )*f. siguiendo este orden de ideas el árbol queda construido así:
Existe un método sencillo para construir una árbol que representa un a expresión. El primer paso consiste en transformar la expresión de infijo a prefijo y partiendo de la expresión escrita en prefijo construir el árbol. Veamos algunos ejemplos:
Infijo a+b
Prefijo +ab
Al tener la expresión en prefijo, fácilmente se puede construir el árbol siguiendo este método:
Se insertan nuevos nodos por la izquierda del árbol que hayamos insertado un operando
+a
Luego volvemos hacia atrás en el árbol e insertamos el siguiente elemento a su derecha.
+ab
Si el nodo insertado fue un operador, insertamos el siguiendo a su izquierda. Si el nodo insertado fue un operando, volvemos hacia atrás e insertamos el siguiente nodo a la derecha. Este proceso se continúa hasta que se agote la expresión escrita en prefijo. Veamos otro ejemplo:
Infijo a+(a*c d)
Primero debemos convertir la expresión a prefijo:
+a*b cd
Luego debemos insertar nuevos nodos hasta encontrar un operando:
+a
Luego volvemos hacia atrás e insertamos el siguiente elemento a la derecha:
+a*
Como el último nodo insertado fue un operador, debemos insertar el siguiente a la izquierda:
+a*b
Como el nodo mas reciente insertado fue un operando, volvemos hacia atrás e insertamos el siguiente a la derecha.
+a*b
Como el último nodo insertado fue un operador, debemos insertar el siguiente a la izquierda:
+ a * b c
Como el nodo más reciente insertado fue un operando, volvemos hacia atrás e insertamos el siguiente a la derecha:
+a*b cd
Siguiendo este método, y antes de seguir adelante, se recomienda al lector revisar los árboles para las siguientes expresiones en prefijo:
CONVERSION DE UNA EXPRESION EN UN ARBOL BINARIO A SU REPRESENTACION INFIJO
En este numeral se desarrollara una función que a partir de un árbol binario, genere un arreglo que almacene la expresión en infijo. Antes de entrar propiamente en el desarrollo del problema, estudiaremos algunas propiedades de estos árboles. Supongamos que tenemos en la memoria del computador un árbol así:
Este árbol representa la siguiente expresión
a+b*c
La expresión anterior escrita en prefijo será:
+ a * bc
Si recorremos el árbol en preorden los datos generados serán:
+a*bc
Lo anterior nos permite plantear la primera propiedad:
Si se recorre un árbol en preorden, los datos generados representan la expresión escrita en prefijo.
Si el árbol anterior recorremos en posorden, los datos generados serán:
a b c * +
Estos datos representan la expresión
a + b * c
Escrita en posfijo, lo cual nos permite plantear la segunda propiedad:
Si se recorre un árbol en posorden, los datos generados representan la expresión escrita en posfijo.
Es de esperarse que si recorremos el árbol en inorden, la expresión generada estará escrita automáticamente en infijo. Veamos:
a+b*c
Para el caso que nos ocupa se cumplió la norma. Veamos otro ejemplo:
(a+b) c/d+e
Esta expresión escrita en prefijo será:
+ / + a b c d e
Y en posfijo será:
a b + c d / e +
y el árbol generado será:
Al recorrerlo en preorden, los datos generados serán:
+ / + a b c d e
Al recorrerlo en posorden, los datos generados serán:
a b + c d / e +
Las dos propiedades anteriores se cumplen. Se recorremos el árbol en inorden los datos generados serán:
a + b c / d + e
Pero esta expresión, para su evaluación, se asocia así:
a + ( ( b c ) / d ) + e
Y es bien diferente da la inicial, la cual era:
(a+b) c/d+e
Lo cual nos permite plantear la siguiente propiedad:
Si se recorre un árbol en inorden, los datos generados no representan la expresión escrita en infijo.
Si queremos que de un árbol se genere la correspondiente expresión en infijo no basta con recorrerlo en inorden, además debemos efectuar un proceso que parentice la expresión. Para el ejemplo, el recorrido inorden del árbol es:
a+b c/d+e
Como el operador tiene más prioridad que los demás, y el operador / tiene más prioridad que el +, al tratar de evaluar la expresión esta se asocia así:
a + ( ( b c ) / d ) + e
Debemos diseñar un proceso que genere un arreglo infijo con los siguientes datos:
Lo cual implica que en la medida en que generamos este arreglo debemos ir incluyendo paréntesis donde sea necesario. Veamos la naturaleza del problema:
Como el operador de la raíz aplica a los dos subárboles, gráficamente el árbol anterior lo podemos representar así:
1
2
3
4
Si cada cuadro representa un par de paréntesis, este árbol lo podríamos escribir así:
(rama izquierda )+e
((rama izquierda ) / ) d ) + e
(((rama izquierda ) c ) / d ) + e
((((rama izquierda) + b) c ) / d ) +e
((( a ) + b) c ) / d + e
Ahora retiramos los paréntesis innecesarios, debidos a la jerarquía de los operadores, tendremos la expresión:
((( a +b) c ) / d ) + e
No podemos retirar los paréntesis que encierran la expresión (a+b), debido a que se cambia la expresión ya que el operador es de mayor prioridad que el operador +. Los paréntesis ya encierran la expresión (a+b) c si se puede retirar, debido a que el operador es de mayor jerarquía que el operador /
((a+b) c/d)+e
Los paréntesis que encierran la expresión (a+b) c / d pueden ser retirados ya que el operador + es el de al mínima jerarquía. Con la cual la expresión debidamente patentizada es:
Veamos otro ejemplo:
Si recorremos el árbol en inorden, los resultados serán:
a + b c
Lo cual es diferente a la expresión que esta representada en el árbol.
(a+ b ) c
Si el árbol es:
Al recorrerlo en inorden los resultados son:
a b+c
y no existe la necesidad de insertar paréntesis en la expresión. La diferencia, en este caso particular, radica en que si el operador padre tiene más jerarquía que el operador hijo, debemos patentizar la rama izquierda o derecha del árbol. Observemos los siguientes árboles:
Para el árbol la expresión será:
(a+b) c
Debe patentizarse. El operador tiene mas jerarquía que el operador +
Para el árbol la expresión será:
a b+c
no se necesitan paréntesis. El operador + tiene menos jerarquía que el operador
Para el árbol la expresión será:
(a-b)-c
Para esta expresión., no son necesarios los paréntesis ya que sin ellos la asociación se haría de la misma manera. Veamos este caso.
Para este caso al recorrer el árbol en inorden, se genera la siguiente expresión:
c – a – b
Se deben insertar paréntesis ya que es muy diferente la expresión que está representada en el árbol:
c – (a - b )
Ahora debemos puntualizar en que momento se necesitan insertar paréntesis.
La respuesta es muy sencilla. Veamos este ejemplo
Al recorrer el árbol en inorden, el resultado será:
a+b-c d+e*f
Debemos insertar paréntesis a la expresión a+b-c y también a la expresión d+e*f. al final arreglo infijo quedara así:
( a + b – c ) ((d + e ) * f )
Como puede identificarse esta situación. Obsérvese que si existen dos nodos cuya relación es padre-hijo y los dos contienen operadores, debemos abrir un paréntesis si el operador hijo tiene menos prioridad que el operador padre. Este paréntesis que se abre debe existir siempre y cuando el padre tenga más jerarquía que el hijo y asea izquierdo o derecho. Para insertar un paréntesis son necesarias tres condiciones:
1. que el nodo contenga un operador.
2. que su hijo (izquierdo o derecho) contenga también un operador.
3. que el nodo padre sea un operador de mayor jerarquía que el nodo hijo.
Si estas tres condiciones se cumplen debemos abrir un paréntesis. Este paréntesis, guardaremos en algún lugar el paréntesis que cierra para que en su momento, se incorpore al arreglo infijo. Para la solución a este problema debe servirnos una pila ya que el proceso se asimila a escribir un árbol en inorden, con la salvedad de que bajo las tres condiciones expuestas anteriormente, debemos insertar un paréntesis a la pila.
ÁRBOLES BINARIOS
En la vida cotidiana, muchas vedes sin saberlo, trabajamos en ocasiones con los árboles. Por ejemplo: árboles genealógicos, organigramas, directorios en los discos de un computador, etc. Cada uno de estos conceptos representa un árbol.
ORGANIGRAMA DE UNA EMPRESA
ORGANIZACIOND E UN DIRECTORIO EN UN COMPUTADOR
3.1.DEFINICIONES
En el área de la computación también se conoce una materia que trata de los árboles. Este tema es muy extenso y para su estudio vamos a dividirlo en varios capítulos.
En este capitulo nos vamos a circunscribir solamente en el estudio de los árboles binarios. Este tipo de árbol se caracteriza porque tiene un vértice principal y de él se desprende dos ramas. La rama izquierda y la rama derecha.
La rama izquierda y la derecha, también son dos árboles binarios. El vértice principal se denomina raíz y cada una de las ramas se denomina árbol izquierdo y árbol derecho. Por ejemplo:
La raíz de este árbol es A y el árbol izquierdo esta conformado por otro árbol.
Que a su vez tiene como raíz B. el árbol derecho esta conformado también por otro árbol.
DEFINICIONES
NODO
Un árbol binario es un conjunto de elementos cada uno de los cuales se denomina nodo. Un árbol binario puede tener cero nodos y en este se dice que esta vació. Puede tener un solo nodo, y en este caso existe solamente la raíz del árbol o puede tener un número finito de nodos. Cada nodo que esta ramificado por la izquierda o por la derecha o puede no tener ninguna ramificación. La anatomía de un nodo en un árbol binario es la siguiente:
Información del nodo
Apuntador al árbol de la derecha
Apuntador al árbol de la izquierda
Raíz en un árbol binario se pueden distinguir la raíz principal y las raíces de los demás subárboles. Por ejemplo:
La raíz principal es el nodo cuya información es A. podemos distinguir también el árbol.
Cuya raíz es el nodo con información D. Este nodo es la raíz del árbol de la derecha. El Árbol de la izquierda
Tiene como raíz el nodo cuya información es B y tiene solamente una ramificación.
PADRE
Un padre es un nodo que puede o no tener ramificaciones. Por ejemplo:
Caso 1 caso 2 caso3
En los tres casos el nodo A es un padre. En el caso 1 es un padre que no tiene hijos. En el caso 2, el nodo A es el padre del nodo B. en el caso 3 el nodo A es padre de los nodos By C peo no es padre del nodo D.
HIJO
Nos referimos al ejemplo anterior. En el caso 1 el nodo A no tiene hijos. En el caso 2, B es un hijo del nodo A y en el caso 3, D es hijo de B y el padre de B es el nodo A
HERMANO
Nos referimos al caso 3 del ejemplo anterior. Los hermanos son los hijos de un mismo padre. Los nodos B y C son hermanos. El nodo D no tiene hermanos
HOJA
Una hoja es un nodo que no tiene ramificaciones. Por ejemplo
El nodo C es una hoja mientras que el nodo B no se puede considerar como hoja porque tiene una ramificación por la derecha. El nodo D también es una hoja
NODO NO TERMINAL
Un nodo no Terminal es aquel que posee por lo menos una ramificación. En el ejemplo anterior, el nodo A o el B son nodos no terminales, mientras el nodo D o el nodo C son nodos terminales.
CAMINO
Un árbol siempre se examina hacia abajo. Por ejemplo:
Al nodo C podemos llegar desde el nodo B. Nunca se puede examinar el nodo B a partir del nodo C. Los apuntadores derecho o izquierdo de cualquier nodo apuntan al árbol derecho o izquierdo que siguen a ese nodo. Nunca apuntan a los nodos precedentes. Un camino es el conjunto de nodos que tenemos que visitar con el propósito de llegar a un nodo específico. Por ejemplo para llegar al nodo F es necesario recorrer el camino
A D F
Del mismo nodo, para llegar al nodo G debemos recorrer el camino
A D E G
Obsérvese que los caminos se configuran siempre hacia abajo. Nunca se puede hablar de un camino para llegar al nodo C así:
G E D A B C
Este camino se puede configurar.
LONGITUD
Longitud es el número de nodos que se deben recorrer para pasar de un nodo a otro. Por ejemplo:
La longitud entre A y E es 3. La longitud entre G y G es 0. La longitud entre A y B es 1 Obsérvese que no podemos calcular la longitud entre B y G ya que el camino B A G no existe.
DESCENDIENTE
El nodo C es descendiente del nodo A si a partir de A podemos llegar a C a través de un camino. Por ejemplo:
El nodo C es descendiente de A ya que a C podemos llagar por el camino
A B C
Siempre que exista un camino para llegar de un nodo V a un nodo X, el nodo X es un descendiente de V. pAra el ejemplo anterior, el nodo E es descendiente de D pero el nodo no es descendiente de B
ANCESTRO
El nodo A es un ancestro del nodo C si existe un camino entre A y C. basándonos en el ejemplo anterior. A es un ancestro de C ya que existe un camino entre los nodos. No se puede hablar de que D sea ancestro de ya que el camino D A B no existe
NIVEL
Cada nodo tiene un nivel dentro de un árbol binario. Por definición el nodo raíz tiene un nivel y de los demás nodos tienen el nivel de su padre más 1. Por esto los nodos que son hijos del nodo raíz tienen un nivel 1. Veamos este ejemplo
NIVEL 0
NIVEL 1
NIVEL 2
NIVEL 3
Los nodos A, M y S tienen un nivel 0 en tanto que los nodos G y V tienen un nivel 3. Obsérvese que le nivel del nodo G es la longitud del camino desde la raíz hasta el nodo.
GRADO DE UN NODO
El grado de un nodo es el número de hijos. Por ejemplo el grado del nodo A es 2, el grado del nodo T es 1. El grado de un nodo Terminal siempre es 0.en los árboles binarios, el grado de un nodo fluctúa entre 0 y 2. Existen otros tipos de árboles, (árbol n_ario), en los cuales esta restricción no existe. Estos arboles serán estudiados en el segundo tomo de este libro
ALTURA
La altura de un árbol binario es el nivel de la hoja o de las hojas que están más distantes de la raíz. Basándonos en el ejemplo anterior, la altura del árbol cuya raíz es A, corresponde a la longitud del camino para llegar a la hoja más distante de la raíz. En este caso será 3. La altura cuya raíz es M, corresponde al nivel de la hoja P.
ARBOL BINARIO COMPLETO
Un árbol binario completo es aquel en el que todo nodo no Terminal tiene sus dos hijos. El siguiente es un árbol binario de nivel 3:
NIVEL 0
NIVEL 1
NIVEL 2
NIVEL 3
Obsérvese que todos los nodos no terminales tienen sus dos hijos. El máximo número de nodos que puede tener un árbol de nivel n es:
20 + 21 + 22 + 23….+ 2n
Si n es 3 entonces
20 + 21 + 22 + 23 =15
Este árbol es un árbol binario completo de nivel 3 y este es el máximo número de nodos que puede tener un árbol de nivel 3.
ARBOL BINARIO IGUAL
Dos árboles son iguales si los dos son vacíos. Existe otro caso ene. Cual dos árboles son iguales:
Estos árboles son iguales porque sus raíces son iguales y también lo son su respectivo árbol izquierdo y derecho. Para que un árbol sea igual a otro, es necesario que el contenido de cada uno de sus respectivos nodos sea el mismo y que legan las mismas relaciones de parentesco. Por ejemplo los siguientes árboles
Son diferentes porque el contenido de sus respectivos nodos es diferente. Obsérvese que sus nodos tienen las mismas relaciones de parentesco.
ARBOL BINARIO SEMEJANTE
Dos árboles son semejantes si tienen el mismo número de nodos y los valores de los nodos del primer árbol son los mismos que los valores de los nodos del segundo, sin importar la relación de parentesco entre ellos. Por ejemplo:
Estos árboles son semejantes. Contienen los mismos valores en cada uno de sus nodos.
ARBOL BINARIO ISOMORFO
Dos árboles binarios son isomorfos si tienen la misma estructura aunque el contenido de cada uno e sus nodos sea diferente. Por ejemplo los siguientes árboles son isomorfos.
PESO
El peso de un árbol en un nodo dado es el número de nodos en el árbol sin contarse el mismo. Por ejemplo:
El peso del árbol cuya raíz es A corresponde al número de nodos de ese árbol: los nodos Q,C y R tienen un peso de 2
FORMAS DE RECORRER UN ARBOL BINARIO
Universalmente existen 3 formas de recorrer un árbol binario:
Preorden
Inorden
Posorden
Si logramos construir un árbol como este:
Podemos extraer sus datos de 3 maneras. Veamos cada una. Recorrer un árbol en preorden consiste en:
Examinar el ato del nodo raíz
Recorrer el árbol izquierdo en preorden
Recorrer el árbol derecho en preorden
Si deseamos recorrer todo el árbol, evidentemente debemos comenzar por el nodo raíz. Este método exige examinar primero el nodo raíz debemos entender como examinar un nodo, el hecho de efectuar sobre su información cualquier acción: por ejemplo escribirla, efectuar alguna operación matemática sobre ella o con ella, modificarla. También en la gran mayoría de los textos de estructuras de información, se utiliza el termino visitar un nodo. Entre la palabra examinar y la palabra visitar existe una diferencia. Examinar un nodo es revisar su contenido y eventualmente modificarlo en tanto que visitar un nodo es utilizar la dirección de ese nodo con el propósito de seguir explorando el árbol hacia abajo. Si deseamos recorrer un árbol en preorden, con el propósito de escribir su contenido, debemos examinar el contenido de cada uno se sus nodos, mientras si deseamos contar sus nodos, es necesario visitar cada nodo.
Supongamos que deseamos escribir un árbol en preorden. Para hacerlo, se debe examinar el nodo raíz y luego recorrer el árbol de la izquierda en preorden.
ARBOL A LA IZQUIERDA DE A
Recorrer este árbol en preorden es examinar su nodo raíz y recorrer de nuevo el árbol de la izquierda preorden.
ARBOL A LA IZQUIERDA DE B
Recorrer este árbol en preorden es examinar su nodo raíz. Como ya no existen nodos por la izquierda, debemos empezar a recorrer el árbol D por la derecha. Como ya no existen nodos por la derecha, debemos recorrer el árbol.
Por la derecha. El árbol de la derecha lo debemos recorrer también en preorden.
ARBOL A LA DERECHA DE B
Recorrer este árbol en preorden, es examinar su nodo raíz y recorrer el árbol por la izquierda en preorden y luego recorrerlo por la derecha. Como no existen árboles ni por la izquierda ni por la derecha, debemos recorrer el árbol.
En preorden. El orden en el cual debemos examinar estos nodos es: primero el nodo C, luego F y luego G. por lo tanto al imprimir el árbol anterior en preorden, los resultados deben ser:
A B D E C F G
Antes de seguir adelante, el lector debe certificar que el árbol:
Al imprimirlo recorriéndolo en Preorden debe generar los siguientes resultados:
10 5 3 1 4 7 9 15 14 17 16 20
Ahora veamos la segunda forma de recorrer un árbol binario. Recorrer un árbol en inorden, consiste en:
Recorrer el árbol izquierdo en inorden
Examinar la raíz
Recorrer el árbol derecho en inorden.
Por ejemplo:
Si queremos imprimir este árbol en inorden, debemos primero recorrer el árbol izquierdo en inorden:
Al tratar de recorrer este árbol en inorden y no existe árbol por su izquierda debemos examinar el nodo y luego recorrer el árbol de su derecha. Al no existir árbol por su derecha, entonces el árbol a la izquierda del nodo A ha sido totalmente recorrido. Siguiendo con las normas establecidas inicialmente, debemos examinar el nodo A y luego recorrer el árbol a la derecha del nodo A
ARBOL DERECHO DE A
Para recorrer este árbol en inorden primero debemos recorrer el árbol izquierdo. Al no existir árbol izquierdo, se debe examinar este nodo y luego recorrer el árbol derecho. Al no existir árbol derecho, el árbol ya ha sido recorrido en su totalidad. Por lo tanto los datos impresos serán:
B A C
Observemos este otro ejemplo
Debemos recorrer en inorden el árbol a la izquierda de la raíz:
Al recorrer este árbol en inorden ya sabemos, de acuerdo a la explicación del ejemplo anterior, que los resultados son:
3 5 7
Al terminar de recorrer el árbol a la izquierda de la raíz, debemos examinar la raíz y luego recorrer en inorden el árbol a la derecha de la raíz
Sabemos que al recorrer este árbol en inorden, los resultados son:
11 12 15
Con lo cual al examinar todo el árbol en inorden, los datos impresos serán:
3 5 7 10 11 12 15
Se invita al lector a certificar que al recorrer el siguiente árbol binario en inorden los resultados son:
H D I B E A J F C K G L
Veamos el árbol
Por ultimo estudiemos la tercera forma de recorrer un árbol binario. Examinar un árbol binario en posorden consiste en:
Recorrer el árbol izquierdo posorden
Recorrer el árbol derecho en posorden
Examinar la raíz.
Veamos un ejemplo:
Al recorrer el árbol izquierdo en posorden, el único dato impreso será B. después de haber recorrido todo el árbol de la izquierda en posorden, se debe recorrer todo el árbol de la derecha en posorden. Al recorrer el árbol de la derecha en posorden, el único dato impreso será C. una vez recorridos los árboles izquierdo y derecho, debemos examinar la raíz. Según esto los datos impresos serán.
B C A
Ejercicios
1. Elaborar un programa que cree en la memoria del computador el siguiente árbol binario:
2. Dado el siguiente árbol binario:
Certificar que al recorrer el árbol, los siguientes resultados son correctos:
Preorden ABCDFGEIJ
Inorden BAFDGCIEJ
Posorden BFGDIJECA
3. Suponga que en memorial del computador existe el siguiente árbol:
Escriba un conjunto de instrucciones que cree un nodo X a la derecha de B y un nodo Y a la derecha de E.
4. dado el siguiente árbol: raíz
Cuales serian los datos impresos si se recorre en:
Preorden
Inorden
Posorden
MANTENIMIENTO DE UN CONJUNTO DE NUMEROS CLASIFICADOS ASCENDENTEMENTE, UTILIZANDO UN ARBOL BINARIO ORDENADO.
Utilizando un árbol binario, es posible mantener un conjunto de números clasificados ascendentemente sin necesidad de rutinas de ordenamiento. Se plantea el problema de leer un conjunto de enteros y listarlos clasificados ascendentemente.
Los números repetidos deben ser rechazados. Por ejemplo si la entrada es:
87 25 23 25 48 8 92
El programa debe generar los siguientes resultados:
8 23 25 48 87 92
Este problema se puede resolver fácilmente utilizando un árbol binario ordenado. Solamente es necesario ir leyendo cifra por cifra e ir adicionándola en el árbol así: si es menor al contenido del nodo analizado la instemos por la izquierda de ese nodo y se es mayor por la derecha. Veamos: al leer el número 87, creamos con este dato el nodo raíz. Luego al leer el 25, como 25 es menor que 87, creamos un nuevo nodo a la izquierda de 87. Visualmente el árbol creado hasta el momento sería:
Luego al leer el número 23, como este dato es menor a 87, nos debemos desplazar hacia abajo por la izquierda. Al llegar al 25, debemos crear un nuevo nodo a la izquierda por el hecho de que 23 es menor que 25, así:
Al leer el siguiente dato este debe ser rechazado porque ya existe en el árbol. Al leer el 48, debemos desplazarnos por la izquierda y al compararlo con 25, se debe crear un nuevo nodo a la derecha del 25, así:
Siguiendo este mismo procedimiento, enumero 8 debe insertarse a la izquierda del 23 así
Por ultimo al leer el numero 92 este debe insertarse a la derecha del 87. Los datos en el. Árbol quedan, finalmente, distribuidos así:
Si imprimimos el contenido del árbol, recorriéndolo en inorden. Tendremos la lista pedida:
8 23 25 48 87 92
IMPRESIÓN DE UN ARBOL EN INORDEN
Observemos el siguiente árbol:
Raíz
Al escribir este árbol en inorden los resultados serán:
3 5 6 7 8 10 15 20
Observando el proceso, lo primero que se escribe siempre es el contenido del nodo de la extrema izquierda del árbol. Luego debemos escribir el contenido del nodo padre para luego escribir en inorden el árbol de la derecha.
IMPRESIÓN DE UN ARBOL EN PREORDEN USANDO UNA PILA
Deseamos escribir un árbol en preorden. Veamos esta estructura:
R
A
G
B I
E
H
D F J
La función que vamos a elaborar debe escribir:
100 50 30 10 40 60 65 150 120 160 180
Esta nueva función se diferencia de a función inorden ( ), en que en aquella primero se recorría el árbol izquierdo y luego si se escribía el contenido del padre de ese árbol. En esta nueva rutina primero se debe escribir el contenido del padre del árbol y luego se recorrer en preorden la rama izquierda.
El siguiente paso consiste en retirar de la pila la dirección C y determinar si existe un árbol por la derecha del nodo indicado por C. siguiendo el comportamiento de la pila, podemos por esto, deducir que esta función es muy parecida a la función inorden ( ). La diferencia radica en que antes de analizar el árbol izquierdo, la información del nodo ya ha sido escrita. Veamos el comportamiento del proceso:
Contenido la pila numero escrito
100
50
30
10
-
-
40
-
60
65
-
-
150
120
-
180
-
IMPRESIÓN DE UN ARBOL EN POSORDEN USANSO UNA PILA
La impresión de un árbol en posorden, es un poco más compleja y requiere de modificaciones en el manejo de la pila Veamos este árbol:
La impresión en posorden es:
3 7 5 20 40 30 10
Antes de imprimir el nodo, debemos recorrer el árbol izquierdo y luego el derecho. Es claro que primero debemos llegar hasta la hoja de la extrema izquierda del árbol, guardando los apuntes en una pila para luego poder recuperar las direcciones de todos los ancestros de esa hoja. Se llegamos a la hoja:
Antes de escribir el contenido del nodo debemos certificar que ya han sido recorridos en posorden los árboles izquierdo y derecho.
IMPRESIÓN DE UN ARBOL POR NIVELES USANDO UNA COLA
Imprimir un árbol por niveles, es imprimir primero su raíz, luego los contenidos de los nodos del nivel 1, luego los contenidos de los nodos del nivel 2, y así sucesivamente hasta imprimir el contenido de los nodos del ultimo nivel. Por ejemplo:
Al imprimir este árbol por niveles, los resultados serán:
20 10 30 5 15 25 40 7 50
Aprovechando una estructura FIFO, podemos efectuar esta impresión sin ningún problema.
Al comenzar almacenamos en una cola la dirección del nodo raíz:
Ahora mientras la cola no este vacía, retiramos el primer elemento de la cola y escribimos el contenido de la dirección del elemento retirado e insertamos en la cola las direcciones izquierda y derecha almacenadas en el contenido de la dirección retirada de la cola
Siguiendo este mismo procedimiento, tendríamos los siguientes estados de la cola:
10
30
5
15
25
40
7
50
Revisando el proceso anterior, observamos dos cosas: la primera es que cuando un apuntador es NULL, a la cola no se adiciona ningún elemento y la segunda es que este proceso repetitivo se debe efectuar mientras la cola no esté vacía.
RECONSTRUCCION DE UNA RBOL BINARIO
Se plantea el problema de reconstruir un árbol binario dados sus recorridos en preorden y en inorden. Por ejemplo, si un árbol genera lo siguiente: al recorrerse en preorden:
G E A I B M C L D F K J H
Y genera lo siguiente al recorrerse en inorden:
I A B E G L D C F M K H J
Se requiere de un programa que a partir de estos datos, genere un árbol binario al cual correspondan las dos impresiones. Vamos a considerar que a la función que elabora este trabajo entran dos arreglos. El método es muy sencillo y consiste en utilizar una estructura LIFO como la herramienta fundamental. Lo más sencillo del proceso es determinar la raíz del árbol. Para el caso que nos ocupa la raíz será:
Vamos a utilizar los apuntadores p y q como auxiliares de trabajo.
Pre G E A I B M C L D F K J H
In I A B E G L D C F M K H J
Si se recorre este árbol en Preorden, el primer nodo que visita es G y al recorrerlo en inorden el nodo del extremo izquierdo es I. en este lugar podemos afirmar que los nodos EAIB, forman el sub.-árbol izquierdo de G y los nodos MCLDFKJH el sub.-árbol derecho q
Raíz p
El problema esta dividido en dos. Ya sabemos que la raíz es G y también sabemos los componentes de la izquierda y de la derecha. Ahora podemos guardar en una pila los componentes del árbol derecho y seguir trabajando sobre el árbol izquierdo. Es decir tratar de organizar el árbol izquierdo.
La pila quedara así:
Vamos a considerar la G del recuadro como un apuntador que esta en la pila que nos indica la dirección del nodo padre de este sub.-árbol derecho. Ahora debemos seguir trabajando con el sub.-árbol izquierdo.
EAIB
IABE
De la misma forma, el nodo raíz de este nuevo árbol es E. este nodo debe conectarse al nodo G así
Q
El apuntador que siempre debe estar dirigido al nodo al cual se conectara el nuevo nodo posteriormente. Siempre el nuevo nodo será indicado por el apuntador p. con lo anterior el árbol estará organizado así:
Obsérvese con cuidado porque el nodo E no tiene sub-árbol derecho. Siguiendo el mismo orden, debemos crear un nodo A, el cual conectara por la izquierda con E y este nodo si tendrá sub- árbol por la derecha, así:
Como siempre que aparezca un sub-árbol derecho debemos actualizar la pila , su nueva información será:
Siguiendo por la izquierda, ahora podemos conectar el nodo I, quedando el árbol así:
En este lugar debemos efectuar un retiro de la pila y conectar el nuevo nodo por la dercha del nodo indicado por el apuntador que estaba almacenando en el primer elemento de la pila.
Con esto, el arbol queda así:
Y la pila contendrá solamente un elemento. Como ya se distribuyo la información el árbol izquierdo, debemos retirar de la pila el elemento y conectar por la derecha un nuevo nodo M, quedando el árbol así:
La nueva información de la pila será.
Y continuamos trabajando con el árbol izquierdo. Siguiendo hacia la solución, debemos crear un nodo C y guardar en la pila el sub-árbol derecho que se conectara al nodo C posteriormente.
La pila hasta el momento tendrá estos datos:
Acercándonos un poco mas hacia la solución, el árbol se puede ver así:
Y la pila almacenara la siguiente información:
Obsérvese que siempre que se identifique un sub-árbol derecho, la pila debe ser actualizada. Como ya se acabo la información a distribuir por la izquierda, debemos efectuar un retiro de la pila, con el propósito de seguir el proceso. Efectuando este retiro y sabiendo el nodo al cual debemos conectar el nuevo nodo por la derecha, podemos hacer adecuadamente la inserción del nuevo nodo. El primer elemento de la pila es:
Esto quiere decir que el nodo D se debe conectar a la derecha del nodo L, así:
De la misma manera, el nodo F debe conectarse a la derecha del nodo C. Después de conectar el nodo F, debemos retirar de la pila el último elemento y comenzar a distribuir por la izquierda la nueva informaron. Veamos el arbol hasta este momento:
Y la pila contendrá la siguiente información
Ahora al haber distribuido la rama izquierda (no existe rama izquierda e K ), podemos retirar de la pila su único elemento y crear un nodo J e insertar en la pila su rama derecha, ( no existe rama derecha), así:
Al observar el proceso, vemos que la pila queda vacía y falta adicionar al árbol el nodo H. con esto podemos afirmar que el proceso se debe efectuar mientras la pila no este vacía o exista información para distribuir por la rama izquierda. Por lo tanto el árbol final será:
Existe un buen número de formas para construir una función que efectué el proceso anterior. A continuación presentamos una de estas versiones codificada en lenguaje C.
NOTACIONES INFIJO, POSFIJO Y PREFIJO
Cuando se nos pregunta, por ejemplo, cuanto es el resultado de 5 multiplicado por 8 más 3, la respuesta automática que se da es 43. No se da el caso de que la respuesta dad sea 55. Ahora si pregunta es: cual es la respuesta de 3 mas 5 multiplicado por 8, también volveremos a dar la misma respuesta: 43. No se nos ocurre sumas 3 y 5 luego multiplicar la respuesta por 8 para que nos de 64. Se nos pregunta cual es la respuesta de 5 por 2 mas 8 por 3, la respuesta dada es 34. Nos hemos acostumbrado a través del tiempo a que el operador * tiene mas prioridad que el operador + y así lo trabaja cerebro. La notación con la cual trabajamos los humanos este tipo de expresiones se denomina infijo, donde la presencia de los operadores es:
* /
- +
=
Los humanos trabajamos con notación infijo. De la misma manera los computadores están diseñados para que reconozcan la misma prioridad que reconocemos los humanos. La instrucción:
Resol = 5 * 2 + 8 * 3;
Deja almacenada, por ello, la cifra 34, ya que la asociación automática es:
(result: (5 * 2)+(8 * 3));
Si deseamos que un computador, o un ser humano, calcule:
Resul= 5 * 2 + 8 * 3;
Pero sumando 2 y 8 primero, debemos diseñar la instrucción así:
Result= 5 * (2 + 8) * 3:
Se utilizan los paréntesis para modificar la prioridad de los operadores.
Un programador al indicarle esta instrucción a un computador:
Resul= 5 * 2 + 8 * 3;
Espera la respuesta 34 pero no le interesa como lo hizo la maquina. Internamente, esta operación la ejecuta utilizando una pila. La operación la ejecuta reconociendo objeto a objeto. Vamos a ilustrar la transformación que debe hacer la maquina con el propósito de efectuar la operación anterior. De lo único que esta enterada tanto la maquina como el programador, es que el operador * tiene mas prioridad que el operador +. La transformación que se realiza es convertir la expresión de notación infijo a notación posfijo lo cual se estudiará en el siguiente numeral. A continuación estudiaremos que es la notación posfijo.
La notación posfijo, es otra manera de escribir una expresión aritmética. La notación posfijo, se caracteriza por la ausencia de paréntesis. Esta notación, aunque nunca utiliza paréntesis, es presentada sin ningún tipo de ambigüedad. Veamos su naturaleza. Si tenemos una expresión en notación infijo. Por ejemplo:
a +b
Para escribir esa misma expresión en posfijo. Se debe ejecutar los siguientes pasos:
1. agrupar utilizando paréntesis, de acuerdo a la prioridad de los operadores, así:
(a+b)
2. escribir en posfijo la expresión, así:
ab+
Obsérvese que en la notación posfijo, el operador se escribe después de los operadores . Veamos otro ejemplo:
a + b * c
Agrupando tenemos:
a + ( b * c )
Convirtiendo a posfijo la expresión entre paréntesis resulta:
a + ( b c * )
Ahora tratando la expresión entre paréntesis como un operador tenemos
a ( b c * )+
y destruyendo los paréntesis, nos queda la expresión escrita en posfijo:
a b c * +
Veamos este ejemplo;
( x * y ) + ( v * w )
Primero debemos convertir las expresiones encerradas entre paréntesis a notación posfijo, así:
( x y * ) + ( v w * )
Y luego toda la expresión a notación posfijo, así
x y * v w * +
Veamos estos ejemplos:
1. (a+b)*( c+d) ( a b + ) * ( c d + ) a b + c d + *
2. a+b-c ( a b + ) - c a b + c -
3. (a+b)*(c-d)*e*f ((( a b + ) * ( c d - )) * e ) * f
(( a b + c d - * ) * e ) * f
( a b + c d - * e * ) * f
a b + c d - * e * f *
4. (a+b)*(c/(d-e)+f)-g
( a b + ) * ( c / ( d e - ) + f ) - g
( a b + ) * ( ( cd e - / )+ f ) – g
( a b + ) * ( c d e - / f + ) - g
a b + c d e - / f * g –
5. vamos a suponer que la operación exponenciación esta definida y la representamos así: además, tiene la mayor prioridad de todos los operadores. Veamos estos ejemplos, usando este nuevo operador:
(a b c) (a b) c ab c
6. a b * c – d + e / f/ (g+h) ((a b) * c – d ) + ( e / f ) / ( g+ h )
(ab c * d - ) + ( ef / gh + / )
ab c * d – ef / gh + / +
7. a + ((( b – c ) * ( d – e ) + f ) / g ) (h – j )
a + ((( bc - de - * f + ) / g ) (hj - )
a + (( bc – de - * f + a / hj- )
abc – de - * f + g / hj- +
Existe otro tipo de notación para escribir las expresiones aritméticas. Esta nueva notación recibe el nombre de prefijo y recaracteriza porque los operadores se escriben primero que los operadores. Por ejemplo la expresión:
a+b
Escrita en notación prefijo, sería:
-ab
En general todas las reglas para convertir infijo a posfijo, se aplican para efectuar las conversiones infijo a prefijo, tendiendo en cuenta que los operadores se escriben antes que los operadores. Veamos estos ejemplos:
1. a+b+c (a-b)+ (+ab)+c
++abc
2. a+b-c (a-b)-c (+ab)-c
-+abc
3. (a+b)*(c-d) (+ab)*(-cd)
*+ab-cd
4. a+b/c-d a+(b/c)-d
(a+(/bc))-d
(+a/bc)-d
- + a / bcd
5. a b*c-d+e/f/(g+h)
(((a b) * c ) – d ) + ( e/f ) / (g+h)
( - * abcd) + ( / ef ) / ( + gh)
- * abcd + (//ef + gh)
+ - * abad //ef+gh
Podemos también plantear algunos ejemplos para convertir de posfijo a prefijo o infijo. Veamos primero algunos ejemplos para convertir de posfijo a infijo:
1. ab+
El operador se debe aplicar a los últimos dos operandos, quedando así:
a+b
2. ab+c-
El análisis se comienza por la izquierda de la expresión. Se debe recorrer la expresión hasta que encontremos un operador, así:
ab+c-
Una vez hayamos encontrado el primer operador, debemos aplicar ese operador a los dos últimos operandos que lo precedan, así
(a+b)c-
Y luego debemos seguir analizando la expresión hasta encontrar el próximo operador:
(a+b)c-
Una vez hayamos encontrando el próximo operador debemos aplicar ese operador a los últimos dos operandos. Obsérvese que la expresión encerrada entre paréntesis, se debe trabajar como un solo operando.
(a+b)-c
3. ab+cd-*
Siguiendo el proceso anterior, tenemos:
(a+b)cd-*
(a+b)(c-d)
(a+b)*(c-d)
4. ab+cd-*e*f* (a+b)cd - * e * f *
(a+b)(c-d)e * f *
((a+b)*(c-d)*e) f *
((a+b)*(c-d)*e) * f
(a+b)*(c-d) * e * f
5. ab c (a b)c
(a b)c a b c
6. ab c*d-ef / gh+/+
(a b*c)d-ef / gh + / +
(a b*c-d)ef / gh + / +
(a b* c-d)(e/f) gh + / +
(a b*c-d)(e/f)(g+h) / +
(a b*c-d)((e/f)/(g+h)) +
(a b*c-d)+(e/f)/(g+h)
A b*c-d+e / f / (g+h)
De la misma manera, podemos pasar de la notación prefijo a la notación infijo; veamos un ejemplo
+ab
En este caso debemos analizar la expresión de derecha a izquierda hasta que encontremos el primer operador. Una vez lo hayamos encontramos, aplicamos este operador a los dos operandos que le siguen, así:
a+b
Veamos algunos ejemplos:
1. -+abc -(a+b)c
(a+b)-c a+b-c
2. *+ab - cd * + ab(c-d)
* (a+b) (c-d)
(a+b) * (c-d)
3. -*+abc - de -fg -*+abc – de (f-g)
-*+abc (d-e) (f-g)
-*(a+b)c(d-e)(f-g
-((a+b)*c)(d-e)(f-g)
(((a+b)*c)-(d-e))(f-g)
((a+b)*c-(d-e)) (f-g)
EJERCICIOS
1. cada una de las siguientes expresiones escritas en fijo convertirlas a posfijo
a) (x+y)*(z (s+t)+u)-v
b) a+((x+y)*(w+v)) (i+j)
2. Convertir las expresiones del ejercicio anterior a prefijo
3. Convertir las siguientes expresiones de prefijo a infijo:
a) + - xyz*i**klm
b) ++1-* mno/+pq*rst
4. Convertir las siguientes expresiones en posfijo a infijo
a) pqrst-+ *uv*-
b) lm-n+opq-+
REPRESENTACION DE EXPRESIONES ARITMETICAS EN ÁRBOLES BINARIOS
Una expresión aritmética puede expresarse utilizando un árbol binario. Por ejemplo la expresión:
a+b
Expresada en un árbol binario es:
El operador +aplica a los operandos de la rama izquierda y la rama derecha. La expresión:
a+b*c
Quedara expresada así:
El árbol queda organizado así ya que la expresión implícitamente esta asociada así:
a+(b*c)
Porque por definición el operador * es de mayor jerarquía que el operador +
Vamos a construir un árbol par ala expresión:
a / b * c + d e * f
para defecto esta expresión escrita en infijo, asocia sus operandos así:
(( a / b ) * c ) + (( d e ) * f )
Esto indica que la raíz del árbol contiene el operador+. La rama izquierda contiene la expresión (a / b ) * c y la rama derecha la expresión (d e )*f. siguiendo este orden de ideas el árbol queda construido así:
Existe un método sencillo para construir una árbol que representa un a expresión. El primer paso consiste en transformar la expresión de infijo a prefijo y partiendo de la expresión escrita en prefijo construir el árbol. Veamos algunos ejemplos:
Infijo a+b
Prefijo +ab
Al tener la expresión en prefijo, fácilmente se puede construir el árbol siguiendo este método:
Se insertan nuevos nodos por la izquierda del árbol que hayamos insertado un operando
+a
Luego volvemos hacia atrás en el árbol e insertamos el siguiente elemento a su derecha.
+ab
Si el nodo insertado fue un operador, insertamos el siguiendo a su izquierda. Si el nodo insertado fue un operando, volvemos hacia atrás e insertamos el siguiente nodo a la derecha. Este proceso se continúa hasta que se agote la expresión escrita en prefijo. Veamos otro ejemplo:
Infijo a+(a*c d)
Primero debemos convertir la expresión a prefijo:
+a*b cd
Luego debemos insertar nuevos nodos hasta encontrar un operando:
+a
Luego volvemos hacia atrás e insertamos el siguiente elemento a la derecha:
+a*
Como el último nodo insertado fue un operador, debemos insertar el siguiente a la izquierda:
+a*b
Como el nodo mas reciente insertado fue un operando, volvemos hacia atrás e insertamos el siguiente a la derecha.
+a*b
Como el último nodo insertado fue un operador, debemos insertar el siguiente a la izquierda:
+ a * b c
Como el nodo más reciente insertado fue un operando, volvemos hacia atrás e insertamos el siguiente a la derecha:
+a*b cd
Siguiendo este método, y antes de seguir adelante, se recomienda al lector revisar los árboles para las siguientes expresiones en prefijo:
CONVERSION DE UNA EXPRESION EN UN ARBOL BINARIO A SU REPRESENTACION INFIJO
En este numeral se desarrollara una función que a partir de un árbol binario, genere un arreglo que almacene la expresión en infijo. Antes de entrar propiamente en el desarrollo del problema, estudiaremos algunas propiedades de estos árboles. Supongamos que tenemos en la memoria del computador un árbol así:
Este árbol representa la siguiente expresión
a+b*c
La expresión anterior escrita en prefijo será:
+ a * bc
Si recorremos el árbol en preorden los datos generados serán:
+a*bc
Lo anterior nos permite plantear la primera propiedad:
Si se recorre un árbol en preorden, los datos generados representan la expresión escrita en prefijo.
Si el árbol anterior recorremos en posorden, los datos generados serán:
a b c * +
Estos datos representan la expresión
a + b * c
Escrita en posfijo, lo cual nos permite plantear la segunda propiedad:
Si se recorre un árbol en posorden, los datos generados representan la expresión escrita en posfijo.
Es de esperarse que si recorremos el árbol en inorden, la expresión generada estará escrita automáticamente en infijo. Veamos:
a+b*c
Para el caso que nos ocupa se cumplió la norma. Veamos otro ejemplo:
(a+b) c/d+e
Esta expresión escrita en prefijo será:
+ / + a b c d e
Y en posfijo será:
a b + c d / e +
y el árbol generado será:
Al recorrerlo en preorden, los datos generados serán:
+ / + a b c d e
Al recorrerlo en posorden, los datos generados serán:
a b + c d / e +
Las dos propiedades anteriores se cumplen. Se recorremos el árbol en inorden los datos generados serán:
a + b c / d + e
Pero esta expresión, para su evaluación, se asocia así:
a + ( ( b c ) / d ) + e
Y es bien diferente da la inicial, la cual era:
(a+b) c/d+e
Lo cual nos permite plantear la siguiente propiedad:
Si se recorre un árbol en inorden, los datos generados no representan la expresión escrita en infijo.
Si queremos que de un árbol se genere la correspondiente expresión en infijo no basta con recorrerlo en inorden, además debemos efectuar un proceso que parentice la expresión. Para el ejemplo, el recorrido inorden del árbol es:
a+b c/d+e
Como el operador tiene más prioridad que los demás, y el operador / tiene más prioridad que el +, al tratar de evaluar la expresión esta se asocia así:
a + ( ( b c ) / d ) + e
Debemos diseñar un proceso que genere un arreglo infijo con los siguientes datos:
Lo cual implica que en la medida en que generamos este arreglo debemos ir incluyendo paréntesis donde sea necesario. Veamos la naturaleza del problema:
Como el operador de la raíz aplica a los dos subárboles, gráficamente el árbol anterior lo podemos representar así:
1
2
3
4
Si cada cuadro representa un par de paréntesis, este árbol lo podríamos escribir así:
(rama izquierda )+e
((rama izquierda ) / ) d ) + e
(((rama izquierda ) c ) / d ) + e
((((rama izquierda) + b) c ) / d ) +e
((( a ) + b) c ) / d + e
Ahora retiramos los paréntesis innecesarios, debidos a la jerarquía de los operadores, tendremos la expresión:
((( a +b) c ) / d ) + e
No podemos retirar los paréntesis que encierran la expresión (a+b), debido a que se cambia la expresión ya que el operador es de mayor prioridad que el operador +. Los paréntesis ya encierran la expresión (a+b) c si se puede retirar, debido a que el operador es de mayor jerarquía que el operador /
((a+b) c/d)+e
Los paréntesis que encierran la expresión (a+b) c / d pueden ser retirados ya que el operador + es el de al mínima jerarquía. Con la cual la expresión debidamente patentizada es:
Veamos otro ejemplo:
Si recorremos el árbol en inorden, los resultados serán:
a + b c
Lo cual es diferente a la expresión que esta representada en el árbol.
(a+ b ) c
Si el árbol es:
Al recorrerlo en inorden los resultados son:
a b+c
y no existe la necesidad de insertar paréntesis en la expresión. La diferencia, en este caso particular, radica en que si el operador padre tiene más jerarquía que el operador hijo, debemos patentizar la rama izquierda o derecha del árbol. Observemos los siguientes árboles:
Para el árbol la expresión será:
(a+b) c
Debe patentizarse. El operador tiene mas jerarquía que el operador +
Para el árbol la expresión será:
a b+c
no se necesitan paréntesis. El operador + tiene menos jerarquía que el operador
Para el árbol la expresión será:
(a-b)-c
Para esta expresión., no son necesarios los paréntesis ya que sin ellos la asociación se haría de la misma manera. Veamos este caso.
Para este caso al recorrer el árbol en inorden, se genera la siguiente expresión:
c – a – b
Se deben insertar paréntesis ya que es muy diferente la expresión que está representada en el árbol:
c – (a - b )
Ahora debemos puntualizar en que momento se necesitan insertar paréntesis.
La respuesta es muy sencilla. Veamos este ejemplo
Al recorrer el árbol en inorden, el resultado será:
a+b-c d+e*f
Debemos insertar paréntesis a la expresión a+b-c y también a la expresión d+e*f. al final arreglo infijo quedara así:
( a + b – c ) ((d + e ) * f )
Como puede identificarse esta situación. Obsérvese que si existen dos nodos cuya relación es padre-hijo y los dos contienen operadores, debemos abrir un paréntesis si el operador hijo tiene menos prioridad que el operador padre. Este paréntesis que se abre debe existir siempre y cuando el padre tenga más jerarquía que el hijo y asea izquierdo o derecho. Para insertar un paréntesis son necesarias tres condiciones:
1. que el nodo contenga un operador.
2. que su hijo (izquierdo o derecho) contenga también un operador.
3. que el nodo padre sea un operador de mayor jerarquía que el nodo hijo.
Si estas tres condiciones se cumplen debemos abrir un paréntesis. Este paréntesis, guardaremos en algún lugar el paréntesis que cierra para que en su momento, se incorpore al arreglo infijo. Para la solución a este problema debe servirnos una pila ya que el proceso se asimila a escribir un árbol en inorden, con la salvedad de que bajo las tres condiciones expuestas anteriormente, debemos insertar un paréntesis a la pila.