按特定格式逐层打印二叉树的广度优先搜索

Question

首先，这个问题并不是那个问题的重复，而是在它的基础上提出的。

以那个问题中的树为例，

    1 
   / \
  2   3
 /   / \
4   5   6

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

1
2 3
4 5 6

而不是一般的

1 
2 
3 
4 
5 
6

我主要想知道最有效的方法是什么——我现在有一种方法是把结果添加到一个列表中，然后再遍历这个列表。更有效的方法可能是在每一层弹出元素时，保存最后一个元素，然后在之后打印一个新行。

有什么想法吗？

Answer 1

我的解决方案和Alex Martelli的有点像，不过我把遍历数据结构的部分和处理数据结构的部分分开了。我把主要的代码放在iterLayers里，这样printByLayer就可以保持简洁明了。

from collections import deque

class Node:
    def __init__(self, val, lc=None, rc=None):
        self.val = val
        self.lc = lc
        self.rc = rc

    def iterLayers(self):
        q = deque()
        q.append(self)
        def layerIterator(layerSize):
            for i in xrange(layerSize):
                n = q.popleft()
                if n.lc: q.append(n.lc)
                if n.rc: q.append(n.rc)
                yield n.val
        while (q):
            yield layerIterator(len(q))

    def printByLayer(self):
        for layer in self.iterLayers():
            print ' '.join([str(v) for v in layer])

root = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))
root.printByLayer()

运行时会打印出以下内容：

1
2 3
4 5 6
7

Answer 2

听起来像是广度优先遍历。

广度优先遍历是用一个队列来实现的。在这里，你只需要在队列里放一个特殊的标记，表示需要打印一个换行符。每当找到这个标记时，就打印一个换行符，然后把这个标记再放回队列的最后面（这就是队列的特点）。

算法开始时，队列里放入根节点，后面跟着这个特殊的换行标记。

Answer 3

一次只处理一个层级，比如：

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 加上一些辅助信息（比如深度或者某一层剩余节点数）要直接得多。

不过，如果你只是往列表中添加元素（而不是“消费”它），那么使用列表的效率要比 deque 高很多。如果你在寻找 C++ 的解决方案，类似地，使用 std::vector 只用 push_back 来构建，然后再用循环来使用它，比 std::deque 更高效。因为所有的生成操作都是先进行的，然后才是遍历（或消费），如果内存非常紧张，一个有趣的替代方案是，还是用列表来表示每个层级，然后在开始消费之前用 .reverse 将它反转（通过 .pop 来取出元素）——我没有大型树结构来进行测量，但我怀疑这种方法仍然会比 deque 更快（而且实际上占用的内存更少），前提是列表的底层实现（或者 std::vector）在调用几次 pop（或者 pop_back）后确实会回收内存——当然，deque 也是同样的假设；-）。