Recorrido en Pre-Orden de un Árbol Binario
El siguiente ejemplo ilustra el uso del Patrón Iterator al hacer
recorridos en pre-orden de un árbol binario.
El ejemplo posee la siguiente estructura:
Las clases a las cuales les debemos prestar atención son:
-
AbstractGraph como una representación genérica abstracta
de los grafos, cuya información es del tipo Type. Aquí
solo se utiliza la función de insertar un nodo en el grafo (Ins_Node),
la función de observar el valor de la información contenida
en un nodo (Info) y la función CreateIterator que retorna
un iterador abstracto para ésta clase.
-
AbstractIterator representa el iterador genérico abstracto,
con las funciones principales de iteración: First, Next, IsDone
y CurrentItem.
-
ConcreteTree se refiere a un grafo concreto (árbol binario),
el cual es representado internamente por medio de un vector de MAX_NODES
(definido en los fuentes como 127) posiciones, llamado root.
También implementa las funciones heredadas de AbstractGraph.
La representación interna del árbol es la siguiente:
La raíz de un sub-árbol se encuentra en la posición
n.
El árbol izquierdo (hijo izq.) se encuentra en la posición
2n+1 dentro del vector.
El árbol derecho (hijo der.) se encuentra en la posición
2n+2 dentro del vector.
-
ConcreteIterator se refiere a un iterador concreto para árboles
binarios, es decir, su función es la de implementar un recorrido
en pre-orden de árboles binarios, por lo tanto implementa las funciones
heredadas de AbstractIterator para objetos del tipo árbol
binario.
Tenga en cuenta que los parámetros utilizados en
AbstractGraph::CreateIterator y en ConcreteIterator::ConcreteIterator
son apuntadores a objetos de las clases bases. Esto es para darle
mayor generalidad a los procedimientos, al acceder a los objetos por medio
de sus clases bases.
La pila implementada para ConcreteIterator es
única y exclusivamente para el manejo de valores enteros.
El ejemplo
implementado es bastante sencillo. Sigue, a groso modo, los siguientes
pasos:
-
Crea un árbol binario cuyos elementos son del tipo int.
-
Inserta 10 nodos, obteniendo el valor de la información de cada
uno de ellos pseudo-aleatoriamente.
-
Muestra la posición y la información de cada uno de los nodos
dentro del árbol.
-
Por último, realiza el recorrido en pre-orden del árbol.