代码随想录算法训练营第14天 part01 | 二叉树理论基础篇

代码随想录

二叉树理论基础篇

二叉树的种类

二叉树有两种主要的形式:满二叉树和完全二叉树

满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。
在这里插入图片描述
这棵二叉树为满二叉树,也可以说深度为k,有2^k-1个节点的二叉树。

完全二叉树

在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层(h从1开始),则该层包含 1~ 2^(h-1) 个节点。
在这里插入图片描述
优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。

二叉搜索树

二叉搜索树是有数值的了,二叉搜索树是一个有序树。

若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉排序树

平衡二叉搜索树

平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
在这里插入图片描述
C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn,注意我这里没有说unordered_map、unordered_set,unordered_map、unordered_set底层实现是哈希表。

二叉树的存储

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

那么链式存储方式就用指针顺序存储的方式就是用数组
在这里插入图片描述
顺序存储的方式如图:
在这里插入图片描述
用数组来存储二叉树如何遍历的呢?

如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。

二叉树的遍历

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

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

深度优先遍历

	1、前序遍历(递归法,迭代法)
	2、中序遍历(递归法,迭代法)
	3、后序遍历(递归法,迭代法)

广度优先遍历

层次遍历(迭代法)

这里前中后,其实指的就是中间节点的遍历顺序

前序遍历:中左右
中序遍历:左中右
后序遍历:左右中

在这里插入图片描述
最后再说一说二叉树中深度优先和广度优先遍历实现方式,我们做二叉树相关题目,经常会使用递归的方式来实现深度优先遍历,也就是实现前中后序遍历,使用递归是比较方便的。

之前我们讲栈与队列的时候,就说过栈其实就是递归的一种实现结构,也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现,这也是队列先进先出的特点所决定的,因为需要先进先出的结构,才能一层一层的来遍历二叉树。

在现场面试的时候 面试官可能要求手写代码,所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。

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;
    }
}

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

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

相关文章

2023年迟到的年终总结

前言 一年又一年,过的好快啊。本以为上一年是黑云压城城欲摧,2023年可以甲光向日金鳞开,但是没想到23年更是黑暗啊,人生嘛总是十之八九不如意,一年的经历可以大概的概括为,业务转型的Q1,压力倍增…

悲观锁(Pessimistic Locking)是一种数据库锁定机制

悲观锁(Pessimistic Locking)是一种数据库锁定机制,用于防止多个事务同时修改同一数据记录。以下是关于悲观锁的一些详细信息: 锁定数据:当事务对一条记录进行操作时,悲观锁会阻止其他事务对这条记录进行修…

2024年全新的抖店电商创业玩法,一个月多赚大几千!实操教程在这

大家好,我是电商花花。 新一年,新征程,一些打工人回到自己的岗位上做着按部就班的工作。 然后也有一些创业的朋友就开始寻找着2024年的赚钱新机会和新风口。 作为在电商创业将近8年的我,预测2024年的风口依然是电商渠道&#x…

【Redis】基于Redis实现共享Session登录

用户登录是一种常用功能。这里记录一下基于Redis实现用户登录的代码。  下面是登录的流程图: 用户先提交手机号和验证码,服务器以手机号为key校验redis中存储的验证码,存在,则查询数据库中是否存在用户,不存在则创建…

【Quixel Mixer】简单介绍

一、下载 官网下载地址:Quixel Mixer - All-in-one texturing & material creation tool 下载好之后双击exe来安装 等待安装完成 下载后打开,新建一个工程和Mix 二、界面介绍 我们先将软件界面分为如下3个部分 1号区域为菜单栏 2号区域介绍 2号…

Windows Docker 安装

Docker 并非是一个通用的容器工具,它依赖于已存在并运行的 Linux 内核环境。 Docker 实质上是在已经运行的 Linux 下制造了一个隔离的文件环境,因此它执行的效率几乎等同于所部署的 Linux 主机。 因此,Docker 必须部署在 Linux 内核的系统上…

Linux —— 定时任务(sleep、crontab、at)

目录 1、使用 sleep 来完成定时任务 2、使用 crontab 来进行定时任务 3、使用 at 来执行单次的定时任务 1、使用 sleep 来完成定时任务 sleep n 等待 n 秒再继续往后执行 usleep n 等待 n 微秒再继续往后执行(1 秒等于 1 000 000 微秒&#xf…

聚道云如何实现薪人薪事与金蝶云无缝对接,破解财务难题?

一、客户介绍 某科技有限责任公司是一家在信息技术领域具有显著影响力的企业,长期致力于为企业提供全面的解决方案和技术支持。在业务范围上,该公司覆盖了多个关键领域,包括云计算、大数据、人工智能等前沿技术。公司不仅提供定制化的技术解…

从资金管理的角度谈谈个人怎样交易现货白银

刚进入现货白银市场,个人要怎么交易现货白银的?这就涉及现货白银交易生涯的开启问题,开头开的好,我们整个交易生涯都将会有所裨益,所以我们要为个人怎样交易现货白银开个好头。下面我们就从资金管理的角度出发&#xf…

可视化搭建一个智慧零售订单平台

前言 智慧零售行业是在数字化浪潮中快速发展的一个领域,它利用先进的信息技术和大数据分析来提升零售业务的效率和顾客体验。智慧零售订单平台,具有跨平台、数据智能清洗和建模,以及更加丰富的数据展示形式等优势。智慧零售订单平台可以以文…

1.gradle编译和运行

1.在Windows 项目的根目录下使用.\gradlew.bat build命令进行编译。 如果出错的原因是连接超时: Exception in thread “main” java.io.IOException: Downloading from https://services.gradle.org/distributions/gradle-8.6-bin.zip failed: timeout (10000ms) a…

薄板/厚板模态分析Matlab有限元编程 | 【源码+理论文本】|板单元|板壳单元|Mindlin Reissner

专栏导读 作者简介:工学博士,高级工程师,专注于工业软件算法研究本文已收录于专栏:《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现,并提供所有案例完整源码;2.单元…

软件测试方法 -- 等价类边界值

测试用例的定义 测试用例是为了特定的目的而设计的一组测试输入、执行条件和预期的结果,以便测试是否满足某个特定需求。通过大量的测试用例来检验软件的运行效果,他是指导测试工作进行的依据。 下面我们介绍几种常用的黑盒测试方法 等价类划分法 定…

挑战杯 车位识别车道线检测 - python opencv

0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 深度学习 机器视觉 车位识别车道线检测 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐! 🥇学长这里给一个题目综合评分(每项满分5分) …

BOM(物料清单)是什么?在生产管理中有什么用?

BOM(物料清单)是什么?在生产管理中有什么用? 一、什么是BOM (物料清单)? 举个例子,做一双运动鞋,需要的配料可以笼统的分为鞋身和鞋带,那么由鞋身和鞋带组成…

部署高斯喷射项目gaussian-splatting

硬件要求 支持 CUDA 的 GPU,具有 7.0 的计算能力24 GB VRAM 软件要求 Conda用于 PyTorch 扩展的 C 编译器(Visual Studio 2019) CUDA SDK 11 for PyTorch 扩展,在 Visual Studio 之后安装C 编译器和 CUDA SDK 必须兼容 拉取源码 …

AI实景无人自动直播间怎么搭建?三步教你轻松使用

最近很多朋友看到AI自动直播带货玩法,也想开启自己的自动直播间,但还是有些问题比较担心,这种自动讲解、自动回复做带货的直播间是不是很麻烦? 实景无人自动直播 ​ 实际上这种直播间搭建相当简单便捷!今天跟着笔者&…

sqlserver字段2按字段1分组后;合并字段2

效果 相同dzbm的mc通过‘;’合并 sqlserver语句 按字段dzbm分组,有相同dzbm的mc通过 ;合并成一个字段,其它字段都选择第一个 SELECT dzbm, STUFF((SELECT DISTINCT ; + mc FROM tablenameWHERE dzbm = p.dzbm FOR XML PATH()), 1

PHP反序列化--pop链

目录 一、了解pop链 1、pop链: 2、pop链触发规则: (1)通过普通函数触发: (2)通过魔术方法触发: 3、pop链魔术方法例题: 一、了解pop链 1、pop链: pop链…

力扣大厂热门面试算法题 43-45

43. 字符串相乘,44. 通配符匹配,45. 跳跃游戏 II,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.18 可通过leetcode所有测试用例。 目录 43. 字符串相乘 解题思路 完整代码 Python Java 44. 通配符…