树的等级序遍历

问题描述

为了做一个普通的树我写了下面的显示功能，在下面的链接中提到的code级顺序（BFS）遍历。的问题是，每个级别被印刷两次。谁能告诉我为什么。如果没有这个功能原来的code可在下面，以防有人链接中找到所需要的整个实施其他人只是看看下面的displayBFS功能，告诉我为什么值重复

In order to do level order(BFS) traversal of a generic tree I wrote the following display function for the code mentioned in the link below. The problem is that each level is printed twice. Can someone tell me why.Original Code without this function can be found in the link below in case someone need the entire implementation else just look at the displayBFS function below and tell me why are values repeating

Level在java中一个通用的树（N叉树）中序遍历

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

仅供参考当前树结构：

Current Tree Structure for reference:

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

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

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

推荐答案

现在的问题是，你处理你的根节点两次：你最初把它添加到您的队列（在该行 q.add（ N）），那么你处理它的在的你第一次到 N = q.poll（），然后你得到它的队列，并再次对其进行处理。

The problem is that you process your root-node twice: you initially add it to your queue (in the line q.add(n)), then you process it before you first get to n = q.poll(), and then you get it off the queue and process it again.

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

Everything else is correct, which is why you only get two copies of each non-root node: the doubling only occurs once, at root.

要解决这个问题，要么删除行 q.add（N）（因为你无论如何处理根节点，即使没有的话），或者改变这样的：

To fix this, either remove the line q.add(n) (since you process the root node anyway, even without it), or else change this:

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

这样：

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

让你不处理根节点，最初的额外时间。

so that you don't process the root node that initial extra time.

这篇关于树的等级序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！