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

Question

首先，这个问题不是this one的重复，而是建立在它之上的。

以那棵树为例

    1 
   / \
  2   3
 /   / \
4   5   6

你如何修改你的程序来打印它

1
2 3
4 5 6

而不是将军

1 
2 
3 
4 
5 
6

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

有什么想法？

Answer 1

对我来说好像是breadth-first traversal。

广度优先遍历是用queue实现的。在这里，只需在队列中插入一个特殊的标记，指示必须打印换行符。每次找到令牌时，打印一个新行并将令牌重新插入到队列中（在末尾——这是队列的定义）。

使用一个包含根和特殊换行标记的队列启动算法。

Answer 2

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

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），而不是简单的循环。一次创建一个级别的想法（当您使用或迭代前一个级别时）仍然保持不变——当您确实需要区分级别时，这比使用单个大deque加上辅助信息（例如深度或给定级别中的节点数）更直接。

但是，只附加到（并且循环，而不是“消耗”）的列表比DEQE效率要高一些（如果您在C++解决方案之后，同样地，使用仅使用{{CD4}}来构建它的STD:：向量，然后使用它，则比STD::DEQE更有效。由于所有的产生都是首先发生的，然后是所有的迭代（或消耗），如果内存受到严格的限制，一个有趣的替代方法可能是无论如何使用一个列表来表示每个级别，然后在开始使用它之前（使用.pop调用）--我没有大的树来进行度量检查，但我怀疑这种方法仍然比deque（假设list[[或std：：vector]]的底层实现在对pop[[或pop_back]]进行几次调用后实际回收内存更快（而且实际消耗的内存更少），当然，对deque也有同样的假设；-）。

Answer 3

这是广度优先搜索，因此您可以使用队列并以简单紧凑的方式递归执行此操作。。。

# built-in data structure we can use as a queue
from collections import deque

def print_level_order(head, queue = deque()):
    if head is None:
        return
    print head.data
    [queue.append(node) for node in [head.left, head.right] if node]
    if queue:
        print_level_order(queue.popleft(), queue)