Algoritmos y Estructuras de Datos (VJ1215)

#include <queue>

void Conjunto::mostrarPorNiveles() const {

   queue<Nodo *> nodosAMostrar;

   cout << "<";
   if (raiz != nullptr) {
      nodosAMostrar.push(raiz);
      while (! nodosAMostrar.empty()) {
	 Nodo * nodo = nodosAMostrar.front();
	 nodosAMostrar.pop();
	 cout << " " << nodo->dato;
	 if (nodo->izquierdo != nullptr)
	    nodosAMostrar.push(nodo->izquierdo);
	 if (nodo->derecho != nullptr)
	    nodosAMostrar.push(nodo->derecho);
      }
   }
   cout << " >" << endl;

}
      

En el algoritmo se usa una cola. Mientras de la cola van saliendo (desencolando) los nodos que están a profundidad i, se van metiendo al final (encolando) los que están a profundidad i + 1, que son sus hijos, para que salgan después de todos los que están a profundidad i. Por ejemplo:

1. Se empieza metiendo en la cola la raíz (nodo con 37) que está a profundidad 0.

2. Tras desencolar la raíz, se encolan sus hijos, que están a profundidad 1 (nodos con 32 y 75).

3. Mientras se desencolan los nodos a profundidad 1, se encolan los nodos a profundidad 2 (nodos con 4, 38 y 84): tras desencolar el nodo con 32 se encola el nodo con 4 y tras desencolar el nodo con 75 se encolan los nodos con 38 y 84.

4. Mientras se desencolan los nodos a profundidad 2, se encolan los nodos a profundidad 3 (nodos con 23 y 63).

5. Tras desencolar los nodos a profundidad 3, como ninguno tiene hijos, la cola queda vacía y el recorrido por niveles termina.

En la implementación en C++ guardamos en la cola las direcciones de los nodos.

El coste temporal de este algoritmo es O(n), siendo n la cantidad de nodos del árbol, porque encolar y desencolar tienen coste temporal O(1) y se realizan una vez por nodo.