java - 树的层序遍历

Question

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

Level Order traversal of a generic tree(n-ary tree) in java

谢谢!

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)
    {
        ...
    }

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