前言

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

  1. 剪枝决策树原理与Python实现

    机器学习经典模型决策树的实现原理,以及Python实现目录一、决策树模型 二、选择划分 2.1 信息熵和信息增益 2.2 增益率 2.3 基尼指数 三、剪枝 3.1 预剪枝 3.2 后剪枝 3.3 剪枝示例 3.4 预剪枝和后剪枝对比 四、Python实现 4.1 基尼值和基尼指数 4.2 选择划分......

  2. 用Python自动清理电脑内重复文件,只要10行代码(自动脚本)

    给定一个文件夹,使用Python检查给定文件夹下有无文件重复,若存在重复则删除主要涉及的知识点有:os模块综合应用glob模块综合应用利用filecmp模块比较两个文件步骤分析该程序实现的逻辑可以具化为:遍历获取给定文件夹下的所有文件,然后通过嵌套循环两两比较文件是否相同,如果相同则删除后者。实现问......

  3. python 制作网站筛选工具(附源码)

    一.思路1.整体思路2.代码思路思路很简单,就是用python发送请求,提取响应体中的状态码加以判断,最后保存到本地txt文本中,以实现网站信息的筛选。二.撰写代码import timeimport requestsimport urllib3from concurrent.futures impo......

  4. 解决python 读取npy文件太大不能完全显示的问题

    python读取npy文件时,太大不能完全显示,其解决方法当用python读取npy文件时,会遇到npy文件太大,用print函数打印时不能完全显示,如以下情况:解决办法添加一行代码:np.set_printoptions(threshold = 1e6),其中threshold表示输出数组的元素数......

  5. 详解用 python-docx 创建浮动图片

    相信大家对python-docx这个常用的操作docx文档的库都不陌生,它支持以内联形状(Inline Shape)的形式插入图片,即图片和文本之间没有重叠,遵循流动版式(flow layout)。但是,截至最新的0.8.10版本,python-docx尚不支持插入浮动图片(floating pic......

  6. pytorch 实现冻结部分参数训练另一部分

    1)添加下面一句话到模型中for p in self.parameters():p.requires_grad = False比如加载了resnet预训练模型之后,在resenet的基础上连接了新的模快,resenet模块那部分可以先暂时冻结不更新,只更新其他部分的参数,那么可以在下面加入上面那句话......

  7. pandas调整列的顺序以及添加列的实现

    在对excel的操作中,调整列的顺序以及添加一些列也是经常用到的,下面我们用pandas实现这一功能。1、调整列的顺序>>> df = pd.read_excel(r'D:/myExcel/1.xlsx')>>> dfA B C D0 bob 12 78 871......

  8. python中用ggplot绘制画图实例讲解

    Python的绘图库也允许用户创建优雅的图形,本章给大家介绍的是关于ggplot绘制画图的技巧,ggplot2建立在grid系统上,这个系统不支持纹理。需要额外创建一堆数据,再基于这些数据构建一个geom_path图层,盖在柱图上才可以进行各种绘制,下面给大家详细讲解下怎么使用ggplot绘图。简介......

  9. python基于pexpect库自动获取日志信息

    1. 前言对大部分的人来说,解决 Bug 都是依靠关键字去日志去定位问题!在调试情况下,我们可以实时在控制台查看日志;但对于部署到服务器上的应用,日志都存放在服务器某个目录下,没法通过本地查看到这种情况下,就需要我们先登录服务器,然后进入到日志目录文件夹,最后通过日志文件去定位问题;如果涉及到 K8......

  10. opencv python 对指针仪表读数识别的两种方式

    我尝试了两种方式用opencv 对指针仪表进行读数识别,1. 先模板匹配,然后边缘检测 + 霍夫直线2. 按轮廓大小过滤,然后边缘检测 + 霍夫直线两种方式对光线都非常敏感其中第一种的应用范围更广,背景复杂一点也能识别到个人比较喜欢这种方式第二种的限制多一点,对背景、光线条件要求比较高对于固定位置,......

随机推荐

  1. 浅谈在Java中JSON的多种使用方式

    1. 常用的JSON转换JSONObject 转 JSON 字符串JSONObject json = new JSONObject();jsonObject.put("name", "test");String str = JSONObject.toJSONS......

  2. Android如何实现动态滚动波形图(心电图)功能

    一、前言最近涉及的某个医疗相关的业务,传感器数据传递上来需要实现示波器的效果,心电图的效果,目前交付效果还算理想,于是封装了一下,方便自己以后使用,也给大家分享一下二、效果图图一是心电图效果,图二是一个滚动的波形图三、功能实现(一)绘制背景网格为了让他看上去像示波器上的数据,我们先绘制一层网格背景,......

  3. MySQL下载地址与Centos7安装MySQL以及启动问题排查

    MySQL国内镜像下载地址以及开源镜像相关站点Centos7安装MySQL启动问题(The server quit without updating PID file)解决方式目录一、MySQL国内镜像下载二、国内镜像相关站点三、Centos7安装MySQL5.71. 下载并解压至/usr/loca......

  4. input标签checkbox选中触发事件的方法

    1.方法一function checkboxOnclick(checkbox){ if ( checkbox.checked == true){ //Action for checked }else{ //Action for not checked }} 2.方法二$('#allSelect'......

  5. Linux中自定义shell脚本启动jar包的方法

    一键启动、停止、重启 java项目创建.sh文件vi XXX.sh编写shell脚本#!/bin/shport=8080 #定义变量等号左右不能有空格jar_name=/opt/oaclou/XXX.jar#运行脚本提示信息tips(){echo "--------------------......

  6. Java 给Word不同页面设置不同背景

    Word文档中,可直接通过【设计】-【页面颜色】页面颜色,通过Java代码可参考如下设置方法:1. 设置单一颜色背景doc.getBackground().setType(BackgroundType.Color);doc.getBackground().setColor(Color.PINK);2......

  7. Mysql将查询结果集转换为JSON数据的实例代码

    Mysql将查询结果集转换为JSON数据 前言学生表学生成绩表查询单个学生各科成绩(转换为对象JSON串并用逗号拼接)将单个学生各科成绩转换为数组JSON串将数组串作为value并设置key两张表联合查询(最终SQL,每个学生各科成绩)最终结果前言我们经常会有这样一种需求,一对关联关系表,一对多的关......

  8. Python监控进程状态并实现告警

    公司的应用程序有时候会莫名其妙地挂掉,如果我们经常去登录服务器看是不是程序挂了,挂了再拉起,那样是非常耗时和麻烦的事情。后来我们通过使用 supervisor 去守护启动,实现方法如下:那什么是 supervisor了?Supervisor是用 Python 开发的一个client/server服务......

  9. 改进你的c#代码的5个技巧(四)

    像每一篇文章一样,我会重复几行。我在我的Core i3 CPU、4GB主内存和Windows 7平台上测试了以下代码。如果你在不同的硬件配置或使用不同的平台,那么你的输出可能会随着我的输出屏幕而变化,并且输出可能会根据当前运行的进程而变化。由于所有的点都是性能测试,我已经在发布模式下对它们进行了测试......

  10. python爬虫利用代理池更换IP的方法步骤

    0. 前言周日在爬一个国外网站的时候,发现用协程并发请求,并且请求次数太快的时候,会出现对方把我的服务器IP封掉的情况。于是网上找了一下开源的python代理池,这里选择的是star数比较多的proxy_pool1. 安装环境# 安装python虚拟环境, python环境最好为python3.6,......