时间:2021-05-23
本文的内容是数据结构中二叉树部分最基础的,之所以写一下主要是为了方便刷题的时候,能够在自己电脑上很快的使用这种小的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)。
这样我们需要注意的那三个问题的回答自然就有了(做递归问题,心中要想着怎么回答这三个问题):
[给我们的字符用完,也就不需要再创建节点了]
[本次递归要创建三个节点,一个根节点,一个左节点,一个右节点]
[当然是返回一个本层构造好的树的根节点]
理解了上述三个问题的回答,递归的代码自然可以写出:
看懂了上述内容,构建一棵我们想象的二叉树就很简单了,只要输入一个我们心目中前序遍历扩展的二叉树序列即可:
if __name__ == '__main__': Root = None strs="abc##d##e##"#前序遍历扩展的二叉树序列 vals = list(strs) Roots=Creat_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。以上就是如何在Python中创建二叉树的详细内容,更多关于Python创建二叉树的资料请关注其它相关文章!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
问题如何遍历一个二叉树遍历二叉树就是访问二叉树的每一个节点二叉树父结点下先左访问,先序遍历(根左右)例如:遍历以下的二叉树遍历结果:ABDECFPython代码
问题创建一个二叉树二叉树有限多个节点的集合,这个集合可能是:空集由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成创建二叉树,创建节点,再创建节
问题创建一个二叉树二叉树有限多个节点的集合,这个集合可能是:空集由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成创建二叉树:创建节点再创建节点
二叉树是一种非常重要的数据结构。本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历),二叉搜索树的构
本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下:题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树