主页 > 知识库 > 如何在Python中创建二叉树

如何在Python中创建二叉树

热门标签:呼叫中心市场需求 客户服务 Win7旗舰版 企业做大做强 电话运营中心 语音系统 百度AI接口 硅谷的囚徒呼叫中心

前言

本文的内容是数据结构中二叉树部分最基础的,之所以写一下主要是为了方便刷题的时候,能够在自己电脑上很快的使用这种小的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创建二叉树的资料请关注脚本之家其它相关文章!

您可能感兴趣的文章:
  • Python对称的二叉树多种思路实现方法
  • python3实现在二叉树中找出和为某一值的所有路径(推荐)
  • Python实现二叉树的最小深度的两种方法
  • Python3 翻转二叉树的实现
  • Python3实现二叉树的最大深度
  • Python3 合并二叉树的实现
  • 用Python实现二叉树、二叉树非递归遍历及绘制的例子
  • 基于python二叉树的构造和打印例子
  • Python 二叉树的层序建立与三种遍历实现详解
  • python3实现二叉树的遍历与递归算法解析(小结)

标签:济南 安康 长沙 山西 崇左 海南 喀什 山西

巨人网络通讯声明:本文标题《如何在Python中创建二叉树》,本文关键词  ;如发现本文内容存在版权问题,烦请提供相关信息告之我们,我们将及时沟通与处理。本站内容系统采集于网络,涉及言论、版权与本站无关。
  • 相关文章
  • 收缩
    • 微信客服
    • 微信二维码
    • 电话咨询

    • 400-1100-266