python实现二叉树层序遍历（逐层打印二叉树）

╰+攻爆jí腚メ 2022-02-22 12:46 228阅读 0赞

### 题目要求 ###

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

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

实际上就是广度优先遍历, 借助一个队列（这里用数组代替）就可以实现:  
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)

定义的二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDExNjA3_size_16_color_FFFFFF_t_70]  
打印结果：  
![在这里插入图片描述][20190409115606268.PNG]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDExNjA3_size_16_color_FFFFFF_t_70]: /images/20220222/f6d674a4857942c8b1c44943168ca5b2.png
[20190409115606268.PNG]: /images/20220222/0d1d90aaf2d34eb4b6cf2488e1e06531.png