当前位置: 首页 > news >正文

二叉树理论基础知识点

二叉树的种类

在我们解题过程中二叉树有两种主要的形式:满二叉树和完全二叉树

满二叉树

满二叉树:如果一棵二叉树只有度为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。

但是用链式表示的二叉树,更有利于我们理解,所以一般我们都是用链式存储二叉树。

所以大家要了解,用数组依然可以表示二叉树。

二叉树的遍历方式

关于二叉树的遍历方式,要知道二叉树遍历的基本方式都有哪些。

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

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

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

  1. 深度优先遍历:先往深走,遇到叶子节点再往回走。
  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旧时间类关系图![在这里插入图片描述](https://img-blog.csdnimg.cn/e2c2c26c841e40bdb9cc85d0fc4bc1df.png)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 - 蓝奏云 汽车租赁平台网页模板 汽…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...