Tarea #7 [solución]

Recorrido por niveles de un árbol

      Para recorrer un árbol por niveles (Breadth-First) se puede usar una cola, en que que se agregan al final los nodos del árbol a recorrer. Como la lista incluye las operaciones de una cola, lo lógico es usar "std::list<>" para implementar el recorrido.

a /|\ / | \ b c d / \ \ e f g

a /|\ / | \ b d c | / \ g e f

      Además, su implementación debe recorrer en orden todos los nodos de cada nivel. Por ejemplo, el recorrido de los 2 árboles de la figura sería el mismo: a | b c d | e f g. Use el árbol n-ario visto en clase, pues esa implementación está hecha con referencias por lo que su clase cola<> puede ser declarada de la siguiente manera:

#include "Tree_L.h"

template <class T>
typdef std::list< TL::Tree<T> > cola;

      El truco para crear la cola es comenzar insertando la raíz de árbol junto con sus hijos, para luego continuar recorriéndola insertando los hijos de cada nodo. Para ordenar por niveles puede usar marcas dentro de la cola; estas marcas pueden ser un árbol nulo contruido invocando directamente al constructor por defecto de la clase: Tree<T>();. Otra forma de lograr el mismo resultado es almacenar en un vector de listas los nodos que corresponden a cada nivel, de manera que en VEC[0] esté la lista que contiene al nodo raíz, "{ a }" en este caso, VEC[1] sería la lista de hijos de primer nivel, "{ b c d }", etc. Una implementación Pascal de este algoritmo se encunentra en Q_BF.pas.

Di Mare, Adolfo

Una clase C++ completa para conocer y usar árboles, Reporte Técnico ECCI-2005-01, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 2005.
      http://www.di-mare.com/adolfo/p/TreeCpp.htm

Di Mare, Adolfo

La Implementación de Tree.pas, Reporte Técnico ECCI-94-07, Proyecto 326-89-019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
      http://www.di-mare.com/adolfo/p/Tree.doc
      http://www.di-mare.com/adolfo/p/src/Tree.zip

      Entregue su tarea por correo electrónico, como lo hizo anteriormente.

Entrega de Tareas

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2009
Derechos de autor reservados © 2009