用Python怎样创建二叉树？有什么方法？
发布时间：2022-03-29 13:58:57 所属栏目：语言 来源：互联网
导读：这篇文章主要给大家分享如何在Python中创建二叉树，虽然本文内容是数据结构中二叉树部分比较基础的，但是对新手理解Python创建二叉树有一定的学习参考价值，下面我们就一起来看看吧。 二叉树节点定义 二叉树的节点定义如下： class TreeNode():#二叉树节点 d
|
这篇文章主要给大家分享如何在Python中创建二叉树，虽然本文内容是数据结构中二叉树部分比较基础的，但是对新手理解Python创建二叉树有一定的学习参考价值，下面我们就一起来看看吧。 二叉树节点定义 二叉树的节点定义如下： class TreeNode():#二叉树节点 def __init__(self,val,lchild=None,rchild=None): self.val=val #二叉树的节点值 self.lchild=lchild #左孩子 self.rchild=rchild #右孩子 递归构建二叉树 本文使用的前序递归构建的方法（其余顺序读者自行变化，本文主要意在如何快速构建能够执行的二叉树） 例如，我们想构建一个如下图所示的树（其前序遍历结果为：abcde）: 这里我们需要使用到扩展的二叉树，也就是要告诉计算机什么是叶结点，什么是空节点，否侧无法分辨左右节点。例如先序遍历的顺序为"abcde"，扩展的二叉树前序序列为：“abc##d#[/!--empirenews.page--]#”，#代表此处节点为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#[/!--empirenews.page--]#"#前序遍历扩展的二叉树序列 vals = list(strs) Roots=Creat_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。 （编辑：济源站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
