INTRODUCCIÓN

En este trabajo se estudian en detalle las estructuras de datos pilas y arboles que son probablemente las utilizadas mas frecuentemente en los programas mas usuales. Las pilas se conocen también como estructuras lifo (last-in, first-out, último en entrar-primero en salir).Entre las numerosas aplicaciones de las pilas destaca la evaluación de expresiones algebraicas, así como la organización de la memoria. Los arboles son muy utilizados para representar formulas algebraicas como un método eficiente para búsquedas generales y complejas, listas dinamicas y aplicaciones diversas tales como inteligencia artificial o algoritmos de cifrado.

PILA

Una pila (stack) es una colección ordenada de elementos a los que sólo se puede acceder por un único lugar o extremo de la pila. Los elementos de la pila se añaden o quitan (borran) de la misma sólo por su parte superior (cima) de la pila. Éste es el caso de una pila de platos, una pila de libros, etc.

Una pila es una estructuta de datos de entradas ordenadas tales que soolo se pueden introducir y eliminar por un extremo que se llama cima.

Cuando se dice que la pila esta ordenada, lo que se quiere decir es que hay un elemento al que se puede acceder primero (el que esta encima de la pila), otro elemento al que se puede acceder en segundo lugar (justo el elemento que esta debajo de la cima), un tercero,etc. No se requiere que las entradas se puedan comparar utilizando el operador «menor que» (<) y pueden ser de cualquier tipo.
Las entradas de la pila deben ser eliminadas en el orden inverso al que se situaron en la misma. Por ejemplo, se puede crear una pila de libros, situando primero un diccionario, encima de él una enciclopedia y encima de ambos una novela de modo que la pila tendra la novela en la parte superior.

Cuando se quitan los libros de la pila, primero debe quitarse la novela, luego la enciclopedia y, por último, el diccionario. Debido a su propiedad específica «último en entra6 primero en salir» se conoce a las pilas como estructura de datos LIFO (last-in, first-out). Las operaciones usuales en la pila son Insertar y Quitar. La operación Insertar (push) añade un elemento en la cima de la pila y la operación Quitar (pop) elimina o saca un elemento de la pila. La Figura muestra una secuencia de operaciones Insertar y Quitar. El último elemento añadido a la pila es el primero que se quita de la pila.

La operación Insertar (push) sitúa un elemento dato en la cima de la pila y Quitar (pop) elimina o quita el elemento de la pila.

La pila se puede implementar mediante arrays en cuyo caso su dimensión o longitud es fija, y mediante punteros o listas enlazadas en cuyo caso se utiliza memoria dinamica y no existe limitación en su tamaño.

Una pilapuede estar vacía (no tiene elementos) o llena (en el caso de tener tamaño fijo, si no cabe mas elementos en la pila). Si un programa intenta sacar un elemento de una pila vacía, se producira un error debido a que esa operación es imposible; esta situación se denomina desbordamiento negativo (underflow). Por el contrario, si un programa intenta poner un elemento en una pila se produce un error llamado desbordamiento (overflow) o rehosamiento. Pata evitar estas situaciones se diseña funciones, que comprueban si la pila esta llena o vacía.

ESPECIFICACIONES DE UNA PILA

Las operaciones que sirven para definir una pila y poder manipular su contenido son las siguientes (no todas ellas se implementan al definir una pila).

Tipo de dato | Dato que se almacena en la pila. |
Insertar (push) | Insertar un dato en la pila. |
Quitar (pop) | Sacar (quitar) un dato de la pila. |
Pila vacía | Comprobar si la pila no tiene elementos. |
Pila llena | Comprobar si la pila esta llena de elementos. |
Limpiar pila | Quitar todos sus elementos y dejar la pila vacía. |
Tamaño de la pila | Número de elementos maximo que puede contener la pila. |
Cima | Obtiene el elemento cima de la pila. |

EL TIPO PILA IMPLEMENTADO CON ARRAYS

Una pila se puede implementar mediante arrys o mediante listas enlazadas. Una implementación estatica se realiza utilizando un array de tamañofijo y una implementación dinamica mediante una lista enlazada.

En C para definir una pila con arrays se utiliza una estructura. Los miembros de la estructura pila incluyen una lista (array) y un índice o puntero a la cima de la pila; ademas una constante con el maximo número de elementos. El tipo pila junto al conjunto de operaciones de la pila se pueden encerrar en un archivo de inclusión (pi la. H). AI utilizar un array para contener los elementos de la pila hay que tener en cuenta que el tamaño de la pila no puede exceder el número de elementos del array y la condición pila llena sera significativa para el diseño.

El método usual de introducir elementos en una pila es definir el fondo de la pila en la posición O del array y sin ningún elemento en su interior, es decir, definir una pila vacía; a continuación, se van introduciendo elementos en el array (en la pila) de modo que el primer elemento añadido se introduce en una pila vacía y en la posición O, el segundo elemento en la posición 1, el siguiente en la posición 2 y así sucesivamente. Con estas operaciones el puntero (apuntador) que apunta a la cima de la pila se va incrementando en 1 cada vez que se añade un nuevo elemento; es decir, el puntero de la pila almacena el índice del array que se esta utilizando como cima de la pila. Los algoritmos de introducir «insertar» (push) y quitar «sacar» (pop) datosde la pila utilizan el índice del array como puntero de la pila son:

* Insertar (push):

1. verificar si la pila no esta llena.
2. Incrementar en 1 el puntero de la pila.
3. Almacenar elemento en la posición del puntero de la pila.

* Quitar (pop

1. si la pila no esta vacía.
2. Leer el elemento de la posición del puntero de la pila.
3. Decrementar en 1 el puntero de la pila.

En el caso de que el array que define la pila tenga TamanioPila elementos, las posiciones del Array, es decir, el índice o puntero de la pila, estaran comprendidas en el rango O a TamanioPila-1 elementos, de modo que en una pila llena el puntero de la pila apunta a TamanioPila- 1 y en una pila vacía el puntero de la pila apunta a - 1, ya que O, teóricamente, sera el índice del primer elemento.

Si se almacenan los datos A, B, c en la pila se puede representar graficamente por alguno de estos métodos.

Veamos ahora como queda la pila en función de diferentes situaciones de un posible programa.

ESPECIFICACIÓN DEL TIPO PILA

La declaración de una pila incluye los datos y operaciones ya citados anteriormente.
1. Datos de la pila (tipo Ti pouat-a, que es conveniente definirlo mediante typedef).
2. Verificar que la pila no esta llena antes de intentar insertar o poner (<<push»u)n elemento en la pila; verificar que una pila no estavacía antes de intentar quitar sacar ( q m p ~u)n elemento de la pila. Si estas precondiciones no se cumplen se debe visualizar un mensaje de error y el programa debe terminar.
3. Pilavacia devuelve I (verdadero) si la pila esta vacía y O (falso) en caso contrario.
4. Pilallena devuelve 1 (verdadero) si la pila esta llena y O (falso) en caso contrario. Estas
5. Limpiarpila. Se limpia o vacía la pila, dejandola sin elementos y disponible para otras tareas.
6. Cima devuelve el valor situado en la cima de la pila, pero no se decrernenta el puntero de la funciones se utilizan para verificar las operaciones del parrafo 2. pila, ya que la pila queda intacta.

IMPLEMENTACIÓN DE LAS OPERACIONES SOBRE PILAS

Las operaciones de la pila definidas en la especificación se implementan en el archivo pilarray .c para después formar un proyecto con otros módulos y la función principal.

Las otras operaciones de la pila declaradas en el archivo pilarray son: insertar, quitar y Cima. La operación insertar y quitar, insertan y eliminan un elemento de la pila; la operación cima permite a un cliente recuperar los datos de la cima de la pila sin quitar realmente el elemento de la misma.

La operación de Tnsertdr un elemento en la pila incrementa el puntero de la pila (cima) en I y asigna el nuevo elemento a la lista de la pila. Cualquier intento de añadir un elementoen una pila llena produce un mensaje de error «Desbordamiento pila>> y debe terminar el programa.

La operación Quitar- elimina un elemento de la pila copiando primero el valor de la cima de la pila en una variable local aux y a continuación decrementa el puntero de la pila en 1. La variable aux se devuelve en la ejecución de la operación Quitar. Si se intenta eliminar o borrar un elemento en una pila vacía se debe producir un mensaje de error y el programa debe terminar.

OPERACIONES DE VERIFICACIÓN DEL ESTADO DE LA PILA

Se debe proteger la integridad de la pila, para lo cual el tipo P i 1 a ha de proporcionar operaciones que comprueben el estado de la pila: pila vacía o pila llena. Asimismo se ha de definir una operación que restaure la condición inicial de la pila, que fue determinada por el constructor CrearPila (cima de la pila a - I), Limpiarpila.

La función Pilavacia comprueba (verifica) si la cima de la pila es -1. En); en caso contrario, se devuelve O (falso).

La función PilaLlena comprueba (verifica) si la cima es MaxTamaPila-1. En ese caso, la pila esta llena y se devuelve un 1 (verdadero); en caso contrario, se devuelve O (falso).

Por último la operación Limpiar reinicializa la cima a su valor inicial con la pila vacía (-1).

ARBOLES

Un arbol es una estructura en la que los datos se organizan de modo que los elementos deinformación estan relacionados entre sí a través de ramas.
Un arbol consta de un conjunto de finos elementos, denominados nodos y un conjunto de líneas dirigidas, denominadas ramas, que conectan los nodos, el número de ramas asociadas a un nodo es el grado del nodo.
Un arbol esta formado por uno o mas nodos, tales que, hay un nodo diseñado especialmente llamado raíz. Los nodos restantes se dividen en n>=0 conjuntos disjuntos, tales que T1..Tn en donde cada uno de estos conjuntos es un arbol. A T, T2Tn se les denomina subarboles de la raíz.

Figura 1

La figura 1 muestras un arbol donde el primer nodo no esta vacío, por lo que recibe el nombre de raíz. Los nodos sucesores se llaman hijos, un arbol puede representar diversas generaciones en la familia, los hijos de un nodo y los hijos de estos hijos se llaman descendientes y el padre y el abuelo de unos nodos son sus ascendientes. Cada nodo no raíz tiene un único padre, y cada padre tiene cero o mas nodos hijos. Dos o mas nodos con el mismo padre se llaman hermanos, un nodo sin hijos se llama nodo hoja.

En la figura 1 el nodo A, es padre de los nodos B, E y F, los cuales a su vez son hermanos. Los nodos C y D son hijos del nodo B, a su vez estos nodos son hermanos, los nodos G, H e I son hijos del nodo F, que a su vez son hermanos. El nodo A es abuelo de los nodos C, D, G, H e I, los nodos E, C, D, G, H e Ison nodos hojas ya que ninguno de ellos posee hijos.

El nivel de un nudo es su distancia al nodo raíz, la raíz tiene una distancia cero de sí mismo, por lo que se dice que la raíz esta en el nivel cero, los hijos del nodo raíz estan en el nivel uno, sus hijos en el nivel dos y así sucesivamente tantas descendencias tenga el nodo raíz. En los niveles de los nodos se puede apreciar la relación entre niveles y hermanos, los hermanos estén siempre al mismo nivel, pero no todos los nodos de un mismo nivel son necesariamente hermanos.

Figura 2.

En la figura 2, se puede observar que los nodos C, D, G, H e I se encuentran en el mismo nivel, C y D son hermanos al igual que G, H e I, pero C y G no son hermanos ya que poseen diferentes padres.

En la Figura 2 el camino desde la raíz hasta la hora I es representado por AFI, el cual incluye dos ramas distintas AF y FI.
La altura o profundidad de un arbol es el nivel de la hoja del camino mas largo desde la raíz mas o uno. La Figura 2 esta constituida por los niveles 0, 1 y 2, por lo tanto su altura o profundidad es 3.

Un arbol se divide en subarboles, un subarbol es cualquier estructura conectada por debajo del nodo raíz. Cada nodo de un arbol es la raíz de un subarbol que se define por el nodo y todos los descendientes del nodo, el primer nodo de un subarbol se conoce como la raíz del subarbol y se utiliza paranombrarlo. Ademas los subarbol se pueden sub dividir en subarboles.

En la Figura 2, los nodos BCD es un subarboles al igual que E y FGHI, la definición nos dice que un nodo simple es un subarbol por lo tanto el subarbol B se puede dividir en los subarboles C y D, estos son subarboles sin descendientes.

Un arbol esta en equilibro cuando dado un número maximo de k hijos para cada nodo y la altura del arbol h, cada nodo de nivel l < h -1 tiene exactamente k. El arbol esta equilibrado perfectamente cuando cada nodo de nivel l < h tiene exactamente k hijos.

REPRESENTACIÓN DE UN ARBOL

Existen dos maneras de representar un arbol de manera grafica (en papel), la primera es el diagrama o carta de organización, para detonarlas se utiliza el término de arbol general.

Representación en Niveles de Profundidad.

Este tipo de representación se utiliza para representar sistemas jerarquicos en modo texto o numero, en situaciones tales como facturación, almacén, entre otras.

Representación de Lista.

Esta notación es utilizada con expresiones algebraicas, esta representación se utiliza los paréntesis, cada paréntesis abierto indica el comienzo de un nuevo nivel, cada paréntesis cerrado completa un nivel y se mueve hacia arriba un nivel en el arbol.
La representación de lista de la Figura 2 es; A (B (C, D) E, F (G, H, I)).

ARBOLES BINARIOS

En los arbolesbinarios ningún nodo puede tener mas de dos subarboles. Cada nodo puede tener, cero, uno o dos hijos (subarboles).
En cualquier nivel n, un arbol binario puede contener de 1 a 2 nodos, el número de nodos por nivel contribuye a la densidad del arbol.

Figura 3.

En la Figura 3, el arbol a contiene 8 nodos en una profundidad de 4, mientras que el arbol b contiene 5 nodos y una profundidad de 5. Este último caso es una forma especial, denominado arbol degenerado, en el que existe un solo nodo hoja (E) y cada nodo no hoja sólo tiene un hijo. Un arbol degenerado es equivalente a una lista enlazada.

EQUILIBRIO EN ARBOL BINARIO

Para determinar si un arbol esta equilibrado, se calcula su factor de equilibrio.
El factor de equilibro de un arbol binario es la diferencia de altura entre los subarboles derecho e izquierdo. Si definimos la altura del subarbol izquierdo como H, y la altura del subarbol derecho como H, entonces el factor de equilibrio del arbol B se determina por la siguiente formula B = H – H.

Un arbol esta perfectamente equilibrado si su equilibrio o balance cero y sus subarboles son también perfectamente equilibrados. Existe una definición alternativa que se aplica a un mayor número de casos. Un arbol binario esta en equilibrio si la altura de sus subarboles difiere en no mas de uno (su factor de equilibrio -1, 0, +1) y sus subarboles son tambiénequilibrados.

ARBOLES BINARIOS COMPLETOS

Un arbol binario completo de profundidad n es un arbol en el que cada nivel, del 0 al nivel n-1 tiene un conjunto lleno de nodos y todos los nodos hojas del nivel n ocupan las posiciones mas a la izquierda del arbol.
Un arbol binario que contiene 2 nodos en el nivel n es un arbol lleno. Un arbol lleno es un arbol binario que tiene el maximo número de entradas para su altura. Esto sucede cuando el último nivel esta lleno.

Figura 4 – Arbol Completo (Profundidad 4).

Figura 5 – Arbol Degenerado (Profundidad 5) (Figura Izquierda), Arbol Lleno
(Profundidad 3)(Figura Derecha).

Los arboles binarios llenos de profundidad k+1 proporcionan algunos datos matematicos, en cada caso existe un nodo (2) al nivel 0 (raíz), dos nodos (2) al nivel 1, cuatro nodos (2) al nivel 2, etc. A través de los primeros k-1 niveles hay 2-I nodos.
1 + 2 + 4 ++ 2k+1 = 2k – 1

A nivel k, el número de nodos adicionados para un arbol completo esta en el rango de un mínimo de 1 a un maximo de 2 (lleno). Con un arbol lleno el número de nodos es:
1 + 2 + 4 ++ 2k+ + 2k = 2k+ - 1

Un número de nodos n es un arbol binario completo de profundidad k + 1 (0 a k niveles) cumple la igualdad: 2k =< n =< 2k+1 – 1 < 2k+1

Aplicando logaritmos a la ecuación con desigualdad anterior: k log2 (n) < k + 1
Se deduce que la altura o profundidadde un arbol binario completo de n nodos es: h = /log.n + 1/ (parte entera de log2n + 1)

OPERACIONES EN ARBOLES BINARIOS

Las operaciones típicas que se pueden realizar en un arbol binario son las siguientes:
* Determinar su altura.
* Determinar su número de elementos.
* Hacer una copia.
* Visualizar el arbol binario en pantalla o en impresora.
* Determinar dos arboles binarios son idénticos.
* Borrar (eliminar arbol).
* Si es un arbol de expresión, evaluar la expresión.
* Si es un arbol de expresión, obtener la forma de paréntesis de la expresión.

Todas estas operaciones se pueden realizar recorriendo el arbol binario de un modo sistematico. El recorrido de un arbol es la operación de visita al arbol, o lo que es lo mismo, la visita a casa nodo del arbol una vez y sólo una vez.

ARBOLES DE EXPRESIÓN

Una expresión es una secuencia de tokens (componentes de léxicos que siguen unas reglas prescritas). Un token puede ser o bien un operando o bien un operador.
Los arboles de expresión poseen las siguientes propiedades:
* Cada hoja es un operador.
* Los nodos raíz e internos son operadores.
* Los subarboles son subexpresiones en las que el nodo raíz es un operador.

Los arboles binarios se utilizan para representar expresiones en memoria.

Figura 6 – Arbol Binario de Expresión.

La figura 6 muestra unarbol binario de expresión para la expresión aritmética
(a + b) * c, los paréntesis no se almacenan en el arbol pero estan implicados en la forma del arbol. Si se supone que todos los operadores tienen dos operandos, se puede representar una expresión por un arbol binario cuya raíz contiene un operador y cuyos subarboles izquierdo y derecho son los operandos izquierdo y derecho respectivamente. Cada operando puede ser una letra o una subexpresion representada como un subarbol.

REGLAS PARA LA CONSTRUCCIÓN DE ARBOLES DE EXPRESIÓN.

Los arboles de expresiones se utilizan en las computadoras para evaluar expresiones usadas en programas. El algoritmo mas sencillo para construir un arbol de expresión es uno que lee una expresión completa que contiene paréntesis en la misma.

El algoritmo para la construcción de un arbol de expresión es:
* La primera vez que se encuentra un paréntesis a la izquierda, crea un nodo y lo hace en el raíz. Se llama a éste, el nodo actual y se sitúa su puntero en una pila.
* Cada vez que se encuentre un nuevo paréntesis a la izquierda, crear un nuevo nodo, si el nodo actual no tiene un hijo izquierdo, hacer el nuevo nodo el hijo izquierdo; en caso contrario, hacerlo el hijo derecho. Hacer el nuevo nodo actual y situar su puntero en la pila.
* Cuando se encuentra un operando, crear un nuevo nodo y asignar el operando a su campode datos. Si el nodo actual no tiene un hijo izquierdo, hacer el nuevo nodo el hijo izquierdo; en caso contrario, hacerlo el hijo derecho.
* Cuando se encuentra un operador, se saca un puntero de la pila y situar el operador en el campo datos del nodo del puntero
* Ignorar paréntesis derechos y blancos.

RECORRIENDO DE UN ARBOL

Los arboles binarios no tienen realmente un primer valor, un segundo valor, tercer valor, etc. Se puede afirmar que el raíz viene primero, existen diferentes métodos de recorrido de arbol ya que la mayoría de las aplicaciones binarias son sensibles al orden en que se visitan los nodos de forma que sera preciso tener cuidado al elegir el método del recorrido.

Un recorrido de un arbol binario requiere que cada nodo del arbol sea procesado, una vez y solo una vez en una secuencia predeterminada. Existen dos enfoque generales para la secuencia de recorrido, profundidad y anchura.
En el recorrido en profundidad, el proceso exige un camino desde la raíz a través de un hijo, al descendiente mas lejano del primer hijo antes de proseguir a un segundo hijo.

En el recorrido en anchura, el proceso se realiza horizontalmente desde la raíz a todos sus hijos a continuación a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados.

La designación de los recorridos utiliza un nombre para el nodo raíz(N), para el subarbol izquierdo (I) y para el subarbol derecho (D). Según sea la estrategia a seguir, los recorridos se conocen como enorden (inorder), preorden (preorder) y postorden (postorder).
* Preorden (nodo-izquierdo-derecho) (NID)
* Enorden (izquierdo-nodo-derecho) (IND)
* Postorden (Izquierdo-derecho-nodo) (IDN

RECORRIDO PREORDEN

El recorrido preorden (NID) conlleva a los siguientes pasos, en los que el raíz va antes que los subarboles:
* Recorrer la raíz (N).
* Recorrer el subarbol izquierdo (I) en preorden.
* Recorrer el subarbol derecho (D) en preorden.

El algoritmo de recorrido tiene naturaleza recursiva. Primero se procesa la raíz, a continuación el subarbol izquierdo y a continuación el subarbol derecho. Para procesar el subarbol izquierdo, se hace una llamada recursiva al procedimiento preorden y luego se hace lo mismo con el subarbol derecho.

Figura 7 – Recorrido Preorden de un Arbol Binario.

La Figura 7 muestra el recorrido preorden del arbol, se visita primero la raíz
(Nodo A), luego se visita el subarbol izquierdo de A, que costa de los nodos B, D y E. Dado que el subarbol es a su vez un arbol, se visitan los nodos utilizando el orden NID. Por consiguiente, se visita primero el nodo B, después D (izquierdo) y por ultimo E (derecho). A continuación se visita el subarbol derecho de A, que es un arbol quecontiene los nodos C, F y G. De nuevo siguiendo el orden NID, se visita primero el nodo C, a continuación F (izquierdo) y por ultimo G (derecho). En consecuencia el orden del recorrido preorden para el arbol de la Figura 7 es: A-B-D-E-C-F-G.

RECORRIDO ENORDEN

El recorrido enorden (inorder) procesa primero el subarbol izquierdo, después el raíz y a continuación el subarbol derecho. El significado de in es que la raíz se procesa entre los subarboles. Si el arbol no esta vacío, el método implica los siguientes pasos:
* Recorrer el subarbol izquierdo (I) en inorden.
* Visitar el nodo raíz (N).
* Recorrer el subarbol derecho (D) en inorden.

Figura 8 – Recorrido Enorden de un Arbol Binario.

La Figura 8 los nodos en esta figura fueron enumerados en el orden que son visitados durante el recorrido enorden, el primer subarbol recorrido es el subarbol izquierdo del nodo raíz (arbol cuyo nodo es B), este subarbol consta de los nodos B, D y E y es a su vez otro arbol con el nodo B como raíz, por lo que siguiendo el orden IND, se visita primero D, a continuación B (nodo raíz) y, por ultimo E (derecha).

Después de la visita del subarbol izquierdo se visita el nodo raíz A y por último se visita el subarbol derecho, que consta de los nodos C, F y G. A continuación siguiendo el orden IND para el subarbol derecho, se visita primero F, después C (nodo raíz) y porúltimo, G (derecha), por consiguiente el orden del recorrido inorden de la Figura 8 es: D-B-E-A-F-C-G.

RECORRIDO POSTORDEN

El recorrido postorden (IDN) procesa el nodo raíz (post) después de que los subarboles izquierdos y derechos se han procesado, se comienza situandose en la hoja mas a la izquierda y se procesa, a continuación se procesa su subarbol derecho. Por último se procesa el nodo raíz, las etapas del algoritmo son:
* Recorrer el subarbol izquierdo (I) en postorden.
* Recorrer el subarbol derecho (D) en postorden.
* Visitar el nodo raíz (N).
Figura 9 – Recorrido Postorden de un Arbol Binario.

La Figura 9 los nodos en esta figura fueron enumerados en el orden que son visitados durante el recorrido postorden, se visita primero el subarbol izquierdo A, este subarbol consta de los nodos B, D y E y siguiendo el orden IDN, se visita primero
D (izquierdo), luego E (derecho) y por ultimo B (nodo). A continuación se visita el subarbol derecho A, que consta de los nodos C, F y G siguiendo el orden IDN para este arbol, se visita primero F (izquierdo), luego G (derecho) y por ultimo C (nodo), finalmente se visita el raíz A (nodo), así el orden del recorrido postorden para el arbol de la Figura 9 es: D-E-B-F-G-C-A.

ARBOL BINARIO DE BÚSQUEDA

Los arboles binarios ordenados tiene sentido, estos arboles se denominan arboles binarios de búsqueda,debido a que se pueden buscar en ellos un término utilizando un algoritmo de búsqueda binaria. Un arbol binario de búsqueda es aquel que dado un nodo, todos los datos del subarbol izquierdo son menores a los datos de ese nodo, mientras que todos los datos del subarbol derecho son mayores que sus propios datos.

Figura 10 – Arbol Binario de Búsqueda.

CONCLUSIÓN

El método de pila para la evaluación de expresiones fue propuesto en 1955 y dos años después patentado por Fiedrich L.Bauer, quién recibió en 1988 el premio 'IEEE Computer Society Pioneer Award' por su trabajo en el desarrollo de dicha estructura de datos.
En ciencias de la informatica, un arbol es una estructura de datos ampliamente usada que imita la forma de un arbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el arbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demas nodos (tienen padre y uno o varios hijos) se les conoce como rama.

BIBLIOGRAFÍA

Programación en C, Metodología, Algoritmos y estructura de datos.
Joyanes Aguilar, Luis & Zahonero Martínez, Ignacio.
McGraw-Hill - 2000 Primera Edición.