树的水平顺序遍历

Question

为了遍历通用树，我为下面链接中提到的代码编写了以下显示函数。问题是每个级别打印两次。有人能告诉我为什么吗。如果有人需要整个实现，可以在下面的链接中找到没有此函数的原始代码。其他人只需查看下面的displayBFS函数，并告诉我为什么值会重复

java中泛型树（n元树）的级顺序遍历

谢谢

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();
    }  
}

目前的树状结构可供参考：

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

输出：100 90 50 70 90 50 70 20 30 200 300 20 30
200
300

Answer 1

问题是，您需要处理两次根节点：您首先将其添加到队列中（在行q.add（n）中），然后在第一次到达n=q.poll（）之前处理它，然后将其从队列中取出并再次处理。

其他的一切都是正确的，这就是为什么每个非根节点只得到两个副本：加倍只在根节点发生一次。

要解决这个问题，要么删除行q.add（n）（因为您无论如何都要处理根节点，即使没有它），或者更改以下内容：

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

对此：

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

这样，您就不会在最初的额外时间内处理根节点。