如何在Python中创建二叉树
前言
本文的内容是数据结构中二叉树部分最基础的,之所以写一下主要是为了方便刷题的时候,能够在自己电脑上很快的使用这种小的demo进行复杂的练习。
二叉树节点定义
二叉树的节点定义如下:
class TreeNode():#二叉树节点 def __init__(self,val,lchild=None,rchild=None): self.val=val #二叉树的节点值 self.lchild=lchild #左孩子 self.rchild=rchild #右孩子
递归构建二叉树
本文使用的前序递归构建的方法(其余顺序读者自行变化,本文主要意在如何快速构建能够执行的二叉树)
例如,我们想构建一个如下图所示的树(其前序遍历结果为:abcde):
这里我们需要使用到扩展的二叉树,也就是要告诉计算机什么是叶结点,什么是空节点,否侧无法分辨左右节点。例如先序遍历的顺序为"abcde",扩展的二叉树前序序列为:“abc##d##e##”,#代表此处节点为None,如下图:
既然是使用递归的方法构建二叉树,主要需要理解递归的过程,这种思路将在之后的很多地方用的到。
要知道如何递归的构建二叉树,我们不能纠结于递归每一层到底干了什么,这样就会一直纠结下去(所有的递归问题都一样)。我们需要注意的是:
- 在我们的任务中,终止条件是什么?
- 在我们的任务中,本次递归要干嘛?
- 在我们的任务中,本次递归要返回给上一次递归的是啥?
在递归构建二叉树的任务中,我们要做到不纠结于每一层,而是只关注该层在做什么,这样,对于下图左侧的树,我们就可以看作为右侧的树,它只有自己a (a),左子树B (bcd)和右子树C (e)。
这样我们需要注意的那三个问题的回答自然就有了(做递归问题,心中要想着怎么回答这三个问题):
- 在我们的任务中,终止条件是什么?
[给我们的字符用完,也就不需要再创建节点了]
- 在我们的任务中,本次递归要干嘛?
[本次递归要创建三个节点,一个根节点,一个左节点,一个右节点]
- 在我们的任务中,本次递归要返回给上一次递归的是啥?
[当然是返回一个本层构造好的树的根节点]
理解了上述三个问题的回答,递归的代码自然可以写出:
def Creat_Tree(Root,val): if len(vals)==0:#终止条件:val用完了 return Root if vals[0]!='#':#本层需要干的就是构建Root、Root.lchild、Root.rchild三个节点。 Root = TreeNode(vals[0]) vals.pop(0) Root.lchild = Creat_Tree(Root.lchild,val) Root.rchild = Creat_Tree(Root.rchild,val) return Root#本次递归要返回给上一次的本层构造好的树的根节点 else: Root=None vals.pop(0) return Root#本次递归要返回给上一次的本层构造好的树的根节点
看懂了上述内容,构建一棵我们想象的二叉树就很简单了,只要输入一个我们心目中前序遍历扩展的二叉树序列即可:
if __name__ == '__main__': Root = None strs="abc##d##e##"#前序遍历扩展的二叉树序列 vals = list(strs) Roots=Creat_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。
以上就是如何在Python中创建二叉树的详细内容,更多关于Python创建二叉树的资料请关注猪先飞其它相关文章!
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临,小编为大家带来了一个利用Python编写的虎年烟花特效,堪称全网最绚烂,文中的示例代码简洁易懂,感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容,对此有兴趣的朋友们可以学习下。...2021-02-06
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-02-20
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注,帮助大家更好的利用Matplotlib绘制图表,感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-09
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法,对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要为大家详细介绍了python实现双色球随机选号,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-05-02
Python getsizeof()和getsize()区分详解
这篇文章主要介绍了Python getsizeof()和getsize()区分详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-20- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
- 这篇文章主要介绍了解决python 两个时间戳相减出现结果错误的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 这篇文章主要为大家详细介绍了python实现学生通讯录管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-25
- 这篇文章主要介绍了PyTorch一小时掌握之迁移学习篇,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-08
- 这篇文章主要介绍了python进行相关性分析并绘制散点图,具有一定借鉴价值,需要的朋友可以参考下,希望能够给你带来帮助...2021-09-18