python实现二叉树层序遍历（逐层打印二叉树）「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

题目要求

给定一个二叉树，要求从上往下逐层打印该二叉树节点的值，每层从左往右打印。

解题思路——广度优先遍历

实际上就是广度优先遍历, 借助一个队列（这里用数组代替）就可以实现:
1、先将root节点加入队列
2、队列不为空时取队列首节点
3、打印节点的值，然后将该节点的左、右子节点先后加入队尾（核心步骤，广度优先体现在这）
4、回到2，直到队列为空

该方法对满二叉树和非满二叉树都符合题目要求。

代码实现

1. 先定义二叉树的类

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

2. 先从打印一行开始

一步一步来，我们先将所有节点的值按层序打印在一行，即每层之间不换行。后面的函数都是基于这个母版进行的改进。

def print_in_one_line(root):
    ''' 1. 简单版： 打印在一行内，不换行 '''
    if not root:
        return 
    queue = []
    queue.append(root)
    while len(queue) > 0:
        node = queue.pop(0)
        print(node.val, end = " ") # end属性默认为“\n”，所以print()函数默认会换行。此处设为空格“ ”，防止自动换行
        if node.left:
            queue.append(node.left) # 将本节点的左子节点入队
        if node.right:
            queue.append(node.right) # 将本节点的右子节点入队

3. 逐行打印——初级

在node入队时候就加入行号信息，然后判断line与current_line是否相等来控制换行，即当line与current_line不相等时换到下一行。

缺点：

1. 需要辅助结构line/current_line
2. node入队时加入的行号信息增加了空间的开销。

def print_by_layer_1(root):
    ''' 2. 逐行打印——初级版： 用line/current_line 控制换行，在入队时候即加入行号信息 '''
    if not root:
        return 
    queue = [] #
    current_line = 0
    queue.append([current_line, root])
    while len(queue) > 0:
        line, node = queue.pop(0)
        # 核心判断：是否换行
        if line != current_line:
            print()  # 不同时换行，print()函数默认end=“\n”
            current_line = line
        print(node.val, end = " ")
        if node.left:
            queue.append([line+1, node.left])  # 将本节点的行号和左子节点入队
        if node.right:
            queue.append([line+1, node.right]) # 将本节点的行号和右子节点入队

4. 逐行打印——高阶

不需要line/current_line来判断，而是在入队时候就加入换行信息，即在每层第一个节点的子左节点入队之前就加入一个换行标记，该换行标记可以自定义，任何非TreeNode对象就行，这里我用字符“r”代替。
注意：控制好边界条件，防止陷入死循环，别问我是怎么知道的。。。

def print_by_layer_2(root):
    ''' 3. 终极版 无line/current_line,在入队时候加入换行标记信息，注意边界条件，防止陷入死循环 '''
    if not root:
        return 
    queue = ["r"] # 一开始塞入一个换行标记，作为队首,任何非TreeNode对象都行。
    queue.append(root)
    while len(queue) > 0:
        node = queue.pop(0)
        if isinstance(node,TreeNode):
            print(node.val, end = " ")
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        else:
            # 边界条件
            if len(queue) > 0:
                queue.append("r") # 对尾添加换行标记
                print()  # 换行

结果验证

好了，接下来看一下函数的表现，我们写了一个主函数：

if __name__ == "__main__":

    # 新建节点 
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)
    node4 = TreeNode(4)
    node5 = TreeNode(5)
    node6 = TreeNode(6)
    node7 = TreeNode(7)
    node8 = TreeNode(8)
    node9 = TreeNode(9)
    node10 = TreeNode(10)
    node11 = TreeNode(11)

    # 构建二叉树
    node1.left, node1.right = node2, node3
    node2.left, node2.right = node4, node5
    node3.left, node3.right = node6, node7
    node4.left, node4.right = node8, node9
    node5.left, node5.right = node10, node11

    # 指定 node1 为root节点
    root = node1

    # 打印
    print("\nprint in one line:")
    print_in_one_line(root)

    print("\n\nprint by layer 1:")
    print_by_layer_1(root)
    
    print("\n\nprint by layer 2:")
    print_by_layer_2(root)

定义的二叉树：

打印结果：