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

数据结构:二叉树的基本概念

文章目录

  • 1. 二叉树的定义
  • 2. 二叉树的特点
  • 3. 特殊二叉树
    • 斜树
    • 满二叉树
    • 完全二叉树
  • 4. 二叉树的性质

1. 二叉树的定义

如果我们猜一个100以内的数字,该怎么猜才能理论最快呢?
第一种方式:从1,2一直猜到100, 反正数字都是100以内,总能猜到的
第二种方式:先猜50,如果比结果小,猜75;如果比结果大,猜25.最后也能猜到对应的值

很显然,第二种方式明显优于第一种方式.第一种方式的时间复杂度是 O ( N ) O(N) O(N),而第二种方式的时间复杂度是 O ( l o g N ) O(logN) O(logN).

对于这种在某个阶段都是两种结果的情形,比如开和关,0和1,真和假等等,都适合用树状结构来建模,而这种树就是之前说的很优秀的树状结构,叫做二叉树.


二叉树(Binary Tree)是n(n>=0)个结点的有限集合.

  • 该集合或者为空集(称为空二叉树).
  • 或者由一个根节点和两棵互不相交,分别称为根节点的左子树和右子树的二叉树组成.

在这里插入图片描述

2. 二叉树的特点

根据上面的二叉树的图片,我们可以得到二叉树的以下特点

  • 二叉树不存在度大于 2 的结点
    二叉树每个结点最多度为2,即最多有左右两个子树,不存在或者只有一颗子树是可以的.
  • 二叉树的子树有左右之分,次序不能随意颠倒,因此二叉树是有序树
    正如人的左脚和右脚不能随意颠倒,二叉树也分为左子树和右子树的;
    即使某个结点只有一棵子树,也是要分清楚是左子树还是右子树的

在这里插入图片描述

上图的两棵树虽然是同一棵树,但是不是同一棵二叉树


二叉树具有以下五种基本形态,任意的二叉树都是由下面的情况复合而成的
在这里插入图片描述

  • 空二叉树
  • 只有一个根结点
  • 根节点只有左子树
  • 根节点只有右子树
  • 根节点既有左子树又有右子树

如果只从形态上考虑,三个结点的树只有两种情况,就是下图的树1和后面四个中的任意一种.
但是对于二叉树这个有序树而言,左右子树是由区别的,所以下面五种情况都表示不同的二叉树.
在这里插入图片描述


现实中的二叉树很漂亮,正如在数据结构中,二叉树这个树形结构也占据很重要的地位一样,有时候数学的美和大自然的美都是相通的.

在这里插入图片描述

3. 特殊二叉树

斜树

所有的结点都只有左子树的叫左斜树,所有的结点都只有右子树的叫右斜树.
这两者统称为斜树.

在这里插入图片描述

其实,线性表就是一种特殊的斜树,但是两者的逻辑结构还是不一样的,线性表是一对一线性结构的,而斜树是一对多树形结构的


满二叉树

在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有的叶子都在同一层上,这样的二叉树称为满二叉树

在这里插入图片描述

满二叉树有以下特点

  • 叶子结点只能出现在最下一层
  • 非叶子结点的度一定是 2
  • 满二叉树的结点个数最多,叶子数最多.如果一个满二叉树有 K 层, 那么一共有 2 k − 1 2^k-1 2k1个结点

完全二叉树

对一个具有 n 个节点的二叉树按层序编号, 如果编号为 i( 1 ⩽ i ⩽ n 1\leqslant i \leqslant n 1in)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同, 则这颗二叉树称为完全二叉树.

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

最重要的是按层序编号
例如下面的三个二叉树,就不是完全二叉树.它们对应满二叉树的结点编号缺少了.
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

总而言之就是,除了最后一层的不满并且最后一层的从第一个结点开始是连续的,这就是完全二叉树.

完全二叉树有以下特点:

  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左部连续位置
  • 倒数两层,若有叶子结点,一定都在右部连续位置
  • 如果结点度为1, 则该结点只有左孩子
  • 同样节点数的二叉树,完全二叉树的深度最小

如果有h层, 那么完全二叉树的结点数为 [ 2 h − 1 , 2 h − 1 ] [2^{h-1}, 2^h - 1] [2h1,2h1]

4. 二叉树的性质

  1. 若规定根节点的层数为 1, 则一棵非空二叉树的第 i 层最多有 2 i − 1 2^{i-1} 2i1个结点.
  1. 若规定根节点的层数为 1, 则深度为 h 的二叉树的最大结点数是 2 h − 1 2^h - 1 2h1.
  1. 对任何一棵二叉树,如果度为 0 的叶子结点个数为 n 0 n_0 n0, 度为 2 的分支节点个数为 n 2 n_2 n2, 则有 n 0 = n 2 + 1 n_0 = n_2 + 1 n0=n2+1.
  1. 若规定根节点的层数为 1 , 具有n个结点的满二叉树的深度, h = l o g 2 ( n + 1 ) log_2(n + 1) log2(n+1).
  1. 对于具有 n 个结点的完全二叉树, 如果按照从上至下, 从左至右的数组顺序对所有结点开始从 0 编号, 则对于序号为 i 的结点有:
  • 若 i > 0, i位置结点的双亲序号: (i-1)/2; i=0, i为根节点编号, 无双亲结点.
  • 若 2i+1<n, 左孩子序号: 2i+1, 2i+1 >=n 则无左孩子
    i > 0, i位置结点的双亲序号: (i-1)/2**; i=0, i为根节点编号, 无双亲结点.
  • 若 2i+1<n, 左孩子序号: 2i+1, 2i+1 >=n 则无左孩子
  • 若 2i+2<n, 右孩子序号: 2i+2, 2i+2 >=n 则无右孩子

相关文章:

数据结构:二叉树的基本概念

文章目录 1. 二叉树的定义2. 二叉树的特点3. 特殊二叉树斜树满二叉树完全二叉树 4. 二叉树的性质 1. 二叉树的定义 如果我们猜一个100以内的数字,该怎么猜才能理论最快呢? 第一种方式:从1,2一直猜到100, 反正数字都是100以内,总能猜到的 第二种方式:先猜50,如果比结果小,猜75…...

利用Socks5代理IP加强跨界电商爬虫的网络安全

随着跨界电商的兴起&#xff0c;爬虫技术在这个领域变得越来越重要。然而&#xff0c;网络安全一直是一个值得关注的问题。在本文中&#xff0c;我们将讨论如何利用代理IP和Socks5代理来增强跨界电商爬虫的网络安全&#xff0c;确保稳定和可靠的数据采集&#xff0c;同时避免封…...

Spring学习笔记6 Bean的实例化方式

Spring学习笔记5 GoF之工厂模式_biubiubiu0706的博客-CSDN博客 Spring为Bean提供了多种实例化方式,通常包括4中(目的:更加灵活) 1.通过构造方法实例化 2.通过简单工厂模式实例化 3.通过factory-bean实例化 4.通过FactoryBean接口实例化 新建模块 spring-005 依赖 <!--S…...

大二毕设.3-网盘系统-用户模块讲解

目录 模块功能介绍 具体实现讲解 constants层&#xff1a;存放用户模块常量类 entity层&#xff1a;存放实体类&#xff0c;与数据库中的属性值基本保持一致 mapper层&#xff1a;对数据库进行数据持久化操作 service层&#xff1a;业务逻辑层&#xff0c;主要是针对具体…...

(Vue2)智慧商城项目

新增两个目录api、utils api接口模块&#xff1a;发送ajax请求的接口模块 utils工具模块&#xff1a;自己封装的一些工具方法模块 第三方组件库vant-ui PC端&#xff1a;element-ui&#xff08;element-plus&#xff09; ant-design-vue 移动端&#xff1a;vant-ui Mint UI…...

Nginx实战

虚拟主机 虚拟主机指的就是⼀个独⽴的站点&#xff0c;具有独⽴的域名&#xff0c;有完整的www服务&#xff0c;例如⽹站、FTP、邮件等 。Nginx⽀持多虚拟主机&#xff0c;在⼀台机器上可以运⾏完全独⽴的多个站点。⼀些草根流量站⻓&#xff0c;常会搭建个⼈站点进⾏资源分享交…...

day-57 代码随想录算法训练营(19)动态规划 part 17

647.回文子串 思路&#xff1a;动态规划 1.dp存储&#xff1a;判断以i开始&#xff0c;j结尾的字符串是否是回文串2.动态转移方程&#xff1a;当s[i]s[j]时&#xff0c;如果j-i<1,d[i][j]true; 如果 dp[i1][j-1]true&#xff0c;那么dp[i][j…...

在项目中,关于前端实现数据可视化的技术选择

前言 在项目中&#xff0c;数据可视化以图表、报表类型为主。 需求背景 技术框架是Vue2.x版本&#xff0c;组件库是Ant Design of Vue能够支撑足够多的图表类型开发图表大小/位置能够随意变动图表样式需要支持丰富多样的用户配置强大、开放的图表语法支持复杂的数据可视化场景…...

DT 卡通材质学习 一

渐变着色器 相交线 笔刷和卡通结合使用 修改器...

【游戏引擎架构】6.2 资源管理器

资源管理器可以分为离线部分系统和运行时系统 文章目录 离线资源管理数据库资产管道 运行时资源管理文件结构内存管理文件间引用 离线资源管理 数据库 UE的数据库可以直接浏览、编辑资产&#xff0c;看到运行时的状态&#xff1b;但也存在两个较大的缺点&#xff1a; 版本管…...

spring的ThreadPoolTaskExecutor装饰器传递调用线程信息给线程池中的线程

概述 需求是想在线程池执行任务的时候&#xff0c;在开始前将调用线程的信息传到子线程中&#xff0c;在子线程完成后&#xff0c;再清除传入的数据。 下面使用了spring的ThreadPoolTaskExecutor来实现这个需求. ThreadPoolTaskExecutor 在jdk中使用的是ThreadPoolExecutor…...

转载 - 洞察问题本质,解决工作难题

作者&#xff1a;关苏哲 高效管理者的三大技能 问题界定的6个问题 1.你所需要解决的问题是什么&#xff1f; 2.你为什么需要解决这个问题&#xff1f; 3.你期待的理想结果是什么&#xff1f; 4.这个问题包括哪些子问题&#xff1f; 5.你曾经尝试过哪些解决方式&#xff1f…...

关于计算机找不到d3dx9_43.dll,无法继续执行代码修复方法

d3dx9_43.dll是一个动态链接库文件&#xff0c;它是DirectX的一个组件&#xff0c;主要用于处理游戏中的图形、声音等多媒体元素。当这个文件丢失时&#xff0c;可能会导致以下问题&#xff1a; 1. 游戏无法正常运行&#xff1a;由于d3dx9_43.dll负责处理游戏中的多媒体元素&a…...

《从零开始的Java世界》01基本程序设计

《从零开始的Java世界》系列主要讲解Javase部分&#xff0c;从最简单的程序设计到面向对象编程&#xff0c;再到异常处理、常用API的使用&#xff0c;最后到注解、反射&#xff0c;涵盖Java基础所需的所有知识点。学习者应该从学会如何使用&#xff0c;到知道其实现原理全方位式…...

【数据开发】数据全栈知识架构,数据(平台、开发、管理、分析)

文章目录 一、数据全栈知识架构1、数据方法&#xff08;思维&#xff0c;统计学&#xff0c;实践&#xff0c;北极星&#xff09;2、数据工具&#xff1a;数据仓库3、数据规范 二、数据分析工具1、大数据平台2、数据开发&#xff1a;入库计算&#xff08;重点&#xff09;3、数…...

基于STM32的宠物托运智能控制系统的设计(第十七届研电赛)

一、功能介绍 使用STM32作为主控设备&#xff0c;通过DHT11温湿度传感器、多合一空气质量检测传感器以及压力传感器对宠物的托运环境中的温湿度、二氧化碳浓度和食物与水的重量进行采集&#xff0c;将采集到的信息在本地LCD显示屏上显示&#xff0c;同时&#xff0c;使用4G模块…...

数据结构的奇妙世界:实用算法与实际应用

文章目录 数据结构和算法的基本概念数据结构数组链表栈队列树图 算法 常见的数据结构和算法排序算法快速排序示例 数据结构的应用数据库管理系统图像处理网络路由 数据结构和算法的性能分析时间复杂度空间复杂度 如何更好地编写代码避免常见错误结论 &#x1f389;欢迎来到数据…...

uniapp实现表格冻结

效果图如下&#xff1a; 思路&#xff1a; 1.由于APP项目需要&#xff0c;起初想去插件市场直接找现成的&#xff0c;结果找了很久没找到合适的&#xff08;有的不支持vue2有的不能都支持APP和小程序&#xff09; 2.后来&#xff0c;就只能去改uni-table源码了&#xff0c;因…...

Spring面试题11:什么是Spring的依赖注入

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:说一说Spring的依赖注入 依赖注入(Dependency Injection)是Spring框架的一个核心特性,它是指通过外部容器将对象的依赖关系注入到对象中,从而…...

用于设计 CNN 的 7 种不同卷积

一 说明 最近对CNN架构的研究包括许多不同的卷积变体&#xff0c;这让我在阅读这些论文时感到困惑。我认为通过一些更流行的卷积变体的精确定义&#xff0c;效果和用例&#xff08;在计算机视觉和深度学习中&#xff09;是值得的。这些变体旨在保存参数计数、增强推理并利用目标…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...

Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目

应用场景&#xff1a; 1、常规某个机器被钓鱼后门攻击后&#xff0c;我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后&#xff0c;我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...

深度解析云存储:概念、架构与应用实践

在数据爆炸式增长的时代&#xff0c;传统本地存储因容量限制、管理复杂等问题&#xff0c;已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性&#xff0c;成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理&#xff0c;云存储正重塑数据存储与…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化

一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一&#xff0c;是基于哈希表的Map接口非同步实现。它允许使用null键和null值&#xff08;但只能有一个null键&#xff09;&#xff0c;并且不保证映射顺序的恒久不变。与Hashtable相比&#xff0c;Hash…...

Ray框架:分布式AI训练与调参实践

Ray框架&#xff1a;分布式AI训练与调参实践 系统化学习人工智能网站&#xff08;收藏&#xff09;&#xff1a;https://www.captainbed.cn/flu 文章目录 Ray框架&#xff1a;分布式AI训练与调参实践摘要引言框架架构解析1. 核心组件设计2. 关键技术实现2.1 动态资源调度2.2 …...