Curso 2023/2024
#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:
Se empieza metiendo en la cola la raíz (nodo con 37) que está a profundidad 0.
Tras desencolar la raíz, se encolan sus hijos, que están a profundidad 1 (nodos con 32 y 75).
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.
Mientras se desencolan los nodos a profundidad 2, se encolan los nodos a profundidad 3 (nodos con 23 y 63).
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.