如何在Python中创建二叉树
作者:English_yang 发布时间:2022-07-30 06:27:35
目录
前言
二叉树节点定义
递归构建二叉树
前言
本文的内容是数据结构中二叉树部分最基础的,之所以写一下主要是为了方便刷题的时候,能够在自己电脑上很快的使用这种小的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,如下图:
既然是使用递归的方法构建二叉树,主要需要理解递归的过程,这种思路将在之后的很多地方用的到。
要知道如何递归的构建二叉树,我们不能纠结于递归每一层到底干了什么,这样就会一直纠结下去(所有的递归问题都一样)。我们需要注意的是:
在我们的任务中,终止条件是什么?
在我们的任务中,本次递归要干嘛?
在我们的任务中,本次递归要返回给上一次递归的是啥?
在递归构建二叉树的任务中,我们要做到不纠结于每一层,而是只关注该层在做什么,这样,对于下图左侧的树,我们就可以看作为右侧的树,它只有自己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就是我们要的二叉树的根节点。
来源:https://blog.csdn.net/English_yang/article/details/115285234
猜你喜欢
- 今天因为做一个效果的时候需要CSS的定位来实现,于是我就根据自己原来对CSS的了解,用absolute和relative摆弄了好一阵子,总是
- 本文要实现的功能是:根据下拉列表的选项将数据库中对应的内容显示在页面,选定要排除的选项后,提交剩余的选项到数据库。为了方便前后台交互,利用了
- 本文实例讲述了Python pymongo模块用法。分享给大家供大家参考,具体如下:MongoDB优点 MongoDB是一个为当代web应用
- 本文实例讲述了Python求解平方根的方法。分享给大家供大家参考。具体如下:主要通过SICP的内容改写而来。基于newton method求
- 对匿名用户采用 IP 控制访问频率,对登录用户采用 用户名 控制访问频率。from rest_framework.throttling im
- 前言Iframe 是一种将网页嵌入到另一个页面的内容中的方法。这是通过使用 HTML 元素、外部网站的 URL 以及窗口在您的网站上的外观参
- 这篇文章主要介绍了微信小程序 云开发模糊查询实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友
- 这篇文章主要介绍了Oracle数据库到SQL Server数据库主键的迁移过程,具体内容请参考下文。由于项目需要要将以前Oracle的数据库
- 本教程主要介绍css的基础知识,将逐个讲解css的各个属性,过程可能比较枯燥,但会尽力多举例说明.作者的网站:http://jorux.co
- 本文实例分析了Python自定义进程池。分享给大家供大家参考,具体如下:代码说明一切:#encoding=utf-8#author: wal
- 1、首先,界面上有个按钮触发操作:<button type="button" class="layui-
- 如何利用pandas读取csv数据并绘图导包,常用的numpy和pandas,绘图模块matplotlib,import matplotli
- 介绍在本文中,云朵君将和大家一起了解装饰器的工作原理,如何将我们之前定义的定时器类 Timer 扩展为装饰器,以及如何简化计时功能。最后对
- 用opencv处理一下pillow也可以,但是试过有时候会把图片自动旋转180°,cv没有这个问题import osfrom
- 这是Smashing Magazine花费几个月的时间研究编写的2009 年Web设计风格与潮流,Smashing Magazine 的编辑
- 在 Python 中也可以像 gcc/gdb 那样调试程序,只要在运行 Python 程序时引入 pdb 模块(假设要调试的程序名为 d.p
- Flask-Login 为 Flask 提供用户会话管理。它处理登录、注销和长时间记住用户会话等常见任务。Flask-Login 不绑定到任
- 爬取流程(美食区最热标签下的三个视频)在首页获取视频的编号和名字拼接成正确的url保存视频思路1.从网页中获取视频的url发现视频的url在
- iconv函数库能够完成各种字符集间的转换,是php编程中不可缺少的基础函数库。 1、下载libiconv函数库http://ftp.gnu
- 服务端:#!/usr/bin/envimport SocketServerclass myMonitorHandler(SocketServ