Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
作者:DreamLee0625 时间:2022-07-06 16:40:59
本文实例讲述了Python二叉树的遍历操作。分享给大家供大家参考,具体如下:
# coding:utf-8
"""
@ encoding: utf-8
@ author: lixiang
@ email: lixiang_cn@foxmail.com
@ python_version: 2
@ time: 2018/4/11 0:09
@ more_info:
二叉树是有限个元素的集合,该集合或者为空、或者有一个称为根节点(root)的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。
1 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。
2 二叉树的第i层至多有2^{i-1}个结点
3 深度为k的二叉树至多有2^k-1个结点;
4 对任何一棵二叉树T,如果其终端结点数为N0,度为2的结点数为N2,则N0=N2+1
5 度是二叉树分支树,对于二叉树而言有0,1,2三种取值
不管是前中后序遍历,都是在当前规则下,无路可走时,输出根结点。
"""
class TreeNode(object):
def __init__(self, x, left=None, right=None):
self.val = x
self.left = left
self.right = right
def pre_traverse(root):
"""
根左右
:param root:
:return:
"""
if not root:
return
print root.val,
pre_traverse(root.left)
pre_traverse(root.right)
def mid_travese(root):
"""
左根右
:param root:
:return:
"""
if not root:
return
mid_travese(root.left)
print root.val,
mid_travese(root.right)
def after_travese(root):
"""
左右根
:param root:
:return:
"""
if not root:
return
after_travese(root.left)
after_travese(root.right)
print root.val,
def level_travese(root):
if not root:
return
queue = []
queue.append(root)
while queue:
cur = queue.pop(0)
print cur.val,
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
def depth(root):
if not root:
return 0
left = depth(root.left)
right = depth(root.right)
return max(left, right) + 1
if __name__ == '__main__':
"""
tree是一个表示树根节点的对象
前序遍历 1 2 4 5 8 9 11 3 6 7 10
中序遍历 4 2 8 5 11 9 1 6 3 10 7
后序遍历 4 8 11 9 5 2 6 10 7 3 1
层序遍历 1 2 3 4 5 6 7 8 9 10 11
深度 5
"""
tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5, TreeNode(8), TreeNode(9, left=TreeNode(11)))), TreeNode(3, TreeNode(6), TreeNode(7, left=TreeNode(10))))
print("\n前序遍历")
pre_traverse(tree)
print("\n中序遍历")
mid_travese(tree)
print("\n后序遍历")
after_travese(tree)
print("\n层序遍历")
level_travese(tree)
print("\n深度")
print(depth(tree))
运行结果:
前序遍历
1 2 4 5 8 9 11 3 6 7 10
中序遍历
4 2 8 5 11 9 1 6 3 10 7
后序遍历
4 8 11 9 5 2 6 10 7 3 1
层序遍历
1 2 3 4 5 6 7 8 9 10 11
深度
5
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/vitaminc4/article/details/80964955
标签:Python,二叉树,遍历
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python中http请求方法库汇总
2021-04-28 10:26:21
Python闭包执行时值的传递方式实例分析
2021-09-22 14:43:50
php编程每天必学之表单验证
2023-07-19 05:50:59
加密SQL Anywhere 提升政府行业数据安全
2008-12-03 15:25:00
256种编程语言大汇总
2023-05-30 19:06:01
js键盘事件全面控制
2008-02-21 12:51:00
利用Python将list列表写入文件并读取的方法汇总
2023-12-07 13:40:07
![](https://img.aspxhome.com/file/2023/4/95164_0s.png)
ubuntu下mysql版本升级到5.7
2024-01-13 11:10:00
python logging模块的分文件存放详析
2023-04-02 20:27:32
![](https://img.aspxhome.com/file/2023/8/97538_0s.png)
django实现支付宝支付实例讲解
2023-08-27 04:45:44
![](https://img.aspxhome.com/file/2023/1/62551_0s.png)
Python中的数据可视化matplotlib与绘图库模块
2021-08-09 06:02:09
![](https://img.aspxhome.com/file/2023/1/101161_0s.png)
GoFrame错误处理常用方法及错误码使用示例
2024-04-25 15:30:35
如何使用Python破解ZIP或RAR压缩文件密码
2022-03-24 19:28:45
![](https://img.aspxhome.com/file/2023/5/92055_0s.png)
Python的批量远程管理和部署工具Fabric用法实例
2022-01-06 08:28:30
Python使用struct库的用法小结
2023-04-29 18:42:53
python实现高精度求自然常数e过程详解
2023-12-01 05:21:51
![](https://img.aspxhome.com/file/2023/8/109928_0s.png)
MySQL大小写敏感导致的问题分析
2024-01-17 05:41:12
![](https://img.aspxhome.com/file/2023/7/65707_0s.png)
Python操作CSV格式文件的方法大全
2023-07-08 18:57:45
![](https://img.aspxhome.com/file/2023/8/71488_0s.png)
Golang 实现 Redis系列(六)如何实现 pipeline 模式的 redis 客户端
2024-05-13 10:44:23
scrollWidth,clientWidth,offsetWidth的区别
2024-04-22 22:29:00
![](https://img.aspxhome.com/file/2023/0/135710_0s.png)