二叉树基础概念
1.二叉树种类
1.1 满二叉树
满二叉树:如果一棵二叉树只有度为 0 0 0 的结点和度为 2 2 2 的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。
如图所示:

这棵二叉树为满二叉树,也可以说深度为 k k k,有 2 k − 1 2^k-1 2k−1 个节点的二叉树。
图中二叉树的深度为4,叶子节点个数= 2 4 − 1 = 15 2^4-1=15 24−1=15
1.2 完全二叉树
什么是完全二叉树?
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h h h 层,则该层包含 1 1 1~ 2 ( h − 1 ) 2^{(h-1)} 2(h−1) 个节点。

优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。
1.3 二叉搜索树
二叉搜索树是一个有序树。
- 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树:

1.4 平衡二叉搜索树
平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
如图:

最后一棵 不是平衡二叉树,因为它的左右两个子树的高度差的绝对值超过了 1 1 1。
2.二叉树的存储方式
二叉树可以链式存储,也可以顺序存储。
那么链式存储方式就用指针, 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的,而链式存储则是通过指针把分布在散落在各个地址的节点串联一起。
链式存储如图:

顺序存储的方式如图:

用数组来存储二叉树如何遍历的呢?
如果父节点的数组下标是 i i i,那么它的左孩子就是 i ∗ 2 + 1 i * 2 + 1 i∗2+1 ,右孩子就是 i ∗ 2 + 2 i * 2 + 2 i∗2+2。
但是用链式表示的二叉树,更有利于我们理解,所以一般我们都是用链式存储二叉树。
所以大家要了解,用数组依然可以表示二叉树。
3.二叉树的遍历方式
二叉树主要有两种遍历方式:
- 深度优先遍历:先往深走,遇到叶子节点再往回走。
- 广度优先遍历:一层一层的去遍历。
那么从深度优先遍历和广度优先遍历进一步拓展,才有如下遍历方式:
- 深度优先遍历
- 前序遍历(递归法,迭代法)
- 中序遍历(递归法,迭代法)
- 后序遍历(递归法,迭代法)
- 广度优先遍历
- 层次遍历(迭代法)
这里前中后,其实指的就是中间节点的遍历顺序
看如下中间节点的顺序,就可以发现,中间节点的顺序就是所谓的遍历方式
- 前序遍历:中左右
- 中序遍历:左中右
- 后序遍历:左右中

二叉树中深度优先和广度优先遍历实现方式,我们做二叉树相关题目,经常会使用递归的方式来实现深度优先遍历,也就是实现前中后序遍历,使用递归是比较方便的。
之前我们讲栈与队列的时候,就说过栈其实就是递归的一种是实现结构,也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现,这也是队列先进先出的特点所决定的,因为需要先进先出的结构,才能一层一层的来遍历二叉树。
4.二叉树的定义
class TreeNode: def __init__(self, value):self.value = valueself.left = Noneself.right = None
相关文章:
二叉树基础概念
1.二叉树种类 1.1 满二叉树 满二叉树:如果一棵二叉树只有度为 0 0 0 的结点和度为 2 2 2 的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。 如图所示: 这棵二叉树为满二叉树,也可以说深度为 k k k&…...
【MySQL】(1)数据库基础,库与表的增删查改,数据库的备份与还原
文章目录服务器,数据库,表关系MySQL 数据存储逻辑SQL 分类存储引擎库的操作查看数据库创建数据库查看创建语句删除数据库选择(切换)数据库查看当前选择的数据库修改数据库字符集和排序规则表的操作创建表查询表查询表结构插入数据…...
Python基础-01 变量
注释 注释的分类 在Python中,支持单行及多行注释 单行注释 使用#对代码进行说明,#右边的所有内容就是注释的内容,起辅助说明作用 # #右边的都是注释,解析器会忽略 print(hello world) #在控制台里打印一段话多行注释 多行注释中,允许换行,使用三个单引号开始,三个单引号结…...
springcloud2.1.0整合seata1.5.2+nacos2.10(附源码)
springcloud2.1.0整合seata1.5.2nacos2.10(附源码) 1.创建springboot2.2.2springcloud2.1.0的maven父子工程如下,不过多描述: 搭建过程中也出现很多问题,主要包括: 1.seataServer.properties配置文件的组…...
map原理
map源码结构体: type hmap struct {count int // 元素的个数B uint8 // buckets 数组的长度就是 2^B 个overflow uint16 // 溢出桶的数量buckets unsafe.Pointer // 2^B个桶对应的数组指针oldbuckets unsafe.Pointer // 发生扩容时࿰…...
[Ext JS]3.6 Ext JS 表格(Grid)概览
Grid, 翻译过来是网格, 也就是表格。 Grid 的基本构成 面板 :Ext.grid.Panel表格视图 :Ext.view.Table。 不直接使用, 通过面板的viewConfig配置项进行配置。比如可以用来配置表格中行是否跳色显示列: Ext.grid.column.Column。 表格中的列定义store , 表格的数据示例代码…...
关于使用云渲染的五大优势
在不影响质量或性能的情况下节省时间、金钱和资源,对于需要在通常较短且严格的期限内创建高质量 3D 内容的专业人士来说,云渲染都是最好的选择!云渲染作为数字媒体生产的最新趋势,与传统的渲染农场和机器相比具有许多优势…...
CSS基础样式
1.高度和宽度 .c1{height:300px;width:500px; } 注意事项: 宽度,支持百分比 行内标签:默认无效 块级标签:默认有效(右侧区域就算是空白,也不给占用) 2.块级和行内标签 css样式:标签…...
第03章_流程控制语句
第03章_流程控制语句 讲师:尚硅谷-宋红康(江湖人称:康师傅) 官网:http://www.atguigu.com 本章专题与脉络 流程控制语句是用来控制程序中各语句执行顺序的语句,可以把语句组合成能完成一定功能的小逻辑模…...
配电网电压调节及通信联系研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
stegano(图片隐写、摩斯密码)
附件是PDF,我们在选择内容时发现光标溢出了文本 说明这里还存在一些我们看不到的内容 直接CtrlA全选,CtrlC复制后新建一个纯文本文件 将复制的东西粘贴过去 粘贴后发现果然多出来了一些东西,提取出来 BABA BBB BA BBA ABA AB B AAB ABAA A…...
wsl安装torch_geometric
在官网选择需要的版本 选择安装途径,选择runfile 执行第一行,会下载一个文件到目录下 需要降低C的版本,否则 执行sudo sh cuda_11.1.0_455.23.05_linux.run,会出现 查看对应的文件,会有 可以加上override参数之后,…...
ASP.NET Core - 依赖注入(二)
2,NET Core 依赖注入的基本用法 话接上篇,这一章介绍 .NET Core 框架自带的轻量级 Ioc 容器下服务使用的一些知识点,大家可以先看看上一篇文章 [ASP.NET Core - 依赖注入(一)] 2.3 服务解析 通过 IServiceCollection 注册了服务之后…...
Scala之集合(1)
目录 集合介绍: 不可变集合继承图:编辑 可变集合继承图 数组: 不可变数组: 样例代码: 遍历集合的方法: 1.for循环 2.迭代器 3.转换成List列表: 4.使用foreach()函数&a…...
公网使用SSH远程登录macOS服务器【内网穿透】
文章目录前言1. macOS打开远程登录2. 局域网内测试ssh远程3. 公网ssh远程连接macOS3.1 macOS安装配置cpolar3.2 获取ssh隧道公网地址3.3 测试公网ssh远程连接macOS4. 配置公网固定TCP地址4.1 保留一个固定TCP端口地址4.2 配置固定TCP端口地址5. 使用固定TCP端口地址ssh远程前言…...
PVE相关的各种一键脚本(一键安装PVE)(一键开设KVM虚拟化的NAT服务器-自带内外网端口转发)
PVE 原始仓库:https://github.com/spiritLHLS/pve 前言 建议debian在使用前尽量使用最新的系统 非debian11可使用 debian一键升级 来升级系统 当然不使用最新的debian系统也没问题,只不过得不到官方支持 请确保使用前机器可以重装系统,…...
CSDN目录博客(zhaoshuangjian)
总目录 一、Java1.1 高并发1.2 多线程1.3 集合1.4 I/O1.5 异常1.6 事务1.7 锁机制1.8 JVM 二、数据库2.1 mysql2.1.1 mysql索引2.1.1 mysql锁2.1.1 mysql事务2.1.1 2.2 oracle2.3 postgresql2.4 达梦2.5 人大金仓kingbase 三、设计模式四、中间件4.1 缓存中间件-redis4.2 缓存中…...
uniapp人脸识别解决方案
APP端: 因为APP端无法使用uni的camera组件,最开始考虑使用内嵌webview的方式,通过原生dom调用video渲染画面然后通过canvas截图。但是此方案兼容性在ios几乎为0,如果app只考虑安卓端的话可以采用此方案。后面又想用live-pusher组件…...
hashlib模块
欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起探讨和分享Linux C/C/Python/Shell编程、机器人技术、机器学习、机器视觉、嵌入式AI相关领域的知识和技术。 hashlib模块专栏:《python从入门到实战》 哈希算法,也叫摘要算法。 加密&…...
NC65合并报表如何取消上报并退回以及注意事项和相关问题总结
NC65合并报表如何取消上报并退回? 在【企业绩效管理】-【合并报表】-【合并】-【合并执行】节点中,点击〖数据中心〗按钮,在弹出的〖合并报表数据中心〗界面中,点击〖报送管理〗-〖合并方案请求退回〗,然后到【合并综…...
别只点‘Passive’!深入理解Altium Designer引脚电气类型,从根源上杜绝原理图ERC错误
深入解析Altium Designer引脚电气类型:从原理到实践的设计规范 在电子设计自动化(EDA)领域,原理图设计是整个产品开发流程的基石。许多工程师在使用Altium Designer(AD)时,往往将注意力集中在布…...
收藏!AI技能进化全解析:从聊天搭子到行业专家的成长之路
本文回顾了AI技能的演进过程,从最初只能进行简单对话的聊天机器人,到如今能够理解行业规范、执行复杂任务的智能体。文章详细介绍了AI技能发展的五个阶段:初级聊天机器人、通过函数调用实现工具交互、通用接口MCP规范、智能体引擎赋予环境感知…...
MATLAB图像处理实战:用imfindcircles快速定位硬币边缘(附完整代码)
MATLAB图像处理实战:用imfindcircles快速定位硬币边缘(附完整代码) 在工业检测和医学影像分析中,圆形物体的精准定位往往是关键的第一步。无论是生产线上的硬币质量检查,还是显微镜下的细胞计数,快速准确地…...
leetcode 困难题 1505. 最多 K 次交换相邻数位后得到的最小整数
Problem: 1505. 最多 K 次交换相邻数位后得到的最小整数 从左到右遍历字符串的每个索引,对每个索引i,向后查找k窗口内的最小数字,右边界是min(n, ik1),删去这个最小数字,然后将这个最小数字插入到当前索引,…...
OpenCV实战:用Python+SIFT+八点算法搞定双目视觉匹配(附完整代码)
OpenCV实战:PythonSIFT八点算法实现双目视觉精准匹配 在计算机视觉领域,立体匹配是一个经典而富有挑战性的问题。想象一下,当你用双眼观察世界时,大脑能自动计算出物体的距离——这正是双目视觉系统要模拟的过程。本文将带你用Pyt…...
免环境配置:Qwen-Image定制镜像让4090D显卡快速跑通视觉语言模型
免环境配置:Qwen-Image定制镜像让4090D显卡快速跑通视觉语言模型 1. 引言 1.1 视觉语言模型的应用价值 在当今AI技术快速发展的背景下,视觉语言模型(VLM)已成为连接计算机视觉与自然语言处理的桥梁。这类模型能够理解图像内容并生成相关文本描述&…...
从电源到复位:深入拆解STM32最小系统每个电路模块的设计考量与选型避坑
从电源到复位:深入拆解STM32最小系统每个电路模块的设计考量与选型避坑 在嵌入式系统开发中,STM32系列微控制器因其出色的性能和丰富的外设资源而广受欢迎。然而,即使是看似简单的STM32最小系统设计,也蕴含着大量值得深入探讨的工…...
别再只用Canvas了!用Vue3组合式API优雅封装fabric.js的画笔与橡皮擦(附完整Hook代码)
重构Canvas交互:用Vue3组合式API封装fabric.js的工程化实践 在Web图形编辑领域,fabric.js以其强大的对象模型和交互能力成为许多开发者的首选。但当我们将它集成到Vue3项目中时,常常会遇到状态管理混乱、代码耦合度高的问题。本文将展示如何用…...
SecGPT-14B实战手册:Chainlit中集成Markdown渲染与代码块语法高亮
SecGPT-14B实战手册:Chainlit中集成Markdown渲染与代码块语法高亮 1. SecGPT-14B简介 SecGPT是由云起无垠推出的开源大语言模型,专门针对网络安全领域优化。该模型基于先进的自然语言处理技术,能够理解和生成与网络安全相关的专业内容。 S…...
HP-Socket技术演讲视频描述撰写指南:关键词与吸引力
HP-Socket技术演讲视频描述撰写指南:关键词与吸引力 【免费下载链接】HP-Socket High Performance TCP/UDP/HTTP Communication Component 项目地址: https://gitcode.com/gh_mirrors/hp/HP-Socket HP-Socket是一款高性能跨平台网络通信框架,专为…...
