如何在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，如下图：

既然是使用递归的方法构建二叉树，主要需要理解递归的过程，这种思路将在之后的很多地方用的到。
要知道如何递归的构建二叉树，我们不能纠结于递归每一层到底干了什么，这样就会一直纠结下去（所有的递归问题都一样）。我们需要注意的是：

  1. 在我们的任务中，终止条件是什么？
  2. 在我们的任务中，本次递归要干嘛？
  3. 在我们的任务中，本次递归要返回给上一次递归的是啥？

在递归构建二叉树的任务中，我们要做到不纠结于每一层，而是只关注该层在做什么，这样，对于下图左侧的树，我们就可以看作为右侧的树，它只有自己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创建二叉树的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 基于python二叉树的构造和打印例子

    写在最前面: 带你从最简单的二叉树构造开始,深入理解二叉树的数据结构,ps:不会数据结构的程序猿只能是三流的 首先,我们构造一个二叉树 这是最标准,也是最简单的二叉树构造方法 ''' 树的构建: 3 9 20 15 7 ''' class Tree(): '树的实现' def __init__(self,data,left = 0,right = 0): self.left = left self.right = right self.data = data def __str__(self):

  • 用Python实现二叉树、二叉树非递归遍历及绘制的例子

    前言 关于二叉树的实现与遍历,网上已经有很多文章了,包括C, C++以及JAVA等.鉴于python做为脚本语言的简洁性,这里写一篇小文章用python实现二叉树,帮助一些对数据结构不太熟悉的人快速了解下二叉树.本文主要通过python以非递归形式实现二叉树构造.前序遍历,中序遍历,后序遍历,层次遍历以及求二叉树的深度及叶子结点数.其他非递归形式的遍历,想必大多人应该都很清楚,就不再声明.如果你用C或者C++或者其他高级语言写过二叉树或者阅读过相关方面代码,应该知道二叉树的非递归遍历避不开通过栈

  • Python3实现二叉树的最大深度

    问题提出: 给定一个二叉树,找出其最大深度.二叉树的深度为根节点到最远叶子节点的最长路径上的节点数. 说明: 叶子节点是指没有子节点的节点. 解决思路:递归法求解.从根结点向下遍历,每遍历到子节点depth+1. 代码实现(￣▽￣): # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Non

  • Python对称的二叉树多种思路实现方法

    对称二叉树的含义非常容易理解,左右子树关于根节点对称,具体来讲,对于一颗对称二叉树的每一颗子树,以穿过根节点的直线为对称轴,左边子树的左节点=右边子树的右节点,左边子树的右节点=左边子树的左节点.所以对称二叉树的定义是针对一棵树,而判断的操作是针对节点,这时可以采取由上到下的顺序,从根节点依次向下判断,只需要重复调用函数,不需要回溯. 题目:对称的二叉树题: 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的 解题思路一:先遍历右子节点再

  • Python3 翻转二叉树的实现

    提出问题:翻转一棵二叉树.(除根结点以外) 原始二叉树: 新二叉树: 解题思路:遇见二叉树先想到递归.从最下层的叶子结点开始置换左右子节点,一直置换到到最上层的根结点的左右节点为止. 代码如下(￣▽￣): # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solutio

  • Python实现二叉树的最小深度的两种方法

    找到给定二叉树的最小深度 最小深度是从根节点到最近叶子节点的最短路径上的节点数量 注意:叶子节点没有子树 Example: Given binary tree [3,9,20,null,null,15,7], 3    / \   9  20     /  \    15   7 return its minimum depth = 2. 1:算法遍历二叉树每一层,一旦发现某层的某个结点无子树,就返回该层的深度,这个深度就是该二叉树的最小深度 def minDepth(self, root):

  • Python3 合并二叉树的实现

    题目要求:给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠.你需要将他们合并为一个新的二叉树.合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点. 解决思想:遇到二叉树,首先想到的是递归实现.为了降低空间消耗,两个二叉树合并为一个时,不再新建树.初始给定两个树的当前结点(根结点)t1.t2,若t1和t2节点均不为空,t1节点值更新为t1+t2的值,递归遍历当前节点的左子树和右子树:如果任意其

  • Python 二叉树的层序建立与三种遍历实现详解

    Python 二叉树的层序建立与三种遍历实现详解

    前言 二叉树(Binary Tree)时数据结构中一个非常重要的结构,其具有....(此处省略好多字)....等的优良特点. 之前在刷LeetCode的时候把有关树的题目全部跳过了,(ORZ:我这种连数据结构都不会的人刷j8Leetcode啊!!!) 所以 !!!敲黑板了!!!今天我就在B站看了数据结构中关于树的内容后,又用我浅薄的Python大法来实现一些树的建立和遍历. 关于树的建立我觉得层序建立对于使用者来说最为直观,输入很好写.(好吧,我是看LeetCode中的树输入都是采用层序输入觉得

  • python3实现在二叉树中找出和为某一值的所有路径(推荐)

    请写一个程序创建一棵二叉树,并按照一定规则,输出二叉树根节点到叶子节点的路径. 规则如下: 1.从最顶端的根结点,到最下面的叶子节点,计算路径通过的所有节点的和,如果与设置的某一值的相同,那么输出这条路径上的所有节点. 2.从根节点遍历树时,请请按照左到右遍历,即优先访问左子树的节点. 二叉树创建规则:从上到下一层一层的,按照从左到右的顺序进行构造 输入"10,5,12,4,7"值,构造的树如下: 1) 10 2) 10       /     5 3) 10        /\   

  • python3实现二叉树的遍历与递归算法解析(小结)

    1.二叉树的三种遍历方式 二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历 即:先中后指的是访问根节点的顺序 eg:先序 根左右 中序 左根右 后序 左右根 遍历总体思路:将树分成最小的子树,然后按照顺序输出 1.1 先序遍历 a 先访问根节点 b 访问左节点 c 访问右节点 a(b ( d ( h ) )( e ( i ) ))( c ( f )( g )) -- abdheicfg 1.2 中序遍历 a 先访问左节点 b 访问根节点 c 访问右节点 ( ( ( h ) d ) b ( (

随机推荐