Python实现二叉树前序、中序、后序及层次遍历示例代码
作者:yongxinz 发布时间:2023-12-02 00:36:40
标签:python,二叉树,前序
前言
树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树、FP-树。另外可以用来提高编码效率,如哈弗曼树。
用 Python 实现树的构造和几种遍历算法。实现功能如下:
树的构造
递归实现先序遍历、中序遍历、后序遍历
堆栈实现先序遍历、中序遍历、后序遍历
队列实现层次遍历
# -*- coding=utf-8 -*-
class Node(object):
"""节点类"""
def __init__(self, element=-1, l_child=None, r_child=None):
self.element = element
self.l_child = l_child
self.r_child = r_child
class Tree(object):
"""树类"""
def __init__(self):
self.root = Node()
self.queue = []
def add_node(self, element):
"""为树添加节点"""
node = Node(element)
# 如果树是空的,则对根节点赋值
if self.root.element == -1:
self.root = node
self.queue.append(self.root)
else:
tree_node = self.queue[0]
# 此结点没有左子树,则创建左子树节点
if tree_node.l_child is None:
tree_node.l_child = node
self.queue.append(tree_node.l_child)
else:
tree_node.r_child = node
self.queue.append(tree_node.r_child)
# 如果该结点存在右子树,将此节点丢弃
self.queue.pop(0)
def front_recursion(self, root):
"""利用递归实现树的前序遍历"""
if root is None:
return
print root.element,
self.front_recursion(root.l_child)
self.front_recursion(root.r_child)
def middle_recursion(self, root):
"""利用递归实现树的中序遍历"""
if root is None:
return
self.middle_recursion(root.l_child)
print root.element,
self.middle_recursion(root.r_child)
def back_recursion(self, root):
"""利用递归实现树的后序遍历"""
if root is None:
return
self.back_recursion(root.l_child)
self.back_recursion(root.r_child)
print root.element,
@staticmethod
def front_stack(root):
"""利用堆栈实现树的前序遍历"""
if root is None:
return
stack = []
node = root
while node or stack:
# 从根节点开始,一直找它的左子树
while node:
print node.element,
stack.append(node)
node = node.l_child
# while结束表示当前节点node为空,即前一个节点没有左子树了
node = stack.pop()
# 开始查看它的右子树
node = node.r_child
@staticmethod
def middle_stack(root):
"""利用堆栈实现树的中序遍历"""
if root is None:
return
stack = []
node = root
while node or stack:
# 从根节点开始,一直找它的左子树
while node:
stack.append(node)
node = node.l_child
# while结束表示当前节点node为空,即前一个节点没有左子树了
node = stack.pop()
print node.element,
# 开始查看它的右子树
node = node.r_child
@staticmethod
def back_stack(root):
"""利用堆栈实现树的后序遍历"""
if root is None:
return
stack1 = []
stack2 = []
node = root
stack1.append(node)
# 这个while循环的功能是找出后序遍历的逆序,存在stack2里面
while stack1:
node = stack1.pop()
if node.l_child:
stack1.append(node.l_child)
if node.r_child:
stack1.append(node.r_child)
stack2.append(node)
# 将stack2中的元素出栈,即为后序遍历次序
while stack2:
print stack2.pop().element,
@staticmethod
def level_queue(root):
"""利用队列实现树的层次遍历"""
if root is None:
return
queue = []
node = root
queue.append(node)
while queue:
node = queue.pop(0)
print node.element,
if node.l_child is not None:
queue.append(node.l_child)
if node.r_child is not None:
queue.append(node.r_child)
if __name__ == '__main__':
"""主函数"""
# 生成十个数据作为树节点
elements = range(10)
tree = Tree()
for elem in elements:
tree.add_node(elem)
print '队列实现层次遍历:'
tree.level_queue(tree.root)
print '\n\n递归实现前序遍历:'
tree.front_recursion(tree.root)
print '\n递归实现中序遍历:'
tree.middle_recursion(tree.root)
print '\n递归实现后序遍历:'
tree.back_recursion(tree.root)
print '\n\n堆栈实现前序遍历:'
tree.front_stack(tree.root)
print '\n堆栈实现中序遍历:'
tree.middle_stack(tree.root)
print '\n堆栈实现后序遍历:'
tree.back_stack(tree.root)
需要源码的小伙伴可自行下载:代码传送门
来源:https://juejin.im/post/5cdd5f5ee51d453a6c23b0af
0
投稿
猜你喜欢
- 之前用 copy 不多,本以为它是个很方便的函数,没想到在做练习题时竟还是被它坑了。是我对他期望太多了。func copy(dst, src
- 本文实例讲述了Python文件及目录操作的方法。分享给大家供大家参考。具体分析如下:在python中对文件及目录的操作一般涉及多os模块,o
- 这是Smashing Magazine花费几个月的时间研究编写的2009 年Web设计风格与潮流,Smashing Magazine 的编辑
- 用python连接Oracle是总是乱码,最有可能的是oracle客户端的字符编码设置不对。本人是在进行数据插入的时候总是报关键字"
- 本文为大家分享了购物商城小程序,供大家参考,具体内容如下软件版本:python3.x功能:实现简单购物商城1.允许用户选择购买多
- 前言:在生活中工作中,我们经常使用Excel用于储存数据,Tableau等BI程序处理数据并进行可视化。我们也经常使用R、Python编程进
- 废话少说,上干活。for的基本操作for是用来循环的,是从某个对象那里依次将元素读取出来。看下面的例子,将已经学习过的数据对象用for循环一
- 每次在"万达影城"网上购票总会用到左上角选择城市的功能。如下:今天就在ASP.NET MVC中实现一下。我想最好的方式应
- Celery (芹菜)是基于Python开发的分布式任务队列。它支持使用任务队列的方式在分布的机器/进程/线程上执行任务调度。架
- 现在,比较牛的设计师和开发者都认识到了可用性在他们工作中的重要性。可用性好的网站会极大地提高用户体验,并且好的用户体验会让用户更加快乐。用聪
- 这几天研究了下PyQt5中QWebEngineView内嵌网页与Python的数据交互,今天把实例方法与代码发布出来供大家参数数据交互需要l
- 存在问题:jupyter代码无法在pycharm中运行原因:工作文件和安装文件不统一引起的解决方案:pycharm中新建工程项目时,要将图中
- 目录项目地址功能概述效果图模块安装提交环境为python3.7 pyqt5==5.13.2 win10 一切正常!说一说大概的思路吧项目地址
- 有时我们需要将一份或者多份PDF文件中的图片提取出来,如果采取在线的网站实现的话又担心图片泄漏,手动操作又觉得麻烦,其实用Python也可以
- 想弄个截屏工具,整理一下学生错题什么的,原来用的方法是:先运行QQ,再监听键盘热键(“ctrl+alt+a”)。后来发现有些问题:需要先上Q
- 代码实例:try: import termios, TERMIOS 1except ImportErro
- 本文实例讲述了Python基础之条件控制操作。分享给大家供大家参考,具体如下:if 语句Python中if语句的一般形式如下所示:if co
- 基本思路使用GDAL创建Shapefile数据的基本步骤如下:使用osgeo.ogr.Driver的CreateDataSource()方法
- 本文实例讲述了Python面向对象程序设计之私有属性及私有方法。分享给大家供大家参考,具体如下:如果有一个对象,当需要对其进行修改属性时,有
- 关于Pytorch的MNIST数据集的预处理详解MNIST的准确率达到99.7%用于MNIST的卷积神经网络(CNN)的实现,具有各种技术,