[C con Clase] (sin asunto)

[Steven R. Davidson]

Hola Cecilia,

Cecilia Macrini wrote:

> Hola!
> Necesito saber cómo es el código del recorrido en amplitud para árboles 
> binarios en c++.

Daniel ya te ha dado un enlace para que puedas buscar información acerca 
del tema que requieres. Sólo quiero dar una descripción y explicación de 
lo que implica el recorrido en amplitud (level order traversal, en inglés).

Este recorrido visita todos los nodos de un árbol como si fuese una 
lista secuencial. Es decir, recorremos los nodos por cada nivel o 
profundidad. Para implementar esto, lo que debes hacer es usar una cola, 
en la cual vayas metiendo cada nodo del árbol. Cuando sacas el primer 
elemento de la cola, la visitas, y agregas a la cola los nodos hijos 
inmediatos: el hijo izquierdo y luego el derecho. Por ejemplo,

      1
     /  \
    2    3
   / \  / \
  4  5 6   7

Empezamo por el nodo 1 que es agregado a la cola:
cola <- 1

Ahora agregamos sus nodos hijos inmediatos:
cola <- 1, 2, 3

Extraemos el elemento de la cola para hacer algo con ello, resultando en:
cola <- 2, 3

Ahora visitamos el nodo 2, y repetimos el mismo proceso:
cola <- 2, 3, 4, 5

Extraemos y operamos el nodo 2:
cola <- 3, 4, 5

Visitamos el nodo 3, agregando sus nodos hijos:
cola <- 3, 4, 5, 6, 7

Extraemos el nodo 3 y hacemos algo con ello:
cola <- 4, 5, 6, 7

Y así sucesivamente.

El algoritmo viene a ser el siguiente:

Recorrido_Amplitud( Arbol raiz )
1.  Crear una cola: C
2.  C.Agregar( raiz );
3.  Mientras que !C.EstaVacio(), hacer
4.     Nodo n <- C.Mirar()
5.     Si n.izq existe, entonces
6.        C.Agregar( n.izq )
5.     Si n.der existe, entonces
6.        C.Agregar( n.der )
7.     C.Extraer()
8.     HacerAlgo( n )
9.  Terminar


Espero

Steven