estructuras de datos

Árboles binarios
Los árboles binarios son estructuras matemáticas que organizan un conjunto de elementos. Supondremos en este ejercicio que en un mismo árbol no puede haber elementos repetidos. Cada elemento se almacena en un nodo. Algunos de los nodos pueden estar relacionados, y son estas relaciones las que definen el árbol. Definimos un árbol binario de la manera siguiente:
El árbol vacíoes un árbol binario que no contiene ningún nodo.
Dados dos árboles binarios  y  y dado un elemento x, se puede formar un tercer árbol binario  enraizando  y  con un nodo que almacene x. Diremos que el nuevo nodo que almacena x es la raíz de ,  es el subárbol izquierdo de , y  el subárbol derecho. Diremos también que la raíz de  es el hijo izquierdo de la raíz de , la raíz de  es elhijo derecho de la raíz de  y, por consiguiente, la raíz de  es el padre de las raíces de ambos subárboles.
En la figura siguiente se muestra un ejemplo de árbol binario:
A: raíz del árbol
A: padre de C y de E
C: hijo izquierdo de A
E: hijo derecho de A

Notemos pues que los nodos de un árbol binario pueden tener 0, 1 ó 2 hijos.
1.- Dado un árbol binario  conletras mayúsculas almacenadas en los nodos (es decir, con un máximo de 26 nodos, pues excluimos la 'Ñ' y la 'Ç'), se define su recorrido en preorden como un listado de los elementos contenidos en sus nodos según la definición siguiente:
Si  es un árbol vacío, se da por finalizado su recorrido.
Si no, el primer elemento del listado es el contenido en la raíz de .
A continuación, aparecen enpreorden los elementos del subárbol izquierdo de .
Por último, aparecen en preorden los elementos del subárbol derecho de .
El recorrido en preorden del árbol de la figura anterior es: A C B E F D.
Nos proponemos construir un programa que calcule el recorrido en preorden de un árbol binario. El árbol residirá en el fichero "ARB1.DAT", que consta de una serie de líneas que definen qué nodos sonpadres de cuáles otros. Cada línea consta de exactamente de cinco caracteres:
Una letra mayúscula que identifica un nodo.
Un carácter blanco.
Una letra mayúscula que identifica otro nodo.
Un carácter blanco.
Un símbolo que puede ser: o bien '', que indica que el segundo nodo es hijo derecho del primero.
Puede suponerse que la entrada permite construir un árbol binario correcto (es decir, dondetodo nodo tenga un único padre, excepto uno de ellos que es la raíz; donde todo nodo tiene como máximo un hijo izquierdo y un hijo derecho; y donde no hay caracteres repetidos). El árbol de la figura anterior puede representarse con el fichero de entrada siguiente (o con cualquier otro que sea una simple permutación de sus líneas):

ARB1.DAT
C B >
E F <
A C <
E D >
A E >

La salida"ARB1.RES" será una única línea que mostrará el listado resultante de recorrer el árbol en preorden, escribiendo un carácter blanco después de cada contenido de nodo.

2.- Definimos el recorrido en inorden de un árbol binario A de manera similar al preorden:
Si  es un árbol vacío, se da por finalizado su recorrido.
Si no, primero aparecen en inorden los elementos del subárbol izquierdo de .
Acontinuación, aparece el contenido en la raíz de .
Por último, aparecen en inorden los elementos del subárbol derecho de .
El recorrido en inorden del árbol de la figura anterior es: C B A F E D.
Puede demostrarse que un árbol binario se puede reconstruir a partir de sus recorridos en preorden e inorden, y se pide un programa que efectúe este proceso. El fichero de entrada, "ARB2.DAT",contendrá dos líneas, la primera con el recorrido en preorden y la segunda con el recorrido en inorden. En cada una de estas líneas aparecerá un carácter blanco después de cada contenido de nodo. Puede suponerse la corrección de este juego de pruebas. El fichero de salida "ARB2.RES" contiene el árbol en el mismo formato que el fichero de entrada "ARB1.DAT" del apartado anterior, con la única diferencia...