python实现二叉树层序遍历(逐层打印二叉树)「建议收藏」
2023-06-13 09:11:41 时间
大家好,又见面了,我是你们的朋友全栈君。
题目要求
给定一个二叉树,要求从上往下逐层打印该二叉树节点的值,每层从左往右打印。
解题思路——广度优先遍历
实际上就是广度优先遍历, 借助一个队列(这里用数组代替)就可以实现: 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不相等时换到下一行。
缺点:
- 需要辅助结构line/current_line
- 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)
定义的二叉树:
打印结果:
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/143485.html原文链接:https://javaforall.cn
相关文章
- 二级Python选择题_二级python选择题题库
- python常用面试题_Python+Selenium 常见面试题整理[通俗易懂]
- 符合python命名规范的标识符是什么_Python标识符命名规范
- python在线代码编辑器-5种最佳Python IDE和代码编辑器
- python表情代码_Python实现表情包的代码实例[通俗易懂]
- Python 技巧篇-pip卸载python库实例演示,查看pip命令大全方法[通俗易懂]
- 【说站】python多分支结构是什么
- Python自动化办公小程序:实现报表自动化和自动发送到目的邮箱
- python图像多层小波分解_Python中图像小波分解与重构以及灰度图加噪
- python里面的缩进是什么意思_Python缩进规则(一看即懂)[通俗易懂]
- python win32api sendmessage_Python win32api.SendMessage方法代码示例[通俗易懂]
- python 图像处理库_Python图像处理库
- python中的if语句怎么用_iserror函数的使用方法
- pycharm如何调试python程序_Pycharm断点调试Python程序的步骤方法
- opencv(4.5.3)-python(二十)--轮廓属性
- Python教程:IO
- python在windows命令行下输出彩色文字代码详解编程语言
- python计算两个日期相差的天数详解编程语言
- Python collections.OrderedDict解决dict元素顺序问题详解编程语言
- 在Linux上搭建Python开发环境(linux搭建python环境)
- MySQL与Python搭配,实现数据库操作。(mysql-python)
- 使用Python操作MySQL数据库快速上手(python访问mysql数据库)
- 用Python仿写MSSQL 编程体验更有趣(python仿mssql)
- 从 Python 连接到 MySQL:实现更多强大的数据库应用(python和mysql)
- Python操作MySQL数据库的必备模块mysqlpython(mysql_python)