java - programar - Nivel de orden Recorrido de un árbol

recorrido de un arbol matematicas discretas

Question

Con el fin de hacer un recorrido de nivel (BFS) de un árbol genérico, escribí la siguiente función de visualización para el código mencionado en el siguiente enlace. El problema es que cada nivel se imprime dos veces. ¿Puede alguien decirme por qué? El código original sin esta función se puede encontrar en el siguiente enlace en caso de que alguien necesite la implementación completa, solo mire la función de displayBFS a continuación y dígame por qué se repiten los valores.

Recorrido de orden de nivel de un árbol genérico (árbol n-ary) en java

¡Gracias!

void displayBFS(NaryTreeNode n)
{
    Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();

    if(n!=null)
    {
        q.add(n);
        System.out.println(n.data);
    }

    while(n!=null)
    {
        for(NaryTreeNode x:n.nary_list)
        {
            q.add(x);
            System.out.println(x.data );
        }        
        n =  q.poll();
    }  
}

Estructura de árbol actual para referencia:

     root(100)
    /      |       /
  90       50       70
  /        /
20 30   200  300

Salida: 100 90 50 70 90 50 70 20 30 200 300 20 30
200
300

Answer 1

El problema es que procesa su nodo raíz dos veces: inicialmente lo agrega a su cola (en la línea q.add(n) ), luego lo procesa antes de llegar a n = q.poll() , y luego lo saca de la cola y lo procesa nuevamente.

Todo lo demás es correcto, y es por eso que solo obtienes dos copias de cada nodo no raíz: la duplicación solo se produce una vez, en la raíz.

Para solucionar esto, elimine la línea q.add(n) (ya que procesa el nodo raíz de todos modos, incluso sin él), o cambie esto:

    while(n!=null)
    {
        ...
        n =  q.poll();
    }

a esto:

    while((n = q.poll()) != null)
    {
        ...
    }

para que no procese el nodo raíz ese tiempo extra inicial.