数据结构——lesson6二叉树基础

前言

hellohello~这里是土土数据结构学习笔记🥳🥳
在这里插入图片描述

💥个人主页:大耳朵土土垚的博客
💥 所属专栏:数据结构学习笔记
💥对于数据结构顺序表链表有疑问的都可以在上面数据结构的专栏进行学习哦~感谢大家的观看与支持🌹🌹🌹
有问题可以写在评论区或者私信我哦~

前面我们已经学习过了数据结构中顺序表和链表(都放在数据结构专栏了),今天我们将继续学习数据结构中二叉树有关的知识🥳🥳

💥1.树概念及结构

🎉1.1树的概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。
把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
在这里插入图片描述
类似于倒立的树:
在这里插入图片描述

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

🥳1.2与树有关的概念

如图是树形结构:
在这里插入图片描述

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

  2. 叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点;

  3. 非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G…等节点为分支节点;

  4. 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点

  5. 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点;

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

  7. 树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6;

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

  9. 树的高度或深度:树中节点的最大层次; 如上图:树的高度为4;

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

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

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

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

以上节点的层次不同于数组下标从0开始,它是从1开始便于后续使用,不然不好区分一层节点和没有节点的情况,当然也可以从0开始,数组下标从0开始则是因为*(arr+i)便于计算。

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

在这里插入图片描述

树可以理解为包括两个:一是父节点(前驱节点),另一个是子树。
而子树同样又可以分为父节点和子树
直到找到叶子节点

💫1.3 树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
我们这里简单介绍一些方法:
(1)直接表示

这里我们需要知道树的度,然后直接定义

struct TreeNode
{
	int data;//保存数据
	struct TreeNode* child1;//保存孩子节点的指针
	struct TreeNode* child2;
	//...
}

如果树的度是7,我们则需要定义7个树的指针

(2)双亲表示法

存放双亲也就是父节点的指针或下标即可

struct TreeNode
{
int data;
struct TreeNode* parent;//或者存放下标int parenti;
}

(3)最常用的孩子兄弟表示法

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

在这里插入图片描述

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

在这里插入图片描述

💥2.二叉树概念及结构

🎉2.1概念

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

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

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

在这里插入图片描述
注意:对于任意的二叉树都是由以下几种情况复合而成的:
在这里插入图片描述

二叉树就是树分支要小于等于2即可

🥳2.2现实中的二叉树

在这里插入图片描述

💫2.3 特殊的二叉树

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

满二叉树每个节点都分两个支,直到叶子节点出现;
完全二叉树最后一层要有连续分支,且分支也小于等于2,其他层是满二叉树

2.4 二叉树的性质

1.每个节点最多有两个子节点,分别称为左子节点和右子节点。

2.二叉树的左子树和右子树也是二叉树。

3.则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.

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

5.若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1)(ps:log是以2为底,n+1为对数)

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

  1. 若i>0,i位置节点的双亲序号:(i-1)/2;
  2. i=0,i为根节点编号,无双亲节点

可以按照等比数列来理解,等比数列的公比为2,首项为1

💥3.结语

以上就是学习二叉树的基础知识啦,重点部分已经加粗或颜色标注了大概知道二叉树有关的概念,以及理解二叉树的原理与概念即可,后续将会持续学习二叉树有关的编程知识…完结撒花~🥳🥳🎉💖

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

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

相关文章

JuiceSSH结合Cpolar实现公网远程SSH访问内网Linux系统

文章目录 1. Linux安装cpolar2. 创建公网SSH连接地址3. JuiceSSH公网远程连接4. 固定连接SSH公网地址5. SSH固定地址连接测试 处于内网的虚拟机如何被外网访问呢?如何手机就能访问虚拟机呢? cpolarJuiceSSH 实现手机端远程连接Linux虚拟机(内网穿透,手机端连接Linux虚拟机) …

echarts 模拟时间轴播放效果

x,y轴为数值轴&#xff0c;通过设置bar的数据模拟时间播放。标签可通过formatter自定义为时间&#xff0c;播放/停止/速度可通过setInterval来控制(待完善) 代码可直接放echart官方示例执行 let data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,100]; option {color: [#3398DB],toolti…

代码随想录算法训练营第二天|977、有序数组的平方

977. 有序数组的平方 已解答 简单 相关标签 相关企业 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#xff1a;nums [-4,-1,0,3,10] 输出&#xff1a;[0,1,9,16,…

Linux Ubuntu系统安装MySQL并实现公网连接本地数据库【内网穿透】

文章目录 前言1 .安装Docker2. 使用Docker拉取MySQL镜像3. 创建并启动MySQL容器4. 本地连接测试4.1 安装MySQL图形化界面工具4.2 使用MySQL Workbench连接测试 5. 公网远程访问本地MySQL5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定TCP地址远程访问 前言 本文主…

基于Flask的宠物领养系统的设计与实现

基于Flask的宠物领养系统的设计与实现 涉及技术&#xff1a;python3.10flaskmysql8.0 系统分为普通用户和管理员两种角色&#xff0c;普通用户可以浏览搜索宠物&#xff0c;申请领养宠物&#xff1b;管理员可以分布宠物信息&#xff0c;管理系统等。 采用ORM模型创建数据&am…

chrome浏览器插件content.js和background.js还有popup都是什么,怎么通讯

popup 在用户点击扩展程序图标时&#xff08;下图中的下载图标&#xff09;&#xff0c;都可以设置弹出一个popup页面。而这个页面中自然是可以包含运行的js脚本的&#xff08;比如就叫popup.js&#xff09;。它会在每次点击插件图标——popup页面弹出时&#xff0c;重新载入。…

高并发服务器模型

高并发服务器模型 1.高并发服务器模型--select2.高并发服务器模型--poll3.epoll模型3.1 epoll原理3.2epoll反应堆 1.高并发服务器模型–select 我们知道实现服务器的高并发&#xff0c;可以用多线程或多进程去实现。但还可以利用多路IO技术:select来实现&#xff0c;它可以同时…

html唐诗鉴赏

<!DOCTYPE html> <html> <head><title>文字网页</title> </head> <body><h2 align"center">唐诗鉴赏</h2><hr width"100%" size"1" color"#00ffee"><p align"…

“2024第九届国际发酵培养基应用与发展技术论坛”圆满落幕

3月5日&#xff0c;“2024第九届国际发酵培养基应用与发展技术论坛”在济南圆满落幕。论坛吸引了来自发酵行业400多名代表现场参会&#xff0c;1600多名代表线上参会。本次论坛由中国生物发酵产业协会主办&#xff0c;安琪酵母股份有限公司承办。中国生物发酵产业协会理事长于学…

抽奖小程序怎么一键生成_揭秘这款火爆的抽奖小程序

一键生成&#xff0c;梦想触手可及&#xff01;揭秘这款火爆的抽奖小程序 在快节奏的现代生活中&#xff0c;每个人都渴望找到一份属于自己的幸运与惊喜。而今天&#xff0c;我要为大家介绍的这款抽奖小程序&#xff0c;正是实现这一愿望的神器&#xff01;它不仅操作简单&…

Linux服务器安装nvm

1、 首先查看服务器有没有安装git git --version 2、如果没有安装&#xff1a;在Linux上是有yum安装Git&#xff0c;非常简单&#xff0c;只需要一行命令 yum -y install git 3、git安装完成后&#xff0c;使用以下其中一个命安装NVM # 能访问github的话&#xff0c;使用这…

逆变器专题(17)-下垂控制(1)

相应仿真原件请移步资源下载 通常情况下&#xff0c;离网型逆变器采用的控制方法为电压电流双闭环控制&#xff0c;而常规的电压电流双闭环控制会存在电压跌落&#xff0c;频率失稳等情况&#xff0c;通俗的将就是没有电压和频率的支撑 。 下垂控制是现如今较为常用的李网逆变…

Python接口自动化之cookie、session应用!

以下介绍cookie、session原理及在接口自动化中的应用。 HTTP 协议是一种无状态协议&#xff0c;即每次服务端接收到客户端的请求时&#xff0c;都是一个全新的请求&#xff0c;服务器并不知道客户端的历史请求记录&#xff1b;Session 和 Cookie 的主要目的就是为了弥补 HTTP 的…

运维工单系统哪家好?

数字化转型数字化时代已然到来&#xff0c;企业运维工作的重要性日益突出。为了满足各类企业的运维需求&#xff0c;市场上涌现了诸多运维工单系统厂家&#xff0c;包括卓豪ServiceDesk Plus、Zendesk、Zenduty、Jira Service Desk等。 而选择合适的运维工单系统&#xff0c;对…

《剑指 Offer》专项突破版 - 面试题 74 : 合并区间(C++ 实现)

题目链接&#xff1a;LCR 074. 合并区间 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 输入一个区间的集合&#xff0c;请将重叠的区间合并。每个区间用两个数字表示&#xff0c;它们分别表示区间的起始位置和结束位置。例如&#xff0c;输入区间集合 [[1, 3], …

【异常处理】BadSqlGrammarException低级SQL语法异常

报错 org.springframework.jdbc.BadSqlGrammarException: ### Error querying database. Cause: java.sql.SQLSyntaxErrorException: You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use …

每日一练 | 华为认证真题练习Day194

1、下面是路由器Huawei的部分输出配置&#xff0c;关于该部分配置描迷正确的是: [huawei] bgp 100 [huawei-bgp]peer 12.12.12.2 ip-prefix P1 export [huawei]ip-prefix P1 index 5 deny 10.0.0.0 0 greater-equal 8 less-equal 32 [huawei]ip-prefix P1 index 5 deny 172…

做副业千万不要在抖音开个人店,个人店血泪史,千万别碰!

大家好&#xff0c;我是电商花花。 抖音小店个人店已经开放了很长时间了&#xff0c;个人店以不用营业执照&#xff0c;不用保证金&#xff0c;凭借身份证就可以在抖音上开抖音小店&#xff0c;就可以做电商&#xff0c;做老板。 目前抖音小店的流量可以说是非常大&#xff0…

【MetaGPT】多智能体协作——你画我猜(文字版)

多智能体协作 本篇将学习 MetaGPT中的 Environment 、 Team 组件。 1. Muti Agent 概念概述 多智能体系统 (Multi-Agent System, MAS) 是由一群具有一定自主性、协同性和学习能力的智能体组成的系统。智能体在环境中相互协作&#xff0c;以达到某种目标或完成特定任务。 2. 多…

哪里下载Mac上最全面的系统清理工具,CleanMyMac X4.15中文版永久版资源啊

哪里下载Mac上最全面的系统清理工具&#xff0c;CleanMyMac X4.15中文版永久版资源啊&#xff0c;CleanMyMac X4.15中文版是一款全面的Mac系统优化工具。它能够扫描、检测并清理不需要的文件和应用程序&#xff0c;优化内存使用和磁盘空间&#xff0c;提高Mac的性能表现。此外&…