问题：实现一个函数，输入二叉树，从上往下打印出二叉树的每个结点，同一层的结点按从左到右的顺序打印。

这道题有别于前序、中序、后序遍历二叉树的方法，该题是按层遍历二叉树。

原理：

不难理解，使用一个辅助空间，FIFO容器可以解决该问题。当遍历根结点后，分别把根结点的左右子树的根结点放到队列容器中。由于队列有FIFO特性，下次从队列中取出的元素一定是左子树的根结点。类似地，左子树的根结点的孩子元素也在遍历时放到队列中…以此类推。队列确保元素按层次排序。

实现：

先实现一个简单的队列做容器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Queue:
    
    def __init__(self):
        self._q = []

    def put(self, item):
        self._q.append(item)

    def get(self):
        item = self._q[0]
        del self._q[0]
        return item

    def empty(self):
        return len(self._q) == 0

建立一颗二叉树，用于做测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def __repr__(self):
        return "Node<{}>".format(self.value)

root = Node(8)
root.left = Node(6)
root.right = Node(10)

root.left.left = Node(5)
root.left.right = Node(7)

root.right.left = Node(9)
root.right.right = Node(11)

实现按层遍历二叉树函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
def print_tree_from_top_to_bottom(root):
    queue = Queue()
    queue.put(root)
    while not queue.empty():
        node = queue.get()
        print(node)
        if node.left:
            queue.put(node.left)
        if node.right:
            queue.put(node.right)

if __name__ == '__main__':
    print_tree_from_top_to_bottom(root)

输出结果：

1
2
3
4
5
6
7
Node<8>
Node<6>
Node<10>
Node<5>
Node<7>
Node<9>
Node<11>

如果打印的输出形式也是分层，我们稍作处理即可。

如果我们需要树一其自身结构分层打印，可以做如下处理。通过标记层的结点数可以解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import collections

def print_tree_step(tree):
    stack = collections.deque()
    stack.append(tree)
    next_level_count = 0
    current_print_count = 1

    while len(stack):
        p_node = stack.popleft()
        print(p_node, end='\t')
        current_print_count -= 1
        if p_node.left is not None:
            next_level_count += 1
            stack.append(p_node.left)
        if p_node.right is not None:
            next_level_count += 1
            stack.append(p_node.right)
        if current_print_count == 0:
            current_print_count = next_level_count
            next_level_count = 0
            print('\n')

这正是我们期待的结果。

启发地，如果要建立一颗二叉树，根据输入序列，按层级建立：从上往下，从左到右。也用类似的思路。