通用树的级别顺序树遍历，逐级显示树

Question

我想逐级显示树结构。我当前的代码执行BFS或级别顺序遍历，但我无法使输出像树一样显示树结构。请参阅当前输出和预期输出。

我的想法是使用某种计数来迭代队列中同一级别的元素。

我怎么能这样做呢。

没有此功能的原始代码可以在下面的链接中找到，以防有人需要整个实现，否则只需查看下面的显示BFS功能。

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

谢谢

   void displayBFS(NaryTreeNode n)
   {
      Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();
      System.out.println(n.data);

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

Current Tree Structure for reference:

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


    Current Output:
        100
        90 50 70
        20 30
        200 300

    Expected Output
        100
        90 50 70
        20 30 200 300    

另外，我之前发布了一个具有相同功能的逻辑问题，因为已经回答了这个问题，并且当前的问题与另一个问题相关，我发布了一个新问题，这种方法可以吗，或者我应该编辑前面的问题，而不是打开一个新问题？

Answer 1

使用另一个队列指示深度。下面的代码未经测试，但它应该能让您了解这一点（引入sep变量是为了避免尾随空格）：

void displayBFS(NaryTreeNode n) {
  Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();
  Queue<Integer> depth  = new LinkedList<Integer>();
  q.add(n);
  depth.add(0);

  String sep = "";
  int oldDepth = 0

  while(!q.isEmpty()) {
    NaryTreeNode currN = q.poll();
    int currDepth = depth.poll();
    if (currDepth > oldDepth) {
      System.out.println();
      oldDepth = currDepth;
      sep = "";
    }
    System.out.print(sep + currN.data);
    sep = " ";

    for(NaryTreeNode x : currN.nary_list) {
      q.add(x);
      depth.add(currDepth + 1);
    }
  }
}

在我看来，与其他方法相比，这种方法更不言自明。

Answer 2

我所知道的解决这个问题的最简单方法是使用哨兵。使用根节点和sentinel初始化队列，然后在队列中循环：

• 删除前元素
• 如果是哨兵：
  • 我们在一个关卡的末尾，所以我们可以结束输出行
  • 如果队列不是空的，将哨兵推回到队列的最后。
  • 打印出来

  我不使用Java，但我有一些用于深度感知BFS的C代码，我将其剥离以执行此打印任务：

  void show_tree_by_levels(std::ostream& os, Node* tree) {
    Node* sentinel = new Node;
    std::deque<Node*> queue{tree, sentinel};
    while (true) {
      Node* here = queue.front();
      queue.pop_front();
      if (here == sentinel) {
        os << std::endl;
        if (queue.empty())
          break;
        else
          queue.push_back(sentinel);
      } else {
        for (Node* child = here->child; child; child = child->sibling)
          queue.push_back(child);
        os << here->value << ' ';
      }
    }
  }
  

  请注意，我更喜欢使用双指针解决方案（第一个子/下一个子），因为它通常比嵌入列表更简单。YMMV。

Answer 3

只需要跟踪当前级别和下一级别。

static void displayBFS(NaryTreeNode root) {
    int curlevel = 1;
    int nextlevel = 0;

    LinkedList<NaryTreeNode> queue = new LinkedList<NaryTreeNode>();
    queue.add(root);

    while(!queue.isEmpty()) { 
        NaryTreeNode node = queue.remove(0);

        if (curlevel == 0) {
            System.out.println();
            curlevel = nextlevel;
            nextlevel = 0;
        }

        for(NaryTreeNode n : node.nary_list) {
            queue.addLast(n);
            nextlevel++;
        }

        curlevel--;
        System.out.print(node.data + " ");
    } 
}

切换级别时，将nextlevel替换为currentlevel并重置nextlevel。我更喜欢这样简单，而不是保持一个完整的单独队列。

上周我在接受微软的采访时问了这个问题。。。我在电话里感觉不太好。谢谢你学习它。