以特定格式按级别顺序打印BFS(二叉树) [英] Printing BFS (Binary Tree) in Level Order with Specific Formatting

问题描述

首先，这个问题不是

To begin with, this question is not a dup of this one, but builds on it.

以该问题中的树为例，

    1 
   / \
  2   3
 /   / \
4   5   6

您将如何修改程序以使其打印出来，

How would you modify your program to print it so,

1
2 3
4 5 6

而不是一般人

1 
2 
3 
4 
5 
6

我基本上是在寻找最有效的方法来直觉-我有一种方法，涉及将结果附加到列表中，然后遍历它.一种更有效的方法可能是在弹出每个级别时存储最后一个元素，然后再打印出新行.

I'm basically looking for intuitions on the most efficient way to do it - I've got a method involving appending the result to a list, and then looping through it. A more efficient way might be to store the last element in each level as it is popped, and print out a new line afterward.

想法?

推荐答案

一次只建立一个级别，例如:

Just build one level at a time, e.g.:

class Node(object):
  def __init__(self, value, left=None, right=None):
    self.value = value
    self.left = left
    self.right = right

def traverse(rootnode):
  thislevel = [rootnode]
  while thislevel:
    nextlevel = list()
    for n in thislevel:
      print n.value,
      if n.left: nextlevel.append(n.left)
      if n.right: nextlevel.append(n.right)
    print
    thislevel = nextlevel

t = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))

traverse(t)

编辑:如果您希望在最大消耗的辅助"内存中少量节省(永远不要在此辅助"内存中同时拥有所有此级别和下一个级别)，则可以当然，请使用 collection.deque 而不是 list ，并在使用时消耗当前级别(通过 popleft )，而不是简单地循环.一次创建一个级别的想法(随着您消耗或迭代前一个级别)保持不变-当您确实需要区分级别时，它比使用单个大双端队列和辅助信息更直接(例如深度或给定级别中剩余的节点数.

Edit: if you're keen to get a small saving in maximum consumed "auxiliary" memory (never having simultaneously all this level and the next level in such "auxiliary" memory), you can of course use collection.deque instead of list, and consume the current level as you go (via popleft) instead of simply looping. The idea of creating one level at a time (as you consume --or iterate on-- the previous one) remains intact -- when you do need to distinguish levels, it's just more direct than using a single big deque plus auxiliary information (such as depth, or number of nodes remaining in a given level).

但是，仅附加到列表(并循环而不是消耗")的列表比双端队列的效率要高得多(如果您使用的是C ++解决方案，则类似地，std :: vector仅使用 push_back 来构建它，然后使用它的循环比std :: deque更有效.由于所有生成都首先发生，然后是所有迭代(或消耗)，因此，一个很有趣的替代方法如果受到严格限制，则无论如何都要使用一个列表来表示每个级别，然后使用 .reverse 在开始使用它之前(通过 .pop 调用)-我周围没有大树可以通过测量进行检查，但是我怀疑这种方法仍然会更快(并且实际上比 deque 消耗的内存少(假设列表[[或std :: vector]]的底层实现实际上在几次调用 pop [[或 pop_back ]] –当然，对于双端队列也有相同的假设；-).

However, a list that is only appended to (and looped on, rather than "consumed") is quite a bit more efficient than a deque (and if you're after C++ solutions, quite similarly, a std::vector using just push_back for building it, and a loop for then using it, is more efficient than a std::deque). Since all the producing happens first, then all the iteration (or consuming), an interesting alternative if memory is tightly constrained might be to use a list anyway to represent each level, then .reverse it before you start consuming it (with .pop calls) -- I don't have large trees around to check by measurement, but I suspect that this approach would still be faster (and actually less memory-consuming) than deque (assuming that the underlying implementation of list [[or std::vector]] actually does recycle memory after a few calls to pop [[or pop_back]] -- and with the same assumption for deque, of course;-).

这篇关于以特定格式按级别顺序打印BFS(二叉树)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！