二叉树的详解

二叉树

【本节目标】

  1. 掌握树的基本概念
  2. 掌握二叉树概念及特性
  3. 掌握二叉树的基本操作
  4. 完成二叉树相关的面试题练习

  1. 树型结构(了解)
    1. 概念

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

有一个特殊的结点,称为根结点,根结点没有前驱结点

除根结点外,其余结点被分成M(M > 0)个互不相交的集合T1T2......Tm其中每一个集合 Ti (1 <= i

<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继树是递归定义的。

注意:树形结构中,子树之间不能有交集,否则就不是树形结构

    1. 概念(重要)

结点的度:一个结点含有子树的个数称为该结点的度; 如上图:A的度为6 树的度:一棵树中,所有结点度的最大值称为树的度; 如上图:树的度为6

叶子结点或终端结点:度为0的结点称为叶结点; 如上图:BCHI...等节点为叶结点

双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:AB的父结点

孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点;  如上图:BA的孩子结点根结点:一棵树中,没有双亲结点的结点;如上图:A

结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推树的高度或深度:树中结点的最大层次; 如上图:树的高度为4

树的以下概念只需了解,在看书时只要知道是什么意思即可:

非终端结点或分支结点:度不为0的结点; 如上图:DEFG...等节点为分支结点兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:BC是兄弟结点

堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:HI互为兄弟结点

结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先

子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙 森林:由mm>=0)棵互不相交的树组成的集合称为森林

    1. 树的表示形式(了解)

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,   孩子表示法孩子双亲表示法孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法

    1. 树的应用

文件系统管理(目录和文件)

  1. 二叉树(重点)
    1. 概念

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

      1. 或者为空
      2. 或者是由一个根节点加上两棵别称为左子树右子树的二叉树组成。

从上图可以看出:

  1. 二叉树不存在度大于2的结点
  2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

注意:对于任意的二叉树都是由以下几种情况复合而成的:

大自然的奇观:

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

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

i>0双亲序号:(i-1)/2i=0i为根结点编号,无双亲结点 2i+1<n,左孩子序号:2i+1,否则无左孩子

2i+2<n,右孩子序号:2i+2,否则无右孩子

    1. 二叉树的存储

二叉树的存储结构分为:顺序存储类似于链表的链式存储顺序存储在下节介绍。

二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式,具体如下:

孩子双亲表示法后序在平衡树位置介绍,本文采用孩子表示法来构建二叉树。

    1. 二叉树的基本操作
      1. 前置说明

在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结   构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等   二叉树结构了解的差不多时,我们反过头再来研究二叉树真正的创建方式。

注意:上述代码并不是创建二叉树的方式,真正创建二叉树方式后序详解重点讲解。 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是:

        1. 空树
        2. 非空:根节点,根节点的左子树、根节点的右子树组成的。

从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。

      1. 二叉树的遍历
        1. 前中后序遍历

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

在遍历二叉树时,如果没有进行某种约定,每个人都按照自己的方式遍历,得出的结果就比较混乱,如果按  照某种规则进行约定,则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点,L代表根节点的  左子树,R代表根节点的右子树,则根据遍历根节点的先后次序有以下遍历方式:

NLR:前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。LNR:中序遍历(Inorder                   Traversal)——根的左子树--->根节点--->根的右子树。LRN:后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。

下面主要分析前序递归遍历,中序与后序图解类似,同学们可自己动手绘制。

前序遍历结果:1 2 3 4 5 6

中序遍历结果:3 2 1 5 4 6

后序遍历结果:3 1 5 6 4 1

        1. 层序遍历

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

练习】请同学们根据以上二叉树的三种遍历方式,给出以下二叉树的:

选择题

      1. 二叉树的基本操作

    1. 二叉树相关oj
      1. 检查两颗树是否相同。OJ链接
      2. 另一颗树的子树。OJ链接
      3. 二叉树最大深度 OJ链接
      4. 判断一颗二叉树是否是平衡二叉树。OJ链接
      5. 对称二叉树。OJ链接
      6. 二叉树的构建及遍历。OJ链接
      7. 二叉树的分层遍历 。OJ链接
      8. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ链接
      9. 二叉搜索树转换成排序双向链表。OJ链接
      10. 根据一棵树的前序遍历与中序遍历构造二叉树。 OJ链接
      11. 根据一棵树的中序遍历与后序遍历构造二叉树([课堂不讲解,课后完成作业])。OJ链接
      12. 二叉树创建字符串。OJ链接
      13. 二叉树前序非递归遍历实现 。OJ链接
      14. 二叉树中序非递归遍历实现。OJ链接
      15. 二叉树后序非递归遍历实现。OJ链接

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

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

相关文章

Redis核心技术与实战【学习笔记】 - 24.Redis 数据分片方案选择:Codis 和 Redis Cluster

简述 Redis 的切片集群使用多个实例保存数据&#xff0c;能很好的应对大数据量的场景。在《4.Redis 切片集群》中&#xff0c;介绍了 Redis 官方提供的切片集群方法 Redis Cluster。本章&#xff0c;再来学习下&#xff0c;在 Redis Cluster 方案正式发布前&#xff0c;业界广…

CodeMeter强化了ETM WinCC 开放架构平台的许可与安全保护

在面对日益复杂的网络安全威胁时&#xff0c;ETM professional control采取了前瞻性的措施&#xff0c;选择了业界领先的威步CodeMeter技术&#xff0c;以保护其标志性的WinCC开放架构平台。这一选择不仅体现了ETM对安全的高度重视&#xff0c;也标志着其在保障关键基础设施运营…

Jmeter 01 -概述线程组

1、Jmeter:概述 1.1 是什么&#xff1f; Jmeter是Apache公司使用Java 开发的一款测试工具 1.2 为什么&#xff1f; 高效、功能强大 模拟一些高并发或多次循环等特殊场景 1.3 怎么用&#xff1f; 下载安装 1、下载jmeter&#xff0c;解压缩2、安装Java环境&#xff08;jmet…

基于OpenCV灰度图像转GCode的螺旋扫描实现

基于OpenCV灰度图像转GCode的螺旋扫描实现 引言激光雕刻简介OpenCV简介实现步骤 1.导入必要的库2. 读取灰度图像3. 图像预处理4. 生成GCode5. 保存生成的GCode6. 灰度图像螺旋扫描代码示例 总结 系列文章 ⭐深入理解G0和G1指令&#xff1a;C中的实现与激光雕刻应用⭐基于二值…

5-3、S曲线生成器【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;本节介绍步进电机S曲线生成器的计算以及使用 一.计算原理 根据上一节内容&#xff0c;已经计算了一条任意S曲线的函数。在步进电机S曲线加减速的控制中&#xff0c;需要的S曲线如图1所示&#xff0c;横…

React 实现表单组件

表单是html的基础元素&#xff0c;接下来我会用React实现一个表单组件。支持包括输入状态管理&#xff0c;表单验证&#xff0c;错误信息展示&#xff0c;表单提交&#xff0c;动态表单元素等功能。 数据状态 表单元素的输入状态管理&#xff0c;可以基于react state 实现。 …

09_树莓派_树莓派外设板_GPIO_按键的中断与消抖

目录 1.树莓派外设集成板总体介绍 2.第一部分 按键矩阵 GPIO_按键与中断 3.实现效果 1.树莓派外设集成板总体介绍 1&#xff09;前言&#xff1a;这是一块为了验证树莓派【兼容树莓派多个型号】的40pins的外设接口的外接板&#xff0c;告别复杂的面包板外设搭建。【欢迎各位…

【Iceberg学习四】Evolution和Maintenance在Iceberg的实现

Evolution Iceberg 支持就底表演化。您可以像 SQL 一样演化表结构——即使是嵌套结构——或者当数据量变化时改变分区布局。Iceberg 不需要像重写表数据或迁移到新表这样耗费资源的操作。 例如&#xff0c;Hive 表的分区布局无法更改&#xff0c;因此从每日分区布局变更到每小…

Node.js+Express+Mysql服务添加环境变量

1、使用dotenv插件 1&#xff09;安装插件&#xff1a;npm install dotenv-cli --save-dev 2&#xff09;在项目根目录下添加对应的 .env 配置文件&#xff1b; // .env配置文件内容 MODEdevelopment, BASE_URLhttp://127.0.0.1:80813) 在启动命令中设置对应的加载文件&#…

RabbitMQ-1.介绍与安装

介绍与安装 1.RabbitMQ1.0.技术选型1.1.安装1.2.收发消息1.2.1.交换机1.2.2.队列1.2.3.绑定关系1.2.4.发送消息 1.2.数据隔离1.2.1.用户管理1.2.3.virtual host 1.RabbitMQ 1.0.技术选型 消息Broker&#xff0c;目前常见的实现方案就是消息队列&#xff08;MessageQueue&…

新零售的升维体验,摸索华为云GaussDB如何实现数据赋能

新零售商业模式 商业模式通常是由客户价值、企业资源和能力、盈利方式三个方面构成。其最主要的用途是为实现客户价值最大化。 商业模式通过把能使企业运行的内外各要素整合起来&#xff0c;从而形成一个完整的、高效率的、具有独特核心竞争力的运行系统&#xff0c;并通过最…

springboot与Elasticsearch版本兼容对比

首先 大家在下载 Elasticsearch 时 最好先弄清楚版本 因为 如果 Spring Boot 版本 不兼容 Elasticsearch 那就是到头一场空了 Elasticsearch 版本 6.x 可以兼容 Spring Boot 2.x Elasticsearch 版本 7.x 可以兼容 Spring Boot 2.x 3.x 4x Elasticsearch 版本 7.x 以及 8.x 可以…

Golang-Map有序输出——使用orderedmap库实现

前言 工作中遇到一个问题&#xff1a;需要导出一个MySQL表格&#xff0c;表格内容由sql查询得来。但现在发现&#xff0c;所导出的表格中&#xff0c;各列的顺序不确定。多次导出&#xff0c; 每一次的序列顺序也是不定的。 因此确定是后端&#xff0c;Map使用相关导致的问题。…

分布式文件存储系统minio

参考Linux搭建免费开源对象存储 wget https://dl.minio.io/server/minio/release/linux-amd64/minio yum install -y wget yum install -y wget wget https://dl.minio.io/server/minio/release/linux-amd64/minio chmod x minio sudo mv minio /usr/local/bin/ minio --vers…

黑马头条 Kafka

我是南城余&#xff01;阿里云开发者平台专家博士证书获得者&#xff01; 欢迎关注我的博客&#xff01;一同成长&#xff01; 一名从事运维开发的worker&#xff0c;记录分享学习。 专注于AI&#xff0c;运维开发&#xff0c;windows Linux 系统领域的分享&#xff01; 知…

玩家笔记:幻兽帕鲁搭建服务器开服教程

玩转幻兽帕鲁服务器&#xff0c;阿里云推出新手0基础一键部署幻兽帕鲁服务器教程&#xff0c;傻瓜式一键部署&#xff0c;3分钟即可成功创建一台Palworld专属服务器&#xff0c;成本仅需26元&#xff0c;阿里云服务器网aliyunfuwuqi.com分享2024年新版基于阿里云搭建幻兽帕鲁服…

1.0 Zookeeper 分布式配置服务教程

ZooKeeper 是 Apache 软件基金会的一个软件项目&#xff0c;它为大型分布式计算提供开源的分布式配置服务、同步服务和命名注册。 ZooKeeper 的架构通过冗余服务实现高可用性。 Zookeeper 的设计目标是将那些复杂且容易出错的分布式一致性服务封装起来&#xff0c;构成一个高…

实践:微服务版本升级步骤以及maven仓库相关概念

进行微服务开发的时候&#xff0c;上层服务依赖于下层的服务的api&#xff0c;比如适配属于上层服务&#xff0c;用户属于下层服务。 例子: 上层服务 <!--订单管理微服务api依赖--> <dependency><groupId>com.jn.server</groupId><artifactId>…

docker部署docker运维工具

简介 主要功能:管理容器,管理镜像,管理容器网络 安装 拉取镜像 docker pull joinsunsoft/docker.ui:1.0.1 启动容器 docker run -d --name docker.ui --restart always -v /var/run/docker.sock:/var/run/docker.sock -p 10039:8999 joinsunsoft/docker.ui:1.0.1 使用 打…

【ArcGIS微课1000例】0101:删除冗余节点或折点

文章目录 一、实验描述二、实验数据三、实验过程1. 手动删除2. 简化线工具四、注意事项一、实验描述 矢量数据获取通常来源于手动或者ArcScan自动采集,其基本存储方式就是记录每个要素的点坐标,如点要素就是一个坐标、线要素由多个点要素连接形成。当某段线要素被过多的节点…