Python编程实现二叉树及七种遍历方法详解
作者:九茶 发布时间:2022-10-31 13:28:28
标签:Python,二叉树,遍历
本文实例讲述了Python实现二叉树及遍历方法。分享给大家供大家参考,具体如下:
介绍:
树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树、FP-树。另外可以用来提高编码效率,如哈弗曼树。
代码:
用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结。实现功能:
① 树的构造
② 递归实现先序遍历、中序遍历、后序遍历
③ 堆栈实现先序遍历、中序遍历、后序遍历
④ 队列实现层次遍历
#coding=utf-8
class Node(object):
"""节点类"""
def __init__(self, elem=-1, lchild=None, rchild=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
class Tree(object):
"""树类"""
def __init__(self):
self.root = Node()
self.myQueue = []
def add(self, elem):
"""为树添加节点"""
node = Node(elem)
if self.root.elem == -1: # 如果树是空的,则对根节点赋值
self.root = node
self.myQueue.append(self.root)
else:
treeNode = self.myQueue[0] # 此结点的子树还没有齐。
if treeNode.lchild == None:
treeNode.lchild = node
self.myQueue.append(treeNode.lchild)
else:
treeNode.rchild = node
self.myQueue.append(treeNode.rchild)
self.myQueue.pop(0) # 如果该结点存在右子树,将此结点丢弃。
def front_digui(self, root):
"""利用递归实现树的先序遍历"""
if root == None:
return
print root.elem,
self.front_digui(root.lchild)
self.front_digui(root.rchild)
def middle_digui(self, root):
"""利用递归实现树的中序遍历"""
if root == None:
return
self.middle_digui(root.lchild)
print root.elem,
self.middle_digui(root.rchild)
def later_digui(self, root):
"""利用递归实现树的后序遍历"""
if root == None:
return
self.later_digui(root.lchild)
self.later_digui(root.rchild)
print root.elem,
def front_stack(self, root):
"""利用堆栈实现树的先序遍历"""
if root == None:
return
myStack = []
node = root
while node or myStack:
while node: #从根节点开始,一直找它的左子树
print node.elem,
myStack.append(node)
node = node.lchild
node = myStack.pop() #while结束表示当前节点node为空,即前一个节点没有左子树了
node = node.rchild #开始查看它的右子树
def middle_stack(self, root):
"""利用堆栈实现树的中序遍历"""
if root == None:
return
myStack = []
node = root
while node or myStack:
while node: #从根节点开始,一直找它的左子树
myStack.append(node)
node = node.lchild
node = myStack.pop() #while结束表示当前节点node为空,即前一个节点没有左子树了
print node.elem,
node = node.rchild #开始查看它的右子树
def later_stack(self, root):
"""利用堆栈实现树的后序遍历"""
if root == None:
return
myStack1 = []
myStack2 = []
node = root
myStack1.append(node)
while myStack1: #这个while循环的功能是找出后序遍历的逆序,存在myStack2里面
node = myStack1.pop()
if node.lchild:
myStack1.append(node.lchild)
if node.rchild:
myStack1.append(node.rchild)
myStack2.append(node)
while myStack2: #将myStack2中的元素出栈,即为后序遍历次序
print myStack2.pop().elem,
def level_queue(self, root):
"""利用队列实现树的层次遍历"""
if root == None:
return
myQueue = []
node = root
myQueue.append(node)
while myQueue:
node = myQueue.pop(0)
print node.elem,
if node.lchild != None:
myQueue.append(node.lchild)
if node.rchild != None:
myQueue.append(node.rchild)
if __name__ == '__main__':
"""主函数"""
elems = range(10) #生成十个数据作为树节点
tree = Tree() #新建一个树对象
for elem in elems:
tree.add(elem) #逐个添加树的节点
print '队列实现层次遍历:'
tree.level_queue(tree.root)
print '\n\n递归实现先序遍历:'
tree.front_digui(tree.root)
print '\n递归实现中序遍历:'
tree.middle_digui(tree.root)
print '\n递归实现后序遍历:'
tree.later_digui(tree.root)
print '\n\n堆栈实现先序遍历:'
tree.front_stack(tree.root)
print '\n堆栈实现中序遍历:'
tree.middle_stack(tree.root)
print '\n堆栈实现后序遍历:'
tree.later_stack(tree.root)
总结:
树的遍历主要有两种,一种是深度优先遍历,像前序、中序、后序;另一种是广度优先遍历,像层次遍历。在树结构中两者的区别还不是非常明显,但从树扩展到有向图,到无向图的时候,深度优先搜索和广度优先搜索的效率和作用还是有很大不同的。
深度优先一般用递归,广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
我印象中是有递归构造树的方法,却一直想不出该怎么构造。后来仔细想了一下,递归思想有点类似深度优先算法,而树的构造应该是广度优先的。如果用递归的话一定要有个终止条件,例如规定树深等。不然构造出来的树会偏向左单子树或者右单子树。所以一般树的构造还是应该用队列比较好。
以上说的不够严谨,有错误之处,欢迎指正!
希望本文所述对大家Python程序设计有所帮助。
0
投稿
猜你喜欢
- 在MySQL数据库中导出整个数据库:1.导出整个数据库mysqldump -u 用户名 -p 数据库名 > 导出的文件名mysqldu
- 就MySQL而言,大多数程序员都不太了解其设计背景,因此当他们尝试创建自己的数据库时,会留下很多漏洞。要想为MySQL数据库进行合适的配置,
- 背景客户最近有这样的需求,想通过统计Oracle数据库活跃会话数,并记录在案,利用比对历史的活跃会话的方式,实现对系统整体用户并发量有大概的
- ASP 组件 FILE对象当前,基于浏览器/服务器模式的应用比较流行。当用户需要将文件传输到服务器上时,常用方法之一是运行FTP服务器并将每
- 代码如下:<% Randomize Do While Len(pass)<12 
- CSS是制作网页效果必不可少的东西,字体的颜色定义、表格的样式定义、图片的特效等等都少不了它。但在Dr
- 前言:由于使用Django框架来做网站,需要动态显示数据库内的信息,所以读取数据库必须要做,写此博文来记录。接下来分两步来做这个事,添加网页
- 异步编程带来的问题在客户端Javascript中并不明显,但随着服务器端Javascript越来越广的被使用,大量的异步IO操作使得该问题变
- 为了把事情变成简单化,我在多个Oracle数据上建立统一的检查数据库账户,并且账户只能访问特定的几个视图(需要查询的sql已生成视图),具体
- 本文实例讲述了php中fgetcsv()函数用法。分享给大家供大家参考。具体方法如下:fgetcsv是一个简单的生成excel文档的函数,从
- 围绕文字、符号、链接三个方面,主要是中文,草拟的个人行文经验:1. 文字避免写错。应付挑剔的读者是一个方面,某些关键词的错误,有可能就避过了
- 继续Mootools常用方法扩展,依然还是String类的扩展。方法:unescapseHTML说明:这个上次忘了,和escapseHTML
- 在讲爬取淘宝详情页数据之前,先来介绍一款 Chrome 插件:Toggle JavaScript (它可以选择让网页是否显示 js 动态加载
- 有一次去超市换货,本能的找到服务中心,服务中心说这个业务在超市旁边一个房间里,由于忘记带小票,那个小房间的人让我去另外一个小房间调电脑里的记
- python可以方便地支持多线程。可以快速创建线程、互斥锁、信号量等等元素,支持线程读写同步互斥。美中不足的是,python的运行在pyth
- 本文实例讲述了JS实现仿Windows经典风格的选项卡Tab切换代码。分享给大家供大家参考,具体如下:这款仿Windows风格的选项卡,带有
- 1. Numpy(Numberical Python)Anaconda中已经集成了NumPy,可以直接使用。如果想要自行安装的话,可以使用流
- 经常看见MOP上有人贴那种动态的图片,就是把一个字符串作为参数传给一个 * 页,就会生成一个带有这个字符串的图片,这个叫做文字水印。像什么原
- 尽管可能是个比较老的话题了,但是我还是从来没有整理过。今天在《精通HTML》一书中看到,这里整理一下。在XHTML中,<html>
- 我们知道在PHP4里面,当我们使用一个类的时候,必须将该类所以文件使用include或require加进来,这样我们就可以使用类了。而对于P