Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
作者:DreamLee0625 发布时间:2022-07-06 16:40:59
标签:Python,二叉树,遍历
本文实例讲述了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
0
投稿
猜你喜欢
- 以下是一个类文件,下面的注解是调用类的方法注意:如果系统不支持建立Scripting.FileSystemObject对象,那么数据库压缩功
- 这10个asp处理网页编码转换的函数,不知何时收藏在我的电脑中,今天刚好看到了,拿出来与大家分享,这里各种常见的网页编码问题已经
- 继Go 1.18支持泛型后,Go 将在下个版本中支持pdqsort排序算法再次引起了开发者们的热切讨论。目前,Go仓库的最新commit中提
- 最近无意看到网上有人使用Python编写几十行代码生成图像验证码,感觉很是繁琐,这里为各位朋友推荐两种方法,使用4行Python代码即可生成
- 一、前言近期在实际项目中使用到了PID控制算法,于是就该算法做一总结。二、PID控制算法详解2.1 比例控制算法例子: 假设一个水缸,需要最
- 一、常用文件函数库1、basename(); -- 返回路径中的文件名部分。string basename ( string $path [
- Python的matplotlib包可以轻松的将数据可视化,博主最近遇到了一个问题,博主想同时在两个窗口展示两张图,但是代码运行结果总是显示
- 本文实例讲述了Django框架基础模板标签与filter使用方法。分享给大家供大家参考,具体如下:一、基本的模板语言1、变量{{ }}1.1
- 检测自己当前系统环境中python是否已经安装该module,若未安装请自行安装检测自己的pycharm使用的环境变量是否与当前环境一致若不
- 目录一、任务二、实现(1)导库并创建画布(2)画图形(3)创建按钮和文本框(4)功能实现三、完整代码四、升级—绑定键盘事件总结一、任务用多个
- 在实现算法的时候,通常会从两方面考虑算法的复杂度,即时间复杂度和空间复杂度。顾名思义,时间复杂度用于度量算法的计算工作量,空间复杂度用于度量
- 正在看的ORACLE教程是:ORACLE8的分区管理。摘要:本篇文章介绍了ORACLE数据库的新特性—分区管理,并用例子说明使用方法。 关键
- Sql Server的存储过程是一个被命名的存储在服务器上的Transacation-Sql语句集合,是封装重复性工作的一种方法,它支持用户
- 协程中未处理的异常会向上冒泡,传给 next 函数或 send 方法的调用方(即触发协程的对 象)。下面示例举例说明如何使用之前博客示例中由
- 1、去空格及特殊符号s.strip().lstrip().rstrip(',')2、复制字符串#strcpy(sStr1,s
- 数据的合并与关联是数据处理过程中经常遇到的问题,在SQL、HQL中大家可能都有用到 join、uion all 等 ,在 Pandas 中也
- 本文实例讲述了python递归计算N!的方法。分享给大家供大家参考。具体实现方法如下:def factorial(n): if
- ISSET();——适合于检测是否存在这个参数。 定义和作用范围:用于测试一个变量是否具有值(包括0,FALSE,或者一个空字串,但不能是N
- 翻译:ShiningRay @ Nirvana Studio作者:Douglas Crockford来源:http://www.crockf
- 可以加上时间判断,让程序在固定的时间启动。#coding=utf-8#!/usr/bin/pythonimport osdef open_a