python二叉树类以及其4种遍历方法实例
作者:Hann?Yang 发布时间:2023-07-25 02:22:48
标签:Python,二叉树类,遍历
前言
之前学习过binarytree第三方库,了解了它定义的各种基本用法。
昨天在问答频道中做题时碰到一个关于二叉树的算法填空题,感觉代码不错非常值得学习,于是整理代码分享如下:
实例代码:
from collections import deque #层遍历中用到队列数据类型
class BTNode: #二叉链中结点类
def __init__(self,d = None):
self.data = d #结点值
self.lchild = None #左hai子指针
self.rchild = None #右hai子指针
class BTree: #二叉树类
def __init__(self,d = None):
self.b = None #根结点指针
def DispBTree(self): #返回二叉链的括号表示串
return self._DispBTree1(self.b)
def _DispBTree1(self,t): #被DispBTree方法调用
if t==None: #空树返回空串
return ""
else:
bstr = t.data #输出根结点值
if t.lchild != None or t.rchild != None:
bstr += "(" #有hai子结点时输出"("
bstr += self._DispBTree1(t.lchild) #递归输出左子树
if t.rchild != None:
bstr += "," #有右hai子结点时输出","
bstr += self._DispBTree1(t.rchild) #递归输出右子树
bstr += ")" #输出")"
return bstr
def FindNode(self,x): #查找值为x的结点算法
return self._FindNode1(self.b,x)
def _FindNode1(self,t,x): #被FindNode方法调用
if t==None:
return None #t为空时返回null
elif t.data==x:
return t #t所指结点值为x时返回t
else:
p = self._FindNode1(t.lchild,x) #在左子树中查找
if p != None:
return p #在左子树中找到p结点,返回p
else:
return self._FindNode1(t.rchild,x) #返回在右子树中查找结果
def Height(self): #求二叉树高度的算法
return self._Height1(self.b)
def _Height1(self,t): #被Height方法调用
if t==None:
return 0 #空树的高度为0
else:
lh = self._Height1(t.lchild) #求左子树高度lchildh
rh = self._Height1(t.rchild) #求右子树高度rchildh
return max(lh,rh)+1
def PreOrder(bt): #先序遍历的递归算法
_PreOrder(bt.b)
def _PreOrder(t): #被PreOrder方法调用
if t != None:
print(t.data,end = ' ') #访问根结点
_PreOrder(t.lchild) #先序遍历左子树
_PreOrder(t.rchild) #先序遍历右子树
def InOrder(bt): #中序遍历的递归算法
_InOrder(bt.b)
def _InOrder(t): #被InOrder方法调用
if t != None:
_InOrder(t.lchild) #中序遍历左子树
print(t.data,end = ' ') #访问根结点
_InOrder(t.rchild) #中序遍历右子树
def PostOrder(bt): #后序遍历的递归算法
_PostOrder(bt.b)
def _PostOrder(t): #被PostOrder方法调用
if t != None:
_PostOrder(t.lchild) #后序遍历左子树
_PostOrder(t.rchild) #后序遍历右子树
print(t.data,end = ' ') #访问根结点
def LevelOrder(bt): #层序遍历的算法
qu = deque() #将双端队列作为普通队列qu
qu.append(bt.b) #根结点进队
while len(qu)>0: #队不空循环
p = qu.popleft() #出队一个结点
print(p.data,end = ' ') #访问p结点
if p.lchild != None: #有左hai子时将其进队
qu.append(p.lchild)
if p.rchild != None: #有右hai子时将其进队
qu.append(p.rchild)
def CreateBTree2(posts,ins): #由后序序列posts和中序序列ins构造二叉链
bt = BTree()
bt.b = _CreateBTree2(posts,0,ins,0,len(posts))
return bt
def _CreateBTree2(posts,i,ins,j,n):
if n <= 0:
return None
d = posts[i+n-1] #取后序序列尾元素d
t = BTNode(d) #创建根结点(结点值为d)
p = ins.index(d) #在ins中找到根结点的索引
k = p-j #确定左子树中结点个数k
t.lchild = _CreateBTree2(posts,i,ins,j,k) #递归构造左子树
t.rchild = _CreateBTree2(posts,i+k,ins,p+1,n-k-1) #递归构造右子树
return t
if __name__ == '__main__':
inlst = ['D','G','B','A','E','C','F']
posts = ['G','D','B','E','F','C','A']
print(f"中序列表 :{inlst}")
print(f"后序列表 :{posts}")
#构造二叉树bt
bt = BTree()
bt = CreateBTree2(posts,inlst)
print(f"\n构造二叉树:{bt.DispBTree()}")
x = 'F'
if bt.FindNode(x):
print(f"bt中存在 :'{x}'")
else:
print(f"bt中不存在 :'{x}'")
print(f"bt的高度 :{bt.Height():^3}")
print("\n先序遍历 :",end='')
PreOrder(bt)
print("\n中序遍历列 :",end='')
InOrder(bt)
print("\n后序遍历 :",end='')
PostOrder(bt)
print("\n层序遍历 :",end='')
LevelOrder(bt)
中序列表:['D', 'G', 'B', 'A', 'E', 'C', 'F']
后序列表:['G', 'D', 'B', 'E', 'F', 'C', 'A']构造二叉树:A(B(D(,G),C(E,F))
bt中存在 :'F'
bt的高度 : 4先序遍历 :A B D G C E F
中序遍历 :D G B A E C F
后序遍历 :G D B E F C A
层序遍历 :A B C D E F G
相关阅读内容:
Python 初识二叉树,新手也秒懂!
Python 初识二叉树,新手也秒懂!(续:实战binarytree)
来源:https://blog.csdn.net/boysoft2002/article/details/124815477
0
投稿
猜你喜欢
- ajax缓存和编码问题不难解决,下面是解决方法。编码问题默认使用UTF-8,如果一旦发现对象找不到的情况,可能js中输入了中文,同时js的编
- 异常描述有时我们的Excel有一个调整过自定义格式的日期字段:当我们用pandas读取时却是这样的效果:不管如何指定参数都无效。出现原因没有
- 代码如下:<% set studentinstance = CreateStudent()&n
- 一个简单的tokenizer分词(tokenization)任务是Python字符串处理中最为常见任务了。我们这里讲解用正则表达式构建简单的
- (需要安装psutil 用来获取服务器资源,以及pymongo驱动)#pip install psutil#pip install pymo
- 去年淘宝做了个“胖子”项目,就是把网页的默认宽度从780提升到了950。也就是说,基本放弃了800×600的用户(没有完全放弃,如果你仔细研
- 前言本文主要给大家介绍了利用django-suit模板在管理后台添加自定义的菜单和自定义的页面、设置访问权限的相关内容,分享出来供大家参考学
- 我们已经在Python运算中看到Python最基本的数学运算功能。此外,math包补充了更多的函数。当然,如果想要更加高级的数学功能,可以考
- Nextcloud 是一款自由 (开源) 的类 Dropbox 软件,由 ownCloud 分支演化形成。它使用 PHP 和 JavaScr
- 如果你正从你的用户那里收集信息, 没有比网页表单更简单和直接的办法了。一份有良好设计的表单可以提供有价值的信息, 相反, 他们有可能把用户吓
- 带你走进数据类型一:整数、浮点数Python中整数和浮点数的定义以及运算和C++都是一样的,我在这里就不需多说了,我就说明一点:Python
- 使用os.environ来读取和修改环境变量:import osprint (os.environ["TEMP"])my
- 安装pillow(python的图形界面库)第一种方法在Dos界面输入pip install pillow(但是不知为何总是失败);搞了好几
- 通过使用bootstrap框架,并配合Django自带的Paginator分页组件即可实现简单的分页效果。1.创建MyWeb项目python
- IE的有条件注释是一种专有的(因此是非标准的)、对常规(X)HTML注释的Miscrosoft扩展。顾名思义,有条件注释使你能够根据条件(比
- Python 实现删除某路径下文件及文件夹的脚本#!/usr/bin/env pythonimport osimport shutildel
- OpenCV提供了很多简单的语句,实现复杂的功能,根据颜色和鼠标交互的基础语句,我们可以建立一个简单的画板。尽管它简单,但是制作的框架步骤不
- 不敢说得太明显太仔细,反正你懂的。有两种方法,一种是搭建本地授权服务器,另一种是直接替换核心文件,修改对应的注册码。先说第一种。 下载Int
- 在翻译这篇文章时我想起一件事情,去年有个朋友在网上非常兴致勃勃的和我说:“我弄了一个很酷的网站,去玩玩吧!真的不错哦!”,然后他把网址发给我
- django程序,需要写很多api,每个函数都需要几个装饰器,例如@csrf_exempt @require_POST