Tarea #5 [solución]

Iterador Tree_BFs.h para el Arbol

      En esta tarea programada usted programará el iterador Tree_BFs.h (Tree .. Breadth First .. Stack) que sirve para recorrer un árbol por niveles, comenzando por el nivel superior hasta llegar a las hojas. Por ejemplo, el orden de recorrido que resulta al usar su iterador deberá ser [a,b,c,d,e,f,g,h,i,j,k,l,m] si se aplica en el siguiente árbol:

a /|\ / / \ \ b c d e /|\ /|\ f g h i j k / \ l m

      En el módulo Q_BF.pas usted encontrará una versión de este iterador que fue programado utilizando una cola, en la que se almacenan punteros a todos los nodos del árbol en el orden en que deben ser retornados por el iterador. El problema de este iterador es que necesita usar siempre una cantidad proporcional al número de nodos del árbol.

      Usted debe implementar el módulo Tree_BFs.h, que realiza el mismo trabajo que Q_BF.pas, pero en lugar de usar una cola, en su implementación usted deberá usar una pila en la que almacenará la rama del subárbol que se está recorriendo. De esta forma, la cantidad máxima de nodos que estarán almacenados en la pila será proporcional a la altura del árbol, que en general es proporcional al logaritmo de la cantidad de nodos del árbol.

      En el libro de texto [AHU-1984] usted puede encontrar algunas ideas de cómo realizar su trabajo. Además, use el árbol C++ como base para trabajar:

Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.

Data Structures and Algorithms, Addisson Wesley Publishing Co., 1984.

Di Mare, Adolfo:

Una abstracción C++ completa de la clase árbol, 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
      http://www.di-mare.com/adolfo/p/TreeCpp/TreeCpp.zip

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

Entrega de Tareas

Soluciones

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