0

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

java中通用树（n-ary树）的级别顺序遍历

谢谢！

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

4

1 回答 1

4

问题是你处理你的根节点两次：你最初将它添加到你的队列中（在行中q.add(n)），然后在你第一次到达之前n = q.poll()处理它，然后你把它从队列中取出并再次处理它。

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

要解决此问题，请删除该行q.add(n)（因为无论如何您都会处理根节点，即使没有它），或者更改此：

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

对此：

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

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

于 2012-10-09T21:05:40.803 回答