[ Foro de Pascal ]

Sobre árboles, grafos, listas enlazadas, pilas y colas.

Un saludo muy grande profesor. Quiero que me aconseje sobre que me recomienda para aprender bien lo referente a listas enlazadas, pilas, colas, árboles y grafos. Me toca hacer un proyecto más o menos grande. Por favor, deme las primeras pautas a seguir.

Las ideas básicas sobre estructuras dinámicas las tienes en el tema 13 del curso:

http://www.aprendeaprogramar.com/mod/resource/view.php?id=156

Comienza por ahí, ve preguntando las dudas y vamos profundizando.

En el 13.4 tienes las ideas básicas sobre pilas, colas y árboles binarios. Sobre grafos no tengo nada elaborado. Podemos ir ampliando a partir de tus dudas, o bien puedes buscar un libro de "estructuras de datos" llegado ese punto.

He estado estudiando árboles, pero tengo dudas sobre un procedimiento que sale en el libro de Luis Joyanes sobre Estructura de Datos: se trata de un procedimiento "recursivo" sobre recorrer el árbol según la modalidad "EnOrden". Lo que no entiendo es cómo se opera recursivamente para obtener el campo Nombre de cada nodo. Sé que con cada llamada a la función se apilan las funciones y cuando se llega a un caso base se van operando las funciones desde la última hasta la primera.
El procedimiento es el siguiente:

const LongMax = 30 {longitud maxima del nombre}
type NombreTipo = string [LongMax];
 ptrTipo = ^nodoTipo;

 nodoTipo = record
              Nombre: nombreTipo;
              HijoIzdo: ptrTipo;
              HijoDcho: ptrTipo;
            end;
 TipoArbolBin = ptrTipo;


procedure EnOrden (A: TipoArbolBin);
begin
 if Anil then
  begin
    EnOrden(A^.HijoIzdo); {operación I}
    WriteLn(A^.Nombre);   {operación N}
    EnOrden(A^.HijoDcho); {operación D}
  end;
end;

Este es el arbol
...................M......................
.........E...................Z............
....A..........G........P.................
...................................Q......  

M es el Nodo raiz, del que se desprenden dos sub-áboles: el izquierdo es E y el derecho es Z.
De E sale el hijo Izquierdo A y, el derecho G
De Z sale un solo hijo, hijo Izquierdo P, y de P sale un solo hijo, hijo Derecho Q.


El resultado "EnOrden" debería ser: A E G M P Q Z

Mi duda es, más que todo sobre la operación de recursividad, ¿en qué momento se imprime el nombre del nodo A?, me gustaría saber cuál es el "caso base", es que yo hago el seguimiento y creo que cuando llegamos al nodo A, como el puntero a ese nodo es igual a nil, entonces no entraría en el if y por consiguiente no presentaría nunca el nombre de ese nodo. Por favor, prof., le pido que me ayude.
Muchos Saludos.

Tú mismo lo has dicho casi por completo:

- Si un nodo está vacío (es "nil"), no se entra a él y no se procesa.

- En caso de que contenga datos, es cuando se entrará al cuerpo del procedimiento (EnOrden) y se mostrará su contenido.

- Eso sí, como es un recorrido "en orden", primero se deben mostrar los hijos que pueda haber a su izquierda (y que serían "menores", por definición del modo en que se construye el árbol), luego el dato actual y luego los hijos a la derecha (que serán "mayores").

- ¿Y si no hay hijos a la izquierda o a la derecha?  No es problema, el procedimiento recursivo se comportará bien, porque se analizaría ese supuesto sub-nodo, pero como es "nil" no se haría nada con él y al terminar la llamada recursiva se volvería al nivel superior.