二叉树理论基础篇

这里写目录标题

    • 二叉树的种类
      • **满二叉树(Full Binary Tree)**
      • **完全二叉树(Complete Binary Tree)**
      • **二叉搜索树(Binary Search Tree,BST)**
      • 平衡二叉搜索树
    • 二叉树的存储方式
    • 二叉树的遍历方式
    • 二叉树的定义

二叉树的种类

满二叉树(Full Binary Tree)

  • 每个节点要么是叶子节点(没有子节点),要么有两个子节点。
  • 即每个非叶子节点都有两个子节点。

完全二叉树(Complete Binary Tree)

  • 除了最底层,其他层的节点都填满了,并且最底层的节点从左到右填充。
  • 最底层的节点可以有0到2个子节点,但必须从左到右排列。

之前我们刚刚讲过优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。

二叉搜索树(Binary Search Tree,BST)

  • 对于任意一个节点,左子树所有节点的值小于该节点的值,右子树所有节点的值大于该节点的值。递归满足这个要求。对于树没有要求。
  • 这使得二叉搜索树在进行查找、插入和删除操作时具有较好的性能。

平衡二叉搜索树

具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn,注意我这里没有说unordered_map、unordered_set,unordered_map、unordered_set底层实现是哈希表。

二叉树的存储方式

二叉树可以链式存储,也可以顺序存储。

那么链式存储方式就用指针, 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的,而链式存储则是通过指针把分布在各个地址的节点串联一起。

二叉树的遍历方式

一些同学用做了很多二叉树的题目了,可能知道前中后序遍历,可能知道层序遍历,但是却没有框架。

我这里把二叉树的几种遍历方式列出来,大家就可以一一串起来了。

二叉树主要有两种遍历方式:

  • 深度优先遍历:先往深走,遇到叶子节点再往回走。
  • 广度优先遍历:一层一层的去遍历。

在深度优先遍历中:有三个顺序,前中后序遍历, 有同学总分不清这三个顺序,经常搞混,我这里教大家一个技巧。这里前中后,其实指的就是中间节点的遍历顺序,只要大家记住 前中后序指的就是中间节点的位置就可以了。

二叉树的定义

刚刚我们说过了二叉树有两种存储方式顺序存储,和链式存储,顺序存储就是用数组来存,这个定义没啥可说的,我们来看看链式存储的二叉树节点的定义方式。

C++代码如下:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

大家会发现二叉树的定义 和链表是差不多的,相对于链表 ,二叉树的节点里多了一个指针, 有两个指针,指向左右孩子。

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/938250.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【376.2协议】国网_用电信息采集系统通信协议

【376.2协议】用电信息采集系统通信协议 文章目录 【376.2协议】用电信息采集系统通信协议1、帧格式2、各传输帧2.1 控制域 C (一个字节|8个位)2.2 用户数据区格式2.2.1 信息域2.2.2 地址域2.2.3 应用数据域 3、式例 1、帧格式 帧格式定义规则起始字符固定报文头( …

鸿蒙项目云捐助第十一讲鸿蒙App应用的捐助成功自定义对话框组件实现

在生活中,用户做了一个好事后,很多场合都会收到一份感谢。在捐助的行业也是一样的,用户捐出了一片爱心,就会收获一份温情。这里的温情是通过自定义对话框实现的。 一、通过自定义对话框组件实现捐款成功的信息页 这里用户捐款成…

leetcode区间部分笔记

区间部分 1. 汇总区间2. 合并区间3. 插入区间4. 用最少数量的箭引爆气球 1. 汇总区间 给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并…

spring学习(spring-bean实例化(静态工厂))

目录 一、spring容器实例化bean的几种方式。 二、spring容器使用静态工厂方式实现bean实例化。 (1)基本介绍。 1、静态工厂? 2、"factory-method"属性。 3、二种操作方式。 方法一。 方法二。 (2)demo(案例)…

25年宁德时代社招在职晋升Verify测评SHL题库:语言理解+数字推理考什么?

宁德时代的社招测评采用Verify系统,主要分为两大核心部分:语言理解和数字推理。 1. **语言理解部分**:包括阅读理解、逻辑填空和语句排序等题型。要求应聘者在17分钟内完成30题,旨在考察应聘者的阅读速度、理解准确性和逻辑性。 …

2024数证杯初赛

计算机取证 请根据计算机检材,回答以下问题:(32个小题,共76分 1.[填空题对计算机镜像进行分析,计算该镜像中ESP分区的SM3值后8位为?(答案格式:大写字母与数字组合,如:D…

典型案例 | 旧PC新蜕变!东北师范大学依托麒麟信安云“旧物焕新生”

东北师范大学始建于1946年,坐落于吉林省长春市,是中国共产党在东北地区创建的第一所综合性大学。作为国家“双一流”建设高校,学校高度重视教学改革和科技创新,校园信息化建设工作始终走在前列。基于麒麟信安云,东北师…

项目二十三:电阻测量(需要简单的外围检测电路,将电阻转换为电压)测量100,1k,4.7k,10k,20k的电阻阻值,由数码管显示。要求测试误差 <10%

资料查找: 01 方案选择 使用单片机测量电阻有多种方法,以下是一些常见的方法及其原理: 串联分压法(ADC) 原理:根据串联电路的分压原理,通过测量已知电阻和待测电阻上的电压,计算出…

ST-Linker V2 烧录器详解说明文档

目录 ST-Linker v2烧录器介绍 STM8烧录口 STM32烧录接口 JTAG烧录接口 ​​​​​​​ ​​​​​​​ ​​​​​​​ 编写不易,仅供学习,请勿搬运,感谢理解 ST-Linker v2烧录器介绍 图片中是两种IC芯片的烧录器&#x…

在Centos7上安装MySQL数据库 How to install MySQL on Centos 7

执行以下命令,下载并安装MySQL。 wget http://dev.mysql.com/get/mysql57-community-release-el7-10.noarch.rpm && yum -y install mysql57-community-release-el7-10.noarch.rpm && yum install -y mysql-community-server --nogpgcheck执行以下…

FireFox火狐浏览器企业策略禁止更新

一直在用火狐浏览器,但是经常提示更新,进入浏览器右上角就弹出提示,比较烦。多方寻找,一直没有找到合适的方案,毕竟官方没有给出禁用检查更新的选项,甚至about:config里都没有。 最终找到了通过企业策略控…

【Qt】按钮类控件:QPushButton、QRadioButton、QCheckBox、ToolButton

目录 QPushButton 例子: QRadioButton 例子: 按钮的常见信号函数 单选按钮分组 例子: QCheckButton 例子: QToolButton QWidget的常见属性及其功能对于它的派生类控件都是有效的(也就是Qt中的各种控件),包括…

SpringBoot3 升级介绍

优质博文:IT-BLOG-CN 一、项目背景 截止2023.05.18,springboot发布了最新版本3.1.0。而在我们开发项目中,springboot一直使用的是1.5.8版本(相差6年的维护更新)。版本差距较大,很多新功能未能得到使用。例如近几年Loom的兴起&am…

运筹说 第130期 | 对策论引言

通过对对策论基础知识进行梳理和总结,小编绘制了《对策论思维导图》,如下图所示,对策论章节一共包含4个小节。 第1小节是对策论引言。介绍了对策论的基本概念,包含对策行为和对策论、对策现象的三要素、对策问题举例及对策的分类…

Windows 与 Linux 下 Ping IPv6 地址 | 常用网络命令

注:本文为网络命令相关文章合辑。 未整理去重。 一、IPv6 概述 IPv6 即 “Internet 协议版本 6”,因 IPv4 地址资源面临耗尽问题而被引入以替代 IPv4。IPv6 则提供了理论上多达 2 128 2^{128} 2128 个地址,有效解决地址不足困境。 IPv6 具…

密码学——密码学概述、分类、加密技术(山东省大数据职称考试)

大数据分析应用-初级 第一部分 基础知识 一、大数据法律法规、政策文件、相关标准 二、计算机基础知识 三、信息化基础知识 四、密码学 五、大数据安全 六、数据库系统 七、数据仓库. 第二部分 专业知识 一、大数据技术与应用 二、大数据分析模型 三、数据科学 密码学 大数据…

Android Studio、JDK、AGP、Gradle、kotlin-gradle-plugin 兼容性问题

文章目录 问题:解决办法:gradle与 java的版本兼容AGP与Gradle的版本兼容kotlin 与 jvm 的版本兼容KGP、Gradle、AGP兼容关系kotlin 与 java 的编译版本配置 问题: 你从githb上clone了一个项目,本地跑的时候,各种报错。…

ChatGPT搜索全新升级,向全体用户开放,近屿智能助力AI行业发展

12月17日,OpenAI在第八天直播中正式宣布ChatGPT搜索功能全面升级,并即日起对所有ChatGPT用户开放。此次更新不仅带来了显著的性能提升,还引入了多项突破性功能,如更快的搜索速度、全新的地图体验以及YouTube视频嵌入,为…

VSCode编辑+GCC for ARM交叉编译工具链+CMake构建+OpenOCD调试(基于STM32的标准库/HAL库)

本文以【STM32F103ZET6】单片机作为示例来进行演示,标准库/HAL库的工程是通用的,修改CMakeLists.txt里面的源文件和头文件引用部分即可。 更多细节请参考【VSCode编辑GCC for ARM交叉编译工具链Makefile构建OpenOCD调试(基于STM32的标准库&am…

ResNet网络:深度学习中的革命性架构

目录 ​编辑 引言 ResNet网络的特点 1. 残差块(Residual Block) 2. 恒等映射(Identity Mapping) 3. 深层网络训练 4. Batch Normalization 5. 全局平均池化 6. 灵活的结构 ResNet的应用案例 ResNet的研究进展 实战案例…