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

二叉树详解

这里写目录标题

  • 前言
  • 树型结构(了解)
    • 树常见的概念
    • 树的表示形式(了解)
    • 树的应用
  • 二叉树
    • 概念
    • 两种特殊的二叉树
    • 二叉树的性质(重要)
    • 二叉树的存储
    • 二叉树的基本操作

前言

本篇博客讲述了以下几个知识点

  1. 树的基本概念
  2. 二叉树概念及特性
  3. 二叉树的基本操作

树型结构(了解)

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点

  • 有一个特殊的结点,称为根结点,根结点没有前驱结点除根结点外,其余结点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm,其中每一个集合Ti (1 <= i <=m) 又是一棵与树类似的子树。
  • 每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
  • 树是递归定义的。

树的图片
在这里插入图片描述
注意:树形结构中,子树之间不能有交集,否则就不是树形结构

树常见的概念

  • 结点的度:一个结点含有子树的个数称为该结点的度;
  • 树的度:一棵树中,所有结点度的最大值称为树的度;
  • 叶子结点或终端结点:度为0的结点称为叶结点;
  • 双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点;
  • 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点;
  • 根结点:一棵树中,没有双亲结点的结点;
  • 树的高度或深度:树中结点的最大层次;
  • 非终端结点或分支结点:度不为0的结点;
  • 兄弟结点:具有相同父结点的结点互称为兄弟结点;
  • 堂兄弟结点:双亲在同一层的结点互为堂兄弟;
  • 结点的祖先:从根到该结点所经分支上的所有结点;
  • 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。
  • 森林:由m(m>=0)棵互不相交的树组成的集合称为森林

树的表示形式(了解)

实际中树有很多种表示方式,如:双亲表示法,孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。最常用的是孩子兄弟表示法

class Node {int value; // 树中存储的数据Node firstChild; // 第一个孩子引用Node nextBrother; // 下一个兄弟引用
}

树的应用

文件系统管理(目录和文件)
在这里插入图片描述

二叉树

概念

一棵二叉树是结点的一个有限集合,该集合:

  1. 或者为空
  2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成
    在这里插入图片描述
    从上图可以看出:
  3. 二叉树不存在度大于2的结点
  4. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

两种特殊的二叉树

  1. 满二叉树: 一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树。也就是说,如果一棵二叉树的层数为K,且结点总数是 ,则它就是满二叉树。
  2. 完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
    在这里插入图片描述

二叉树的性质(重要)

  1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 (i>0)个结点
  2. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是 (k>=0)
  3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1
  4. 具有n个结点的完全二叉树的深度k为 上取整
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的结点有:
    若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
    若2i+1<n,左孩子序号:2i+1,否则无左孩子
    若2i+2<n,右孩子序号:2i+2,否则无右孩子

二叉树的存储

二叉树的存储结构分为:顺序存储和类似于链表的链式存储。
二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式,具体如下:

// 孩子表示法
class Node {int val; // 数据域Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {int val; // 数据域Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树Node parent; // 当前节点的根节点
}

二叉树的基本操作

  1. 前中后序遍历

学习二叉树结构,最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如:打印节点内容、节点内容加1。 遍历是二叉树上最重要的操作之一,是二叉树上进行其它运算之基础。

在遍历二叉树时,如果没有进行某种约定,每个人都按照自己的方式遍历,得出的结果就比较混乱,如果按照某种规则进行约定,则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点,L代表根节点的
左子树,R代表根节点的右子树,则根据遍历根节点的先后次序有以下遍历方式:
NLR:前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。
LNR:中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
LRN:后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点

  1. 层序遍历
    层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
    在这里插入图片描述

相关文章:

二叉树详解

这里写目录标题 前言树型结构(了解)树常见的概念树的表示形式&#xff08;了解&#xff09;树的应用 二叉树概念两种特殊的二叉树二叉树的性质(重要)二叉树的存储二叉树的基本操作 前言 本篇博客讲述了以下几个知识点 树的基本概念二叉树概念及特性二叉树的基本操作 树型结构…...

Git的核心概念:探索Git中的提交、分支、合并、标签等核心概念,深入理解其作用和使用方法

&#x1f337;&#x1f341; 博主 libin9iOak带您 Go to New World.✨&#x1f341; &#x1f984; 个人主页——libin9iOak的博客&#x1f390; &#x1f433; 《面试题大全》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33…...

JAVA设计模式——23种设计模式详解

一、什么是设计模式&#x1f349; 设计模式&#xff08;Design pattern&#xff09; 是解决软件开发某些特定问题而提出的一些解决方案也可以理解成解决问题的一些思路。通过设计模式可以帮助我们增强代码的可重用性、可扩充性、 可维护性、灵活性好。我们使用设计模式最终的目…...

Oracle输出文本平面(CSV、XML)文本数据详细过程

此过程是提供给前端,调用的接口,为报表提供”下载“功能。以下是本人在测试环境的测试,有什么不足的地方,请留言指教,谢谢。 1、测试表 分别对测试表输出csv、xml两种格式文件数据。前期的准备工作。 --在服务器端创建directory,用管理员用户 create or replace directo…...

基于C++的QT基础教程学习笔记

文章目录&#xff1a; 来源 教程社区 一&#xff1a;QT下载安装 二&#xff1a;注意事项 1.在哪里写程序 2.如何看手册 3.技巧 三&#xff1a;常用函数 1.窗口 2.相关 3.按钮 4.信号与槽函数 5.常用栏 菜单栏 工具栏 状态栏 6.铆接部件 7.文本编辑 8…...

【数据分享】全国地级市1999—2020年工业企业数(Shp/Excel格式)

在之前的文章中&#xff0c;我们分享过基于2000-2022年《中国城市统计年鉴》整理的1999-2021年地级市的人口相关数据、各类用地面积数据、污染物排放和环境治理相关数据、房地产投资情况和商品房销售面积、社会消费品零售总额和年末金融机构存贷款余额&#xff08;可查看之前的…...

设计模式【行为型】-- 责任链模式

责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为型设计模式&#xff0c;它允许多个对象依次处理同一个请求&#xff0c;形成一条责任链。当客户端提交一个请求时&#xff0c;请求沿着责任链传递&#xff0c;直到有一个处理者能够处理该请求为止。…...

[Spring] 三级缓存解决循环依赖详解

什么是循环依赖 注册一个bean对象的过程&#xff1a; Spring扫描class得到BeanDefinition – 根据得到的BeanDefinition去生成bean – 现根据class推断构造方法 – 根据推断出来的构造方法&#xff0c;反射&#xff0c;得到一个对象 – 填充初始对象中的属性(依赖注入) – 如果…...

gerrit 从安装到出坑

一般公司在做代码审核的时候选择codereview gerrit来处理代码的入库的问题。 它是通过提交的时候产生Change-Id: If4e0107f3bd7c5df9e2dc72ee4beb187b07151b9 来决定是不是入库&#xff0c;一般如果不是通过这个管理&#xff0c;那么就是我们通常的操作 git add . git comm…...

Java工程师就业前景怎么样?能拿多少工资?

Java软件工程师是指运用Java这个开发工具去完成软件产品的软件程序设计、开发、测试、维护升级等工作的人员。Java程序员可以分为初级、中级、高级、资深等。不同级别的Java程序员&#xff0c;薪资也不一样。 Java除了一般的编程&#xff0c;还可以开发游戏、进行桌面设计、Ja…...

极速跳板机登陆服务器

目录 一&#xff1a;简单登陆跳板器二&#xff1a;一键申请相关的服务器权限三&#xff1a;简化登陆 一&#xff1a;简单登陆跳板器 登陆公司提供的网址&#xff0c; 下载自己的专属RSA密钥。在密钥文件处&#xff0c; 执行登陆指令&#xff1a; ssh -p 36000 -i id_rsa 用户跳…...

【算法与数据结构】226、LeetCode翻转二叉树

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;这道题的思路很简单&#xff0c;本质上就是遍历每一个节点&#xff0c;然后交换左右节点。我们可以用前…...

metaRTC6.0 new feature (一)

概要 metaRTC6.0社区版最新版是6.0.212&#xff0c;标准版最新版本是6.0.276&#xff0c;企业版基础版最新版本是6.0.362&#xff0c;在企业版和标准版新增了一些实用功能模块&#xff0c;文件数字证书模块将并入社区版。 New Feature rtsp协议支持 新增rtsp协议&#xff0…...

聊天机器人如何增加电子商务销售额

聊天机器人和自动化对企业和客户来说都是福音。自动对话和聊天机器人&#xff08;以下统称为“自动化”&#xff09;通过自动回答问题或分配会话信息来帮助用户浏览品牌网站或电商商店。即时答案对客户来说非常有用&#xff0c;使用自动化也可以让原本与客户聊天的客服员工专注…...

stm32 IIC通信

文章目录 IIC 通信一、硬件电路二、IIC时序基本单元三、IIC时序1.指定地址写2.当前地址读3.指定地址读 IIC 通信 IIC总线是一种通用数据总线&#xff0c;有两根通信线&#xff08;SCL(串行时钟总线),SDA&#xff08;串行数据总线&#xff09;&#xff09;。 特点&#xff1a;同…...

Elasticsearch监控工具Cerebro安装

Elasticsearch监控工具Cerebro安装 1、在windwos下的安装 1.1 下载安装包 https://github.com/lmenezes/cerebro/releases/download/v0.9.4/cerebro-0.9.4.zip 1.2 解压 1.3 修改配置文件 如果需要修改相关信息&#xff0c;编辑C:\zsxsoftware\cerebro-0.9.4\conf\applica…...

RTOS 低功耗设计原理及实现

RTOS 低功耗设计原理及实现 文章目录 RTOS 低功耗设计原理及实现&#x1f468;‍&#x1f3eb;前言&#x1f468;‍&#x1f52c;Tickless Idle Mode 的原理及实现&#x1f468;‍&#x1f680;Tickless Idle Mode 的软件设计原理&#x1f468;‍&#x1f4bb;Tickless Idle Mo…...

PaddleOCR C++编译出错解决方案

文章目录 前言一、环境准备1、主要环境2、源码下载3、C推理库下载 二、报错信息1.静态库调用错误2.ld returned 1 exit status 总结 前言 最近&#xff0c;想尝试下PaddleOCR的C推理&#xff0c;但是过程不如人所愿&#xff0c;除了很多问题&#xff0c;这里捡重点的说下吧&…...

89、简述RabbitMQ的架构设计

简述RabbitMQ的架构设计 BrokerQueueExchangeRoutingKeyBinding信道架构设计图Broker RabbitMQ的服务节点 Queue 队列,是RabbitMQ的内部对象,用于存储消息。RabbitMQ中消息只能存储在队列中。生产者投递消息到队列,消费者从队列中获取消息并消费。多个消费者可以订阅同一…...

63 | 图像处理

文章目录 Python图像处理什么是图像处理?Python图像处理库安装Pillow库加载和显示图像调整图像大小裁剪图像调整图像亮度、对比度和色彩平衡应用滤镜练习题Python图像处理 什么是图像处理? 图像处理是指使用计算机算法来改变图像的外观或特征。它可以用于许多不同的应用程序…...

Stable Diffusion - 扩展 Roop 换脸 (Face Swapping) 插件的配置与使用

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/131856141 官网&#xff1a;GitHub - roop&#xff0c;参考论文&#xff1a;RobustSwap: A Simple yet Robust Face Swapping Model against Attr…...

opencv实现替换证件照颜色

程序可以实现蓝色底片变为红色底片&#xff08;但有点小bug&#xff09; 修改自&#xff1a;opencv&#xff1a;HSV颜色模型_opencv hsv_君浪的博客-CSDN博客 相关文章&#xff1a;OpenCV Mat数据类型指针ptr的使用_cv::mat ptr_AoboSir的博客-CSDN博客 【OpenCV】HSV颜色识…...

Elasticsearch【全文检索、倒排索引、应用场景、对比Solr、数据结构】(一)-全面详解(学习总结---从入门到深化)

目录 Elasticsearch介绍_全文检索 Elasticsearch介绍_倒排索引 Elasticsearch介绍_Elasticsearch的出现 Elasticsearch介绍_Elasticsearch应用场景 Elasticsearch介绍_Elasticsearch对比Solr Elasticsearch介绍_Elasticsearch数据结构 Elasticsearch介绍_全文检索 Elasti…...

了解 3DS MAX 3D摄像机跟踪设置:第 2 部分

推荐&#xff1a; NSDT场景编辑器助你快速搭建可二次开发的3D应用场景 1. 项目设置 步骤 1 打开“后效”。 打开后效果 步骤 2 转到合成>新合成以创建新合成。 将“宽度”和“高度”值分别设置为 1280 和 720。将帧速率设置为 25&#xff0c;将持续时间设置为 12 秒。单…...

MySQL 判断 JSON 数组是否相等

文章目录 1.问题2.使用 JSON_CONTAINS 与 JSON_LENGTH参考文献 1.问题 JSON&#xff08;JavaScript Object Notation&#xff09;是流行的互联网应用服务之间的数据交换格式。 MySQL 从 5.7 版本开始支持 RFC 7159 定义的 JSON 规范&#xff0c;主要有 JSON 对象 和 JSON 数组…...

uni-app个人中心

一. 介绍uni-app&#xff1a; uni-app 是基于Vue.js框架开发的一个跨平台移动应用开发框架&#xff0c;可以同时支持多个平台&#xff08;如iOS、Android、Web等&#xff09;的应用开发。采用了统一的语法和组件规范&#xff0c;可以大大简化跨平台开发的工作&#xff0c;提高…...

只需3步,使用Stable Diffusion无限生产AI数字人视频

效果演示 先看效果&#xff0c;感兴趣的可以继续读下去。 没有找到可以上传视频的地方&#xff0c;大家打开这个网盘链接观看&#xff1a;https://www.aliyundrive.com/s/CRBm5NL3xAE 基本方法 搞一张照片&#xff0c;搞一段语音&#xff0c;合成照片和语音&#xff0c;同…...

Mysql执行计划字段解释

文章目录 一、前言二、如何查看执行计划三、执行计划各字段解释四、select_type4.1、SIMPLE&#xff08;简单查询&#xff09;4.1.1、简单的单表查询4.1.2、多表连接查询 4.2、PRIMARY&#xff08;主查询&#xff09;4.2.1、包含复杂子查询的外层查询4.2.2、UNION语句中的第一个…...

Linux -- 线程

文章目录 1. 线程概念1.1 概念1.2 理解&#xff08;Linux OS角度&#xff09;1.3 见一见 2. 线程优缺点3. 线程使用3.1 认识线程库3.2 使用3.2.1 线程创建3.2.2 线程等待3.2.3 线程退出3.2.4 线程取消3.2.5 获取线程id3.2.6 线程分离 3.3 理解线程库3.4 证明线程栈3.5 线程局部…...

Android:实时更新时间

心想着也就是更新精确到分钟&#xff0c;不用精确到秒&#xff0c;定时器就没有必要&#xff0c;系统是有广播Intent.ACTION_TIME_TICK可以直接用 动态注册广播 主方法里面调用一下 //要先设置一下当前时间&#xff0c;不然刷新时间会等到1分钟后再刷新 tv_HM.setText(getHM…...