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

了解树和学习二叉树

 

1.树

1.1 概念

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

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

一颗N结点的树有N-1条边

 

结点的度 :一个结点含有子树的个数称为该结点的度; 如上图: A 的度为 6
树的度 :一棵树中,所有结点度的最大值称为树的度; 如上图:树的度为 6
叶子结点或终端结点 :度为 0 的结点称为叶结点; 如上图: B C H I... 等节点为叶结点
双亲结点或父结点 :若一个结点含有子结点,则这个结点称为其子结点的父结点;如上图: A B 的父结点
孩子结点或子结点 :一个结点含有的子树的根结点称为该结点的子结点;如上图: B A 的孩子结点
根结点 :一棵树中,没有双亲结点的结点;如上图: A
结点的层次 :从根开始定义起,根为第 1 层,根的子结点为第 2 层,以此类推

 2. 二叉树(重点)

2.1 概念

     一棵二叉树是结点的一个有限集合,该集合:
        1. 或者为空
        2. 或者是由 一个根节 点加上两棵别称为 左子树 右子树 的二叉树组成

 

 二叉树的每个节点的度 <= 2

2.2  两种特殊的二叉树  

满二叉树:每层的结点数都达到最大值,就是满二叉树。(每个节点的度=2

完全二叉树:有n 个结点的二叉树,从上到下,从左到右,编号从0n-1的结点一 一对应时称之为完 全二叉树。

      满二叉树是一种特殊的完全二叉树。

2.3 二叉树的性质 

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

2.4 二叉树的遍历 

前序遍历和后序遍历是无法构成一棵树的!

无法确定左、右子树

相关文章:

了解树和学习二叉树

1.树 1.1 概念 树是一种 非线性 的数据结构&#xff0c;它是由 n &#xff08; n>0 &#xff09;个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看 起来像一棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下的 。 注意&#xff1a;树形结构中…...

Spring Boot学习随笔- 拦截器实现和配置(HandlerInterceptor、addInterceptors)、jar包部署和war包部署

学习视频&#xff1a;【编程不良人】2021年SpringBoot最新最全教程 第十三章、拦截器 拦截器 &#xff1a;Interceptor 拦截 中断 类似于javaweb中的Filter&#xff0c;不过没有Filter那么强大 作用 Spring MVC的拦截器是一种用于在请求处理过程中进行预处理和后处理的机制。拦…...

Pipelined-ADC设计二——结构指标及非理想因素(Part2)

接上文&#xff0c;本章将两个比较重要的非理想因素&#xff0c;因此各项指标制定。后续会对常见的非理想因素给出常见的解决方法&#xff0c;以及设计所采用的方法。 2.2.7. 比较器失调 在流水线 ADC 中&#xff0c;比较器的主要误差来源就是比较器失调&#xff0c;称为失调误…...

Ubuntu 常用命令之 clear 命令用法介绍

&#x1f4d1;Linux/Ubuntu 常用命令归类整理 clear命令在Ubuntu系统下用于清除终端屏幕的内容。这个命令没有任何参数&#xff0c;它的主要作用就是清理终端屏幕上的所有信息&#xff0c;使得屏幕看起来像是新打开的一样。 使用clear命令非常简单&#xff0c;只需要在终端中…...

【JAVA面试题】什么是对象锁?什么是类锁?

&#x1f34e; 个人博客 &#xff1a;个 人 主 页 &#x1f3c6;个人专栏&#xff1a;多线程JAVA ⛳️ 功 不 唐 捐 &#xff0c;玉 汝 于 成 目录 前言 回答 对象锁&#xff08;Object Lock&#xff09;&#xff1a; 类锁&#xff08;Class Lock&#xff09;&#xff1…...

飞天使-k8s知识点5-kubernetes基础名词扫盲

文章目录 deploymentspodNodeserviceskubectl 实现应用伸缩kubectl 实现滚动更新kubernetes架构 deployments 中文文档 http://docs.kubernetes.org.cn/251.htmldeployment是用来创建和更新应用的&#xff0c;master 会负责将创建好的应用实例调度到集群中的各个节点 应用实例…...

【视觉实践】使用Mediapipe进行目标检测:杯子检测和椅子检测实践

目录 1 Mediapipe 2 Solutions 3 安装mediapipe 4 实践 1 Mediapipe Mediapipe是google的一个开源项目,可以提供开源的、跨平台的常用机器学习(machine learning,ML)方案。MediaPipe是一个用于构建机器学习管道</...

C++之深拷贝进阶

目录 拷贝构造函数的深拷贝进阶版本 赋值运算符重载的深拷贝进阶 总结 上期我们学习了C中深拷贝的传统版本&#xff0c;今天我们将学习更为高效的版本。 拷贝构造函数的深拷贝进阶版本 传统版本代码如下&#xff1a; string(string& s):_str(new char[strlen(s._str)…...

导行电磁波从纵向场分量求其他方向分量的矩阵表示

导行电磁波从纵向场分量求解其他方向分量的矩阵表示 导行电磁波传播的特点 电磁波在均匀、线性、各向同性的空间中沿着 z z z轴传播&#xff0c;可用分离变量法将时间轴、 z z z轴与 x , y x,y x,y轴分离&#xff0c;电磁波的形式可表示为&#xff1a; E ⃗ E ⃗ ( x , y )…...

融资项目——swagger2的注解

1. ApiModel与ApiModelProperty(在实体类中使用) 如上图&#xff0c;ApiModel加在实体类上方&#xff0c;用于整体描述实体类。ApiModelProperty(value"xxx",example"xxx")放于每个属性上方&#xff0c;用于对属性进行描述。swagger2网页上的效果如下图&am…...

【性能优化】MySql数据库查询优化方案

阅读本文你的收获 了解系统运行效率提升的整体解决思路和方向学会MySQl中进行数据库查询优化的步骤学会看慢查询、执行计划、进行性能分析、调优 一、问题&#xff1a;如果你的系统运行很慢&#xff0c;你有什么解决方案&#xff1f; ​关于这个问题&#xff0c;我们通常首先…...

Chrome浏览器http自动跳https问题

现象&#xff1a; Chrome浏览器访问http页面时有时会自动跳转https&#xff0c;导致一些问题。比如&#xff1a; 开发阶段访问dev环境网址跳https&#xff0c;后端还是http&#xff0c;导致接口跨域。 复现&#xff1a; 先访问http网址&#xff0c;再改成https访问&#xf…...

【C++进阶02】多态

一、多态的概念及定义 1.1 多态的概念 多态简单来说就是多种形态 同一个行为&#xff0c;不同对象去完成时 会产生出不同的状态 多态分为静态多态和动态多态 静态多态指的是编译时 在程序编译期间确定了程序的行为 比如&#xff1a;函数重载 动态多态指的是运行时 在程序运行…...

PHP开发日志——循环和条件语句嵌套不同,效率不同(循环内加入条件语句,条件语句判断后加入循环,array_map函数中加入条件语句)

十多年前开发框架时&#xff0c;为了效率不断试过各种代码写法&#xff0c;今天又遇到了&#xff0c;想想php8时代会不会有所变化&#xff0c;结果其实也还是和当年一样&#xff0c;但当年没写博客&#xff0c;但现在可以把数据记录下来了。 PHP_loop_ireflies_dark_forest 项目…...

【Seata源码学习 】 扫描@GlobalTransaction注解 篇一

1. SeataAutoConfiguration 自动配置类的加载 基于SpringBoot的starter机制&#xff0c;在应用上下文启动时&#xff0c;会加载SeataAutoConfiguration自动配置类 # Auto Configure org.springframework.boot.autoconfigure.EnableAutoConfigurationio.seata.spring.boot.aut…...

DBA-MySql面试问题及答案-上

文章目录 1.什么是数据库?2.如何查看某个操作的语法?3.MySql的存储引擎有哪些?4.常用的2种存储引擎&#xff1f;6.可以针对表设置引擎吗&#xff1f;如何设置&#xff1f;6.选择合适的存储引擎&#xff1f;7.选择合适的数据类型8.char & varchar9.Mysql字符集10.如何选择…...

网络爬虫之Ajax动态数据采集

动态数据采集 规则 有时候我们在用 requests 抓取页面的时候&#xff0c;得到的结果可能和在浏览器中看到的不一样&#xff0c;在浏览器中可以看到正常显示的页面教据&#xff0c;但是使用 requests 得到的结果并没有&#xff0c;这是因为requests 获取的都是原始的 HTML 文档…...

c语言的初始学习(练习)

##初学c语言---MOOC浙江大学翁恺先生学习c语言 那么我们先看看这个题目吧&#xff0c;这是初始语法的应用。 记住&#xff0c;我们的程序是按步骤执行的&#xff0c;并不是在不同的两行同时进行。 程序设计&#xff1a;1.了解题目的需要&#xff0c;几个变量需要用到&#x…...

研究论文 2022-Oncoimmunology:AI+癌RNA-seq数据 识别细胞景观

Wang, Xin, et al. "Deep learning using bulk RNA-seq data expands cell landscape identification in tumor microenvironment." Oncoimmunology 11.1 (2022): 2043662. https://www.tandfonline.com/doi/full/10.1080/2162402X.2022.2043662 被引次数&#xff1…...

ChatGPT4与ArcGIS Pro3助力AI 地理空间分析和可视化及助力科研论文写作

在地学领域&#xff0c;ArcGIS几乎成为了每位科研工作者作图、数据分析的必备工具&#xff0c;而ArcGIS Pro3除了良好地继承了ArcMap强大的数据管理、制图、空间分析等能力&#xff0c;还具有二三维融合、大数据、矢量切片制作及发布、任务工作流、时空立方体等特色功能&#x…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...