二叉树理论基础知识点
二叉树的种类
在我们解题过程中二叉树有两种主要的形式:满二叉树和完全二叉树
满二叉树
满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。
如图所示:
这棵二叉树为满二叉树,也可以说深度为k,有2^k-1个节点的二叉树。
完全二叉树
什么是完全二叉树?
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。
大家要自己看完全二叉树的定义,很多同学对完全二叉树其实不是真正的懂了。
我来举一个典型的例子如题:
相信不少同学最后一个二叉树是不是完全二叉树都中招了。
之前我们刚刚讲过优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。
二叉搜索树
前面介绍的树,都没有数值的,而二叉搜索树是有数值的了,二叉搜索树是一个有序树。
- 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树
平衡二叉搜索树
平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
如图:
最后一棵 不是平衡二叉树,因为它的左右两个子树的高度差的绝对值超过了1。
C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn,注意我这里没有说unordered_map、unordered_set,unordered_map、unordered_map底层实现是哈希表。
所以大家使用自己熟悉的编程语言写算法,一定要知道常用的容器底层都是如何实现的,最基本的就是map、set等等,否则自己写的代码,自己对其性能分析都分析不清楚!
二叉树的存储方式
二叉树可以链式存储,也可以顺序存储。
那么链式存储方式就用指针, 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的,而链式存储则是通过指针把分布在各个地址的节点串联一起。
链式存储如图:
链式存储是大家很熟悉的一种方式,那么我们来看看如何顺序存储呢?
其实就是用数组来存储二叉树,顺序存储的方式如图:
用数组来存储二叉树如何遍历的呢?
如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。
但是用链式表示的二叉树,更有利于我们理解,所以一般我们都是用链式存储二叉树。
所以大家要了解,用数组依然可以表示二叉树。
二叉树的遍历方式
关于二叉树的遍历方式,要知道二叉树遍历的基本方式都有哪些。
一些同学用做了很多二叉树的题目了,可能知道前中后序遍历,可能知道层序遍历,但是却没有框架。
我这里把二叉树的几种遍历方式列出来,大家就可以一一串起来了。
二叉树主要有两种遍历方式:
- 深度优先遍历:先往深走,遇到叶子节点再往回走。
- 广度优先遍历:一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式,后面在介绍图论的时候 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展,才有如下遍历方式:
- 深度优先遍历
- 前序遍历(递归法,迭代法)
- 中序遍历(递归法,迭代法)
- 后序遍历(递归法,迭代法)
- 广度优先遍历
- 层次遍历(迭代法)
在深度优先遍历中:有三个顺序,前中后序遍历, 有同学总分不清这三个顺序,经常搞混,我这里教大家一个技巧。
这里前中后,其实指的就是中间节点的遍历顺序,只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序,就可以发现,中间节点的顺序就是所谓的遍历方式
- 前序遍历:中左右
- 中序遍历:左中右
- 后序遍历:左右中
大家可以对着如下图,看看自己理解的前后中序有没有问题。
最后再说一说二叉树中深度优先和广度优先遍历实现方式,我们做二叉树相关题目,经常会使用递归的方式来实现深度优先遍历,也就是实现前中后序遍历,使用递归是比较方便的。
之前我们讲栈与队列的时候,就说过栈其实就是递归的一种实现结构,也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现,这也是队列先进先出的特点所决定的,因为需要先进先出的结构,才能一层一层的来遍历二叉树。
这里其实我们又了解了栈与队列的一个应用场景了。
具体的实现我们后面都会讲的,这里大家先要清楚这些理论基础。
二叉树的定义
刚刚我们说过了二叉树有两种存储方式顺序存储,和链式存储,顺序存储就是用数组来存,这个定义没啥可说的,我们来看看链式存储的二叉树节点的定义方式。
C++代码如下:
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
大家会发现二叉树的定义 和链表是差不多的,相对于链表 ,二叉树的节点里多了一个指针, 有两个指针,指向左右孩子。
这里要提醒大家要注意二叉树节点定义的书写方式。
在现场面试的时候 面试官可能要求手写代码,所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。
因为我们在刷leetcode的时候,节点的定义默认都定义好了,真到面试的时候,需要自己写节点定义的时候,有时候会一脸懵逼!
其他语言版本
JavaScript:
function TreeNode(val, left, right) {this.val = (val===undefined ? 0 : val)this.left = (left===undefined ? null : left)this.right = (right===undefined ? null : right)
}
Java:
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}
Python:
class TreeNode: def __init__(self, value):self.value = valueself.left = Noneself.right = None
相关文章:

二叉树理论基础知识点
二叉树的种类 在我们解题过程中二叉树有两种主要的形式:满二叉树和完全二叉树 满二叉树 满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。 如图所示: 这…...

【算法基础】堆⭐⭐⭐
一、堆 1. 堆的概念 堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质: (1)堆中某个结点的值总是不大于或不小于其父结点的值; (2)堆总是一棵完全二叉树。 将根结点最大的堆叫做最大堆或大根堆,根结点…...

时序预测 | MATLAB实现CNN-SVM卷积支持向量机时间序列预测
时序预测 | MATLAB实现CNN-SVM卷积支持向量机时间序列预测 目录时序预测 | MATLAB实现CNN-SVM卷积支持向量机时间序列预测预测效果基本介绍研究回顾程序设计参考资料预测效果 基本介绍 CNN-SVM预测模型将深度学习模型作为特征学习器,将SVM 支持向量机 作为训练器进行…...

【TypeScrip】TypeScrip的任意类型(Any 类型 和 unknown 顶级类型):
文章目录一、安转依赖:【1】nodejs 环境执行ts【2】使用ts-node二、Any 类型 和 unknown 顶级类型【1】没有强制限定哪种类型,随时切换类型都可以 我们可以对 any 进行任何操作,不需要检查类型【2】声明变量的时候没有指定任意类型默认为any【…...

智能洗地机什么牌子好?智能洗地机排行
要说家庭清洁热门的产品,洗地机肯定首当其冲,集洗吸拖为一体的清洁工具,省时又省力,可谓是家里清洁好助手,今天笔者就为大家介绍几款重量轻、噪音轻、拖地干净的洗地机! 一、CEYEE希亦T800洗地机 在国内,洗…...

【数据结构与算法】链表1:移除链表 设计链表链表反转(双指针法、递归法)
文章目录今日任务1.链表理论基础(1)什么是链表?(2)链表的类型(3)链表的存储方式(4)链表的定义(5)链表的操作(6)性能分析2.…...

山东大学软件学院面向对象简答题整理【个人向】
面向对象简答题整理【个人向】 0.试用面向对象语言简述改写和重定义的异同,以及方法绑定时的差别 改写是子类的方法和父类的方法具有相同的方法名和类型签名重定义是子类的方法和父类的方法方法名相同但类型签名不同在方法绑定时,改写是动态绑定&#…...

JAVA时间类及JAVA8新时间类
文章目录Java旧时间类关系图GMT、时间戳、统一标准时间、时区Java时间类创建时间类示例java.text.DateFormat时间格式转换java.util.Calendar总结Java时间类Java8新时间类InstantCloc…...

ASEMI代理FGH60N60SFD,安森美FGH60N60SFD原装IGBT
编辑-Z 安森美FGH60N60SFD原装IGBT参数: 型号:FGH60N60SFD 集电极到发射极电压(VCES):600V 栅极到发射极电压(VGES):20V 收集器电流(IC):120…...
【云原生之Docker实战】使用dokcer部署web端vscode
【云原生之Docker实战】使用dokcer部署web端vscode 一、vscode-server介绍二、检查本地docke环境1.检查系统版本2.检查docker版本3.检查docker状态三、下载vscode镜像四、部署vscode-server1.创建安装目录2.创建vscode容器3.查看vscode容器状态4.查看vscode容器日志五、访问vsc…...

Docker安装Tomcat、mysql、redis
目录 前言 一、安装Tomcat 二、安装mysql (一)简单版 (二)实战版 三、安装redis 前言 镜像可以先去Docker Hub Container Image Library | App Containerization 左上角搜,然后点进入可以看到具体的命令&#…...
【python 基础篇 八】python的常用数据类型操作-------集合
目录1.集合的基本概念2.集合的定义2.1 可变集合 set定义2.2 不可变集合 fronzenset 定义2.3 集合定义的注意事项3.单一集合的常用操作4. 集合之间操作4.1 交集4.2 并集4.3 差集4.4 判定1.集合的基本概念 无序的,不可随机访问的,不可重复的元素集合与数学…...
Spring框架中问题补充
BeanFactory 和 ApplicationContext BeanFactory和ApplicationContext是接口。BeanFactory接口时spring框架的顶层接口,定义管理bean的最基本的方法,例如获取实例、判断等功能。 DefaultListableBeanFactory实现BeanFactory 接口,是主要的创建bean的工…...

【Leedcode】顺序表必备的三道面试题(附图解)
顺序表必备的三道面试题(附图解) 文章目录顺序表必备的三道面试题(附图解)前言一、第一题1.题目2.思路图解3.源码二、第二题1.题目2.思路图解3.源码三、第三题1.题目2.思路图解3.源码总结前言 本文给大家介绍三道顺序表学习过程中…...

SOFA Weekly|开源人、本周贡献 issue 精选
SOFA WEEKLY | 每周精选 筛选每周精华问答,同步开源进展欢迎留言互动~SOFAStack(Scalable Open Financial Architecture Stack)是蚂蚁集团自主研发的金融级云原生架构,包含了构建金融级云原生架构所需的各个组件&#…...

2023美赛 ICM E题详细版思路
问题E:光污染注:楷体为题目原文,宋体为思路部分首先,我们需要考虑的就是美赛ABEF的核心问题,数据。这里E题是以光污染为背景的题目,首当其冲的我们就需要收集一些数据以支撑我们的模型。对于E题提出的问题&…...

【LeetCode】剑指 Offer(3)
目录 写在前面: 题目:剑指 Offer 09. 用两个栈实现队列 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 写在前面&…...

springboot simple (13) springboot Elasticsearch(Elasticsearch8.5.1)
这里首先简单的介绍了Elasticsearch,然后实现了springboot集成Elasticsearch。 版本: Elasticsearch:v8.5.1 Kibana:v8.5.1 springboot集成elasticsearch有两种方式。 1)rest客户端RestHingLevelClient; …...

《爆肝整理》保姆级系列教程python接口自动化(十七)--Json 数据处理---一次爬坑记(详解)
简介 有些 post 的请求参数是 json 格式的,这个前面发送post 请求里面提到过,需要导入 json模块处理。现在企业公司一般常见的接口因为json数据容易处理,所以绝大多数返回数据也是 json 格式的,我们在做判断时候,往往只…...

分享111个HTML旅游交通模板,总有一款适合您
分享111个HTML旅游交通模板,总有一款适合您 111个HTML旅游交通模板下载链接:https://pan.baidu.com/s/1VHJSBVJbj4PQpPAwxysJBg?pwd8b17 提取码:8b17 Python采集代码下载链接:采集代码.zip - 蓝奏云 汽车租赁平台网页模板 汽…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...

【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
使用python进行图像处理—图像滤波(5)
图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值,以达到平滑(去噪)、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算,…...
ubuntu清理垃圾
windows和ubuntu 双系统,ubuntu 150GB,开发用,基本不装太多软件。但是磁盘基本用完。 1、查看home目录 sudo du -h -d 1 $HOME | grep -v K 上面的命令查看$HOME一级目录大小,发现 .cache 有26GB,.local 有几个GB&am…...