• 售前

  • 售后

热门帖子
入门百科

如何在Python中创建二叉树

[复制链接]
尘埃416 显示全部楼层 发表于 2021-10-26 14:02:29 |阅读模式 打印 上一主题 下一主题
目录


  • 前言
  • 二叉树节点定义
  • 递归构建二叉树

前言


本文的内容是数据结构中二叉树部分最底子的,之所以写一下主要是为了方便刷题的时候,能够在自己电脑上很快的使用这种小的demo进行复杂的练习。

二叉树节点定义


二叉树的节点定义如下:
  1. class TreeNode():#二叉树节点
  2.   def __init__(self,val,lchild=None,rchild=None):
  3.     self.val=val                #二叉树的节点值
  4.     self.lchild=lchild                #左孩子
  5.     self.rchild=rchild                #右孩子
复制代码
递归构建二叉树


本文使用的前序递归构建的方法(别的序次读者自行变革,本文主要意在如何快速构建能够实行的二叉树)
例如,我们想构建一个如下图所示的树(其前序遍历结果为:abcde):

这里我们须要使用到扩展的二叉树,也就是要告诉盘算机什么是叶结点,什么是空节点,否侧无法分辨左右节点。例如先序遍历的序次为"abcde",扩展的二叉树前序序列为:“abc##d##e##”,#代表此处节点为None,如下图:

既然是使用递归的方法构建二叉树,主要须要理解递归的过程,这种思绪将在之后的很多地方用的到。
要知道如何递归的构建二叉树,我们不能纠结于递归每一层到底干了什么,如许就会不停纠结下去(所有的递归标题都一样)。我们须要注意的是:
      
  • 在我们的使掷中,终止条件是什么?  
  • 在我们的使掷中,本次递归要干嘛?  
  • 在我们的使掷中,本次递归要返回给上一次递归的是啥?
在递归构建二叉树的使掷中,我们要做到不纠结于每一层,而是只关注该层在做什么,如许,对于下图左侧的树,我们就可以看作为右侧的树,它只有自己a (a),左子树B (bcd)和右子树C (e)。

如许我们须要注意的那三个标题的答复自然就有了(做递归标题,心中要想着怎么答复这三个标题):
      
  • 在我们的使掷中,终止条件是什么?
[给我们的字符用完,也就不须要再创建节点了]
      
  • 在我们的使掷中,本次递归要干嘛?
[本次递归要创建三个节点,一个根节点,一个左节点,一个右节点]
      
  • 在我们的使掷中,本次递归要返回给上一次递归的是啥?
[当然是返回一个本层构造好的树的根节点]
理解了上述三个标题的答复,递归的代码自然可以写出:
  1. def Creat_Tree(Root,val):
  2.   if len(vals)==0:#终止条件:val用完了
  3.     return Root
  4.   if vals[0]!='#':#本层需要干的就是构建Root、Root.lchild、Root.rchild三个节点。
  5.     Root = TreeNode(vals[0])
  6.     vals.pop(0)
  7.     Root.lchild = Creat_Tree(Root.lchild,val)
  8.     Root.rchild = Creat_Tree(Root.rchild,val)
  9.     return Root#本次递归要返回给上一次的本层构造好的树的根节点
  10.   else:
  11.     Root=None
  12.     vals.pop(0)
  13.     return Root#本次递归要返回给上一次的本层构造好的树的根节点
复制代码
看懂了上述内容,构建一棵我们想象的二叉树就很简单了,只要输入一个我们心目中前序遍历扩展的二叉树序列即可:
  1. if __name__ == '__main__':
  2.   Root = None
  3.   strs="abc##d##e##"#前序遍历扩展的二叉树序列
  4.   vals = list(strs)
  5.   Roots=Creat_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。
复制代码
以上就是如何在Python中创建二叉树的详细内容,更多关于Python创建二叉树的资料请关注脚本之家别的干系文章!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作