NzN的数据结构--二叉树part1

        你叉叉,让你学数据结构你不学;你叉叉,让你看二叉树你不看。 今天我们来一起学习二叉树部分,先赞后看是好习惯

 

一、树的概念及结构

1. 树的概念

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

 

        我们可以把一棵树拆解成根和子树。除根节点外,其余结点被分成M(M≥0)个互不相交的T1T2 、……、Tm ,其中每一个集合又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继节点。子树也可以继续被拆解为根和子树的子树。因此,树是递归定义的。

注意:

  • 树形结构中,子树是不相交的,否则就不是树形结构。
  • 除了根结点外,每个结点有且仅有一个父结点。
  • 一棵N个结点的树有N-1条边。

       上面两种都不是树形结构!!!

2. 树的相关概念

节点的度:一个节点含有的子树的个数称为该节点的度。 如上图,A的度为6。

叶节点(终端节点)度为0的节点称为叶节点。 如上图:B、C、H、I...等节点为叶节点。

非终端节点(分支节点)度不为0的节点。 如上图:D、E、F、G...等节点为分支节点。

双亲节点(父节点)若一个节点含有子节点,则这个节点称为其子节点的父节点。 如上图,A是B的父节点。

孩子节点(子节点)一个节点含有的子树的根节点称为该节点的子节点。如上图,B是A的孩子节点。

兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点。

树的度:树中最大的节点的度称为树的度; 如上图:节点的度最大为6,则树的度为6。

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推。

树的高度(深度)树中节点的最大层次,一般从1开始数,空树的高度为0。

堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点。

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

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙。

森林:由m(m>0)棵互不相交的树的集合称为森林。

3. 树的表示

        树结构相对线性表就比较复杂了,既然保存值域,也要保存结点和结点之间的关系。树有很多种表示方式:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。

//方法一(容易造成空间浪费)
#define N 6//定义树的度为6
struct TreeNode
{
	int val;
	struct TreeNode* subA[N];//开辟结构体指针数组存储孩子
};
//方法二:用顺序表存储孩子的内容
struct TreeNode
{
	int val;
	//顺序表
	struct TreeNode** subA;//这里应该是二级指针
	//开辟的是指针数组,每个数组的元素是结构体指针
	int size;
	int capacity;
};

        我们这里推荐最常用的左孩子右兄弟表示法

//左孩子右兄弟表示法
struct TreeNode
{
	int val;
	struct TreeNode* leftChild;//指向左边的第一个孩子
	struct TreeNode* nextBrother;//指向自己右边的兄弟,最右边的nextBrother指向NULL
};

        如上图,A的leftChild指向B,nextBrother指向空;B的leftChild指向D,nextBrother指向C;C的leftChild指向G,nextBrother指向空等等,以此类推便可以便将整个树串了起来。 

4. 树在实际中的运用(表示文件系统的目录树结构)

二、二叉树概念及结构

1. 概念

        一棵二叉树是结点的一个有限集合,该集合由一个根节点加上两棵别称为左子树和右子树的二叉树组成或者也可能为空。 

        从上图可以看出:二叉树不存在度大于2的结点;二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

注意:二叉树不是只有两棵子树,而是最多有两棵子树。

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

        后面我们会学二叉搜索树,他的要求是左子树数据全小于根,右子树数据均大于根。

       假设二叉搜索树高度为h,则查找次数最多为h次。二叉搜索树也有不足,有些时候会退化成下面这种情况。就需要我们继续学习AVL数和红黑树。

2. 特殊的二叉树 

        满二叉树:一个二叉树,如果每一层的结点数都达到最大值,则这个二叉树就是满二叉树。即如果一个二叉树的层数为k,且结点总数是2^k-1 ,则它就是满二叉树。

        完全二叉树:对于深度为k,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称为完全二叉树。 满二叉树是一种特殊的完全二叉树。

3. 二叉树的性质

        若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^i-1个结点

        若规定根节点的层数为1,则深度为h的二叉树的最大结点数2^h-1

        对任何一棵二叉树,度为0其叶结点个数比度为2的结点个数多1个

        若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log_{2}(n+1)

        对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:

  • 若i>0,i 位置节点的双亲序号:\frac{i-1}{2};i=0,i为根节点编号,无双亲节点
  • 若2i+1<n,左孩子序号:2i+1,2i+1≥n,否则无左孩子
  • 若2i+2<n,右孩子序号: 2i+2,2i+2≥n,否则无右孩子

3. 二叉树的存储结构 

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。

3.1 顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,否则会有空间浪费。现实使用中,只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

        父子存储的下标规律:

  • leftchild=parent*2+1,rightchild=parent*2+2
  • parent=(child-1)/2

        这样可以直接通过数组下标访问,也可以通过数组还原树。数组存储只适合完全二叉树和满二叉树,否则会造成大量空间浪费。

3.2 链式存储

        链式存储是指用链表来表示二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点分成三个域:数据域和左右指针域。左右指针分别给出该结点左孩子和右孩子所在的链结点的存储地址。

        链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面学到高阶数据结构如红黑树等会用到三叉链。

         那本章我们介绍了二叉树入门的一些内容,下一章我们就要正式开始学习二叉树的实现方法,给个三连,敬请关注~~~

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

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

相关文章

阿里云服务器可以干什么?阿里云服务器主要用途是干嘛的?

阿里云服务器可以干嘛&#xff1f;能干啥你还不知道么&#xff01;简单来讲可用来搭建网站、个人博客、企业官网、论坛、电子商务、AI、LLM大语言模型、测试环境等&#xff0c;阿里云百科aliyunbaike.com整理阿里云服务器的用途&#xff1a; 阿里云服务器活动 aliyunbaike.com…

SpringCloud Alibaba Sentinel 规则持久化

一、前言 接下来是开展一系列的 SpringCloud 的学习之旅&#xff0c;从传统的模块之间调用&#xff0c;一步步的升级为 SpringCloud 模块之间的调用&#xff0c;此篇文章为第十七篇&#xff0c;即使用 Sentinel 实现规则持久化。 二、概述 从前面我们做的实验可知&#xff0c;…

4/7 QT_day1

#include "mainwindow.h"MainWindow::MainWindow(QWidget *parent): QMainWindow(parent) {//窗口设置this->setWindowTitle("小黑子(little black son)");this->setWindowIcon(QIcon("D:\\qq文件\\Pitrue\\pictrue\\black.jpg"));this-&g…

【数据结构与算法】:快速排序和冒泡排序

一&#xff0c;快速排序 快速排序是一种比较复杂的排序算法&#xff0c;它总共有4种实现方式&#xff0c;分别是挖坑法&#xff0c;左右"指针"法&#xff0c;前后"指针"法&#xff0c;以及非递归的快速排序&#xff0c;并且这些算法中也会涉及多种优化措施…

Tokenize Anything via Prompting

SAM的延续&#xff0c;把SAM输出的token序列用来进行分类&#xff0c;分割和一个自然语言的decoder处理&#xff0c;但其实现在多模态的图像的tokenizer也几乎都是用VIT来实现的。一开始认为这篇文章可能是关于tokenize的&#xff0c;tokenize还是很重要的&#xff0c;后来看完…

若依框架学习——分页查询列表

条件查询【多条件】列表展示【分页】SaCheckPermissionTableName TableId NotBlank Page分页 响应数据封装类

JMeter+Ant+Jenkins构建接口报告(无人驾驶版)

展示结果&#xff1a; uc浏览器打开测试报告&#xff0c;绿色显示脚本结果 搭建操作步骤如下 1.jemter写好脚本 2.下载并配置ant环境变量&#xff1a;加上activation.jar、commons-lang3-3.8.1.jar、mail.jar 这3个包 mail.jar需要引用到jmeter 3.下载安装Jenkins 并进行构建…

CKA 基础操作教程(六)

Kubernetes Deployments 理论学习 在 Kubernetes 中&#xff0c;Deployments 是一种资源对象&#xff0c;用于定义和管理容器化应用程序的部署过程&#xff0c; 容器化应用的声明式定义&#xff1a;使用 Deployments &#xff0c;可以声明性地定义应用程序的部署配置&#x…

Vue使用高德地图

1.在高德平台注册账号 2.我的 > 管理管理中添加Key 3.安装依赖 npm i amap/amap-jsapi-loader --save 或 yarn add amap/amap-jsapi-loader --save 4.导入 AMapLoade import AMapLoader from amap/amap-jsapi-loader; 5.直接上代码&#xff0c;做好了注释&#xff08;初始化…

初识ES(ES的基本概念、倒排索引、索引和文档的CRUD)

1、ES是什么&#xff1f; 一个开源的分布式搜索引擎&#xff0c;可以用来实现搜索、日志统计、分析、系统监控等功能。ES的底层是基于Lucene实现的。 Lucene是一个Java语言的搜索引擎类库。 什么是elastic stack&#xff08;ELK&#xff09;&#xff1f; elasticsearch。存储、…

实验室用进口高纯聚四氟乙烯材质PFA方盘抗酸碱耐高温PFA托盘

PFA方盘又称托盘&#xff1a;耐高温、耐腐蚀。 进口透明可溶性聚四氟乙烯方盘。可应用于成膜实验&#xff0c;样品液体脱漏等。能放在电热板上直接加热使用&#xff0c;也可以用于烘箱烘干&#xff0c;实验室腐蚀性样品的转移和搬运&#xff0c;防止腐蚀性液体洒落。 产品特性…

Python常用算法--解决数据结构问题【附源码】

一、约瑟夫环问题 解释:约瑟夫环(Josephus Problem)是一个著名的数学问题,它描述了一个关于围坐一圈的人进行游戏的场景。游戏规则是从一个人开始,顺序报数,每报到特定数目的人将会被排除出圈子,然后从被排除的下一人开始继续报数,游戏继续进行直到最后剩下一个人。 …

ETL工具-nifi干货系列 第九讲 处理器EvaluateJsonPath,根据JsonPath提取字段

1、其实这一节课本来按照计划一起学习RouteOnAttribute处理器&#xff08;相当于java中的ifelse&#xff0c;switch case 控制语句&#xff09;&#xff0c;但是在学习的过程中遇到了一些问题。RouteOnAttribute 需要依赖处理器EvaluateJsonPath&#xff0c;所以本节课我们一起…

如何确定螺栓的载荷和扭矩——SunTorque智能扭矩系统

智能扭矩系统-智能拧紧系统-扭矩自动控制系统-SunTorque 螺栓作为一种常见的紧固件&#xff0c;广泛应用于各种机械和设备中。正确确定螺栓的载荷及其扭矩对于确保设备的安全运行和延长其使用寿命至关重要。本文将探讨如何确定螺栓的载荷及其扭矩&#xff0c;帮助读者更好地理…

将excel,csv中合并块中某条记录的值应用到整个块(使用多行的值,来填充新列数据)。

背景描述 在excel中使用其它列的值&#xff0c;根据某种计算规则来填充另一列&#xff08;或新列&#xff09;很容易实现。但是如果需要根据合并块中的多行来填充列时&#xff0c;就不容易实现&#xff0c;由于对excel不是太常用&#xff0c;因此这里使用的命令行工具实现的。…

K8s学习三(Pod与探针)

深入学习Pod Pod配置文件 写一个自己的配置文件,nginx-po.yaml apiVersion: v1 #api文档版本 kind: Pod #资源类型对象&#xff0c;也可以配置为像Development&#xff0c;StatefulSet这一类的对象 metadata: # Pod相关的元数据&#xff0c;用于描述Pod的数据name: nginx-po…

4月7号总结

java学习 一.正则表达式 定义&#xff1a;正则表达式是一种用于描述字符串模式的表达式&#xff0c;通常被用于文本搜索、匹配和替换。它是一种强大的工具&#xff0c;可以在文本处理和文本分析中进行复杂的匹配和操作。 通过字符串引用里面的方法matches&#xff0c;然后执行…

【Web】纯萌新的CISCN刷题记录(1)

目录 [CISCN 2019华东南]Web11 [CISCN 2019华北Day2]Web1 [CISCN 2019初赛]Love Math [CISCN 2022 初赛]ezpop [CISCN 2019华东南]Double Secret [CISCN 2023 华北]ez_date [CISCN 2019华北Day1]Web1 [CISCN 2019华东南]Web4 [CISCN 2019华北Day1]Web2 [CISCN 2023 …

【Django开发】前后端分离美多商城项目第6篇:用户部分,1. 业务说明【附代码文档】

美多商城项目4.0文档完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;美多商城&#xff0c;项目准备1.B2B--企业对企业,2.C2C--个人对个人,3.B2C--企业对个人,4.C2B--个人对企业,5.O2O--线上到线下,6.F2C--工厂到个人。项目准备&#xff0c;配置1. 修改set…

微服务学习2

目录 一.网关路由 1.1.认识网关 1.2网关快速入门 1.2.1.创建项目 1.2.2.引入依赖 1.2.3.启动类 1.2.4.配置路由 1.3.路由过滤 二.网关登录校验 2.1网关请求处理流程 2.2网关过滤器 2.2.2网关过滤器 2.3自定义GlobalFilter 2.4.登录校验 2.4.1.JWT工具 2.4.2.登…