以特定格式按级别顺序打印BFS（二叉树）

Question

首先，这个问题不是这个问题的重复，而是在此基础上建立的。

以该问题中的树为例，

    1 
   / \
  2   3
 /   / \
4   5   6

您将如何修改程序以进行打印，

1
2 3
4 5 6

而不是一般

1 
2 
3 
4 
5 
6

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

有想法吗？

Answer 1

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

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）进行平移，而不是简单地循环。一次创建一个级别的想法（随着您消耗或迭代前一个级别）保持不变-
当您确实需要区分级别时，它比使用单个大双端队列和辅助信息更直接（例如深度或给定级别中剩余的节点数）。

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