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

Question

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

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

我怎么能这样做。

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

谢谢！

   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

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

score 2 · Accepted Answer

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

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。我更喜欢这种简单性，而不是保留一个完整的单独队列。

上周我在接受微软采访时遇到了这个问题……电话对我来说不太顺利。很高兴你学习它。

score 2 · Accepted Answer

我知道这个问题最简单的解决方案是使用哨兵。队列初始化为根节点，后跟哨兵，然后循环遍历队列：

移除前面的元素
如果是哨兵：
- 我们在关卡的末尾，所以我们可以结束输出行
- 如果队列不为空，则在最后将哨兵推回队列。
如果不是哨兵：
- 打印出来
- 将其所有孩子推入队列。

我不使用 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 << ' ';
    }
  }
}

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

score 1 · Accepted Answer

使用另一个队列来指示深度。下面的代码未经测试，但它应该给你的想法（引入 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);
    }
  }
}

就我的口味而言，与其他方法相比，这种方法更加不言自明。

score 1 · Accepted Answer

我认为我们还需要三个变量。numInCurrentLevel用于跟踪当前级别中的元素数，indexInCurrentLevel用于在当前级别遍历时进行计数，numInNextLevel用于跟踪下一级中的元素数。代码如下：

static void displayBFS(NaryTreeNode root) {

    Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();;
    q.add(root);
    int numInCurrentLevel = 1;
    int numInNextLevel = 0;
    int indexInCurrentLevel=0;

    while(!q.isEmpty()) { 
        NaryTreeNode node = q.poll();
        System.out.print(node.data + " ");
        indexInCurrentLevel++;

        for(NaryTreeNode n : node.nary_list) {
            q.add(n);
            numInNextLevel++;
        }

        //finish traversal in current level
        if(indexInCurrentLevel==numInCurrentLevel) {
            System.out.println();
            numInCurrentLevel=numInNextLevel;
            numInNextLevel=0;           
            indexInCurrentLevel=0;
        }
  } 
}

希望对您有所帮助，我对java编程不太熟悉。

score 0 · Accepted Answer

def printLevelWiseTree(tree):
q= queue.Queue()
if tree == None:
    return None
q.put(tree)
while (not(q.empty())):
    c = q.get()
    print(c.data,end=":")
    for i in range(len(c.children)):
        if i != len(c.children)-1:
            print(c.children[i].data,end=",")
        else:
            print(c.children[i].data,end="")
        q.put(c.children[i])
    print()

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

5 回答 5

Related

Reference