Python二叉树定义与遍历方法实例分析
作者:止语--- 发布时间:2023-06-26 17:26:56
本文实例讲述了Python二叉树定义与遍历方法。分享给大家供大家参考,具体如下:
二叉树基本概述:
二叉树是有限个元素的几个,如果为空则为空二叉树,或者有一个结点称之为根节点,分列根节点两侧的为二叉树的左右子节点,二叉树有如下的性质:
1. 二叉树的每个结点不存在度大于2的结点
2. 二叉树的第i层至多有2^{i-1}个结点
3. 深度为k的二叉树至多有2^k - 1个结点
4. 二叉树中,度为0的结点数N0比度为2的结点数N2大1,即存在N2 + 1 = N0
Python代码:
#coding:utf-8
'BiTree'
class Node(object):
'Node Defination'
def __init__(self,item):
self.item = item
self.left = None
self.right = None
class Tree(object):
'Bitree Defination'
def __init__(self):
self.root = None
def add(self,item):
node = Node(item)
if self.root is None:
self.root = node
else:
q = [self.root]
while True:
pop_node = q.pop(0)
if pop_node.left is None:
pop_node.left = node
return
elif pop_node.right is None:
pop_node.right = node
return
else:
q.append(pop_node.left)
q.append(pop_node.right)
def traverse(self):#层次遍历
if self.root is None:
return None
q = [self.root]
res = [self.root.item]
while q != []:
pop_node = q.pop(0)
if pop_node.left is not None:
q.append(pop_node.left)
res.append(pop_node.left.item)
if pop_node.right is not None:
q.append(pop_node.right)
res.append(pop_node.right.item)
return res
def preorder(self,root): #先序遍历
if root is None:
return []
result = [root.item]
left_item = self.preorder(root.left)
right_item = self.preorder(root.right)
return result + left_item + right_item
def inorder(self,root): #中序遍历
if root is None:
return []
result = [root.item]
left_item = self.inorder(root.left)
right_item = self.inorder(root.right)
return left_item + result + right_item
def postorder(self,root): #后序遍历
if root is None:
return []
result = [root.item]
left_item = self.postorder(root.left)
right_item = self.postorder(root.right)
return left_item + right_item + result
if __name__=='__main__':
t = Tree()
for i in range(10):
t.add(i)
print "层序遍历:",t.traverse()
print "先序遍历:",t.preorder(t.root)
print "中序遍历:",t.inorder(t.root)
print "后序遍历:",t.postorder(t.root)
输出结果:
层序遍历: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
先序遍历: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
中序遍历: [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
后序遍历: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]
这里对于
if __name__=='__main__':
“Make a script both importable and executable”
意思就是说让你写的脚本模块既可以导入到别的模块中用,另外该模块自己也可执行。
这里通过一个示例进行解释:
#test.py
def func():
print "we are in %s"%__name__
if __name__ == '__main__':
func()
输出结果:
we are in __main__
说明if语句中的内容被执行了,调用了 func()
函数,现在在另一个模块中调用func函数
#testtest
from test import func
func()
输出结果:
we are in moudle
也就是说 if 条件中的内容没有执行。
总结:
如果直接执行某个*.py文件,该文件中 if __name__ == '__main__'
是True,相当于调式本模块的代码;如果是从另一个模块(testtest.py)通过import导入该文件的时候,这时__name__就是这个模块的名字(test)而不是__main__,总之在调式代码的时候加上 if __name__ == '__main__'
中加入调试代码,可以让步模块调用的时候不执行调式代码,如果想排查本模块代码的问题时,直接进行调试执行
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/rhx_qiuzhi/article/details/80149026
猜你喜欢
- ''推拉门''动效也可以称作"手风琴"效果,大多数效果实现的思路基本是一样的,下面介绍两
- 1. 横排往下会影响阅读速度。如12345678的单排单列数字,肯定是竖排阅读快。但多行多列的整块信息,横排并不见得就比竖排慢,比如所有简体
- 要是XHTML与CSS能面向对象。。太阳应该从北边升起了。但是,凡事都应该带着OO的思想来看问题,也勉强可以凑数拉。其实,早在零几年就有人提
- 三种遍历列表里面序号和值的方法:最近学习python这门语言,感觉到其对自己的工作效率有很大的提升,特在情人节这一天写下了这篇博客,下面废话
- 许多游戏玩家一定会对游戏中的动态鼠标指针有很深的印象,其实只要一句简单的CSS(层叠样式表),你也能在网页上实现这种效果。首先,你需要一个鼠
- SQL Server会把经常使用到的数据缓存在内存里(就是数据页缓存),用以提高数据访问速度。因为磁盘访问速度远远低于内存,所以减少磁盘访问
- rss的优点 1.您可以有选择地浏览您感兴趣的以及与您的工作相关的新闻。 2.您可以把需要的信息从不需要的信息(兜售信息,垃圾邮件等)中分离
- 行业首页改版的缘故,为了让我们设计师可以更好的了解需求、了解我们的用户,和部门的用研童鞋一起讨论决定使用电话来进行用户访谈,以此来了解用户。
- 这篇文章主要介绍了Python三元运算与lambda表达式实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价
- insert into(列名) select 列名 from 表名 where 条件 --不创建表,只复制表数据 select 列名 int
- 本文实例讲述了PHP5.6读写excel表格文件操作。分享给大家供大家参考,具体如下:测试环境:php5.6.24.这块没啥兼容问题。需要更
- 该语句的作用是:启用或禁用错误处理程序。一般用法如下:On Error Resume NextOn Error GoTo 0如果在您的代码中
- bbssend.asp'寻呼台页面,向在线网友发送寻呼信息<%@ Language=VBScript %&
- 一、Ajax简介Ajax被认为是(Asynchronous JavaScript and XML)的缩写,允许浏览器与服务器通信而无需刷新当
- 前言python中图像处理相关库有很多,这里简单介绍PIL、cv2、scipy.imageio 、matplotlib.image、skim
- 使用Python爬虫登录系统之后,能够实现的操作就多了很多,下面大致介绍下如何使用Python模拟登录。我们都知道,在前端的加密验证,只要把
- 开门见山自动化测试过程中,一般测试结果都会以邮件的形式发送给相关人员,那么,在Python中,如何编写代码将邮件发送给对应的用户?同时,发送
- 首先,我们先来看看,如果是人正常的行为,是如何获取网页内容的。(1)打开浏览器,输入URL,打开源网页(2)选取我们想要的内容,包括标题,作
- 第一章:霍夫变换检测圆① 实例演示1这个是设定半径范围 0-50 后的效果。② 实例演示2这个是设定半径范围 50-70 后的效果,因为原图
- 本文通过实际业务系统中调整的一个案例,试图给出一个常见CPU消耗问题的一个诊断方法.大多数情况下,系统的性能问题都是由不良SQL代码引起的,