2023年6月22日发(作者：)

python实现⼆叉树层序遍历（逐层打印⼆叉树）题⽬要求给定⼀个⼆叉树，要求从上往下逐层打印该⼆叉树节点的值，每层从左往右打印。解题思路——⼴度优先遍历实际上就是⼴度优先遍历, 借助⼀个队列（这⾥⽤数组代替）就可以实现:1、先将root节点加⼊队列2、队列不为空时取队列⾸节点3、打印节点的值，然后将该节点的左、右⼦节点先后加⼊队尾（核⼼步骤，⼴度优先体现在这）4、回到2，直到队列为空该⽅法对满⼆叉树和⾮满⼆叉树都符合题⽬要求。代码实现1. 先定义⼆叉树的类class TreeNode: def __init__(self, value): = value = None = None2. 先从打印⼀⾏开始⼀步⼀步来，我们先将所有节点的值按层序打印在⼀⾏，即每层之间不换⾏。后⾯的函数都是基于这个母版进⾏的改进。def print_in_one_line(root): ''' 1. 简单版： 打印在⼀⾏内，不换⾏ ''' if not root: return

queue = [] (root) while len(queue) > 0: node = (0) print(, end = " ") # end属性默认为“n”，所以print()函数默认会换⾏。此处设为空格“ ”，防⽌⾃动换⾏ if : () #

将本节点的左⼦节点⼊队 if : () #

将本节点的右⼦节点⼊队3. 逐⾏打印——初级在node⼊队时候就加⼊⾏号信息，然后判断line与current_line是否相等来控制换⾏，即当line与current_line不相等时换到下⼀⾏。缺点：1. 需要辅助结构line/current_line2. node⼊队时加⼊的⾏号信息增加了空间的开销。def print_by_layer_1(root): '''

2. 逐⾏打印——初级版： ⽤line/current_line 控制换⾏，在⼊队时候即加⼊⾏号信息 ''' if not root: return

queue = [] # current_line = 0 ([current_line, root]) while len(queue) > 0: line, node = (0) #

核⼼判断：是否换⾏ if line != current_line: print() #

不同时换⾏，print()函数默认end=“n” current_line = line print(, end = " ") if : ([line+1, ]) #

将本节点的⾏号和左⼦节点⼊队 if : ([line+1, ]) #

将本节点的⾏号和右⼦节点⼊队4. 逐⾏打印——⾼阶不需要line/current_line来判断，⽽是在⼊队时候就加⼊换⾏信息，即在每层第⼀个节点的⼦左节点⼊队之前就加⼊⼀个换⾏标记，该换⾏标记可以⾃定义，任何⾮TreeNode对象就⾏，这⾥我⽤字符“r”代替。注意：控制好边界条件，防⽌陷⼊死循环，别问我是怎么知道的。。。def print_by_layer_2(root): '''

3. 终极版 ⽆line/current_line,在⼊队时候加⼊换⾏标记信息，注意边界条件，防⽌陷⼊死循环 ''' if not root: return

queue = ["r"] #

⼀开始塞⼊⼀个换⾏标记，作为队⾸,任何⾮TreeNode对象都⾏。 (root) while len(queue) > 0: node = (0) if isinstance(node,TreeNode): print(, end = " ") if : () if : () else: #

边界条件 if len(queue) > 0: ("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) #

构建⼆叉树 , = node2, node3 , = node4, node5 , = node6, node7 , = node8, node9 , = node10, node11 #

指定 node1

为root节点 root = node1 #

打印 print("nprint in one line:") print_in_one_line(root) print("nnprint by layer 1:") print_by_layer_1(root)

print("nnprint by layer 2:") print_by_layer_2(root)定义的⼆叉树：打印结果：