数据结构之《二叉树》(上)

server/2024/12/21 6:46:30/

在之前的数据结构学习中,我们了解了顺序表、链表等线性表,接下来在本篇中将要学习一种非线性的数据结构——树,我们将来了解树的相关概念和性质,在树当中将重点学习二叉树的结构和特性。学习完相关概念后将试着实现二叉树,解决二叉树相关的问题。接下来就开始本篇的学习吧!!!


1.树 

 1.树的概念与结构

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

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

 

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

例如以下就为非树形结构:

 因此树形结构需要有以下特性
• 子树是不相交的(如果存在相交就是图)
• 除了根结点外,每个结点有且仅有一个父结点
• 一棵N个结点的树有N-1条边

1.2 树相关术语 

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

子结点/孩子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结

结点的度:⼀个结点有几个孩子,他的度就是多少;比如A的度为6,F的度为2,K的度为0

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

叶子结点/终端结点:度为 0 的结点称为叶结点; 如上图: B、C、H、I... 等结点为叶结点

分支结点/非终端结点:度不为 0 的结点; 如上图: D、E、F、G... 等结点为分支结点

兄弟结点:具有相同父结点的结点互称为兄弟结点(亲兄弟); 如上图: B、C 是兄弟结点 

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

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

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

路径:一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列;比如A到Q的路径为:A-E-J-Q;H到Q的路径H-D-A-E-J-Q

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

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

1.3 树的表示 

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩⼦表示法、孩子双亲表示法以及孩子兄弟表示法等。在此我们就来了解其中最常用的孩子兄弟表示法

struct TreeNode
{
// 左边开始的第⼀个孩⼦结点struct Node* child;
// 指向其右边的下⼀个兄弟结点struct Node* brother; 
// 结点中的数据域int data;
};

例如以上的树用孩子兄弟表示法来表示后就可以画出以下的图示

 

1.4 树形结构实际运用场景

在我们的电脑当中许多的场景都用到树,例如在文件系统中,文件系统是计算机存储和管理文件的⼀种方式,它利用树形结构来组织和管理⽂件和⽂件夹。在文件系统中,树结构被⼴泛应用,它通过⽗结点和⼦结点之间的关系来表示不同层级的文件和文件夹之间的关联。

2. 二叉树

 

2.1二叉树的概念与结构

学习了树的相关概念后,接下来来了解在树当中用得最多的结构——二叉树二叉树是结点的一个有限集合,该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空。

在二叉树中有以下的特征:
1.在二叉树当中不存在度大于2的节点
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

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

 

 2.2特殊的二叉树

2.2.1满二叉树

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

在此计算满二叉树的的总节点数公式是由等比数列求和公式Sn=\frac{a1(1-q^{n})}{1-q}得到的,在满二叉树中公比就为2,因此Sn=2^{n}-1

2.2.2 完全二叉树

完全二叉树是效率很高数据结构完全二叉树是由满二叉树而引出来的。对于深度为 K 的,有 n 个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。
注意:满二叉树是一种特殊的完全二叉树

完全二叉树会有以下的性质
💡 二叉树性质
根据满二叉树的特点可知:
(1)若规定根结点的层数为 1 ,则⼀棵非空二叉树的第i层上最多有 2^{i-1} 个结点
(2)若规定根结点的层数为 1 ,则深度为 h 的二叉树的最大结点数是2^{h}-1
(3)若规定根结点的层数为 1 ,具有 n 个结点的满二叉树的深度 h=\log_{2}n+1 ( log以2为底, n+1 为对数)

因此一个二叉树要是完全二叉树就要除了第h层外,其他层都要为最大节点数,且在第h层内的节点必须按照从左向右的方式排列

以下的二叉树就不是完全二叉树

 

2.3 二叉树存储结构 

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

2.3.1顺序结构

顺序结构存储就是使用数组来存储,⼀般使用数组只适合表示完全⼆叉树,因为不是完全二叉树会有空间的浪费,完全二叉树更适合使用顺序结构存储。

例如以下的二叉树使用数组来存储后就为以下形式

而在使用数组来存储非完全二叉树时就会有空间的浪费,例如以下的二叉树的顺序存储

 

这时你可能会想为什么在使用数组存储二叉树的结点数据时直接将每个数据依次存放到数组当中,这样不就不会有空间的浪费的问题吗?

就像以下形式在数组内存储上面的二叉树 

但这样在数组中存储就会存在问题,就是比如当只知道一个节点的数据在数组中存储的下标时当我们要找这个结点的父结点或者是孩子结点就会无法找到对应的数组下标,因此这种方法是行不通的

在二叉树中接下来要学习的堆(一种二叉树)就是使用顺序结构的数组来存储的
注意:这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。

2.3.2链式结构 

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链。

 

 

 

 

以上就是二叉树(上)的全部内容了,接下来在二叉树(中)将继续学习二叉树的知识,在下一篇中我们将重点学习堆的相关知识,未完待续…… 


http://www.ppmy.cn/server/95751.html

相关文章

使用Python实现深度学习模型:智能航空与无人机技术

介绍 在现代航空与无人机技术中,深度学习可以帮助进行飞行路径规划、目标检测、避障等。本文将介绍如何使用Python和深度学习库TensorFlow与Keras来构建一个简单的无人机目标检测模型。 环境准备 首先,我们需要安装必要的Python库: pip install tensorflow pandas numpy…

基本类型和引用类型的参数传递

Java 只有按值传递,不论是基本类型还是引用类型。 基本类型是值传递很好理解,引用类型有些同学可能有点理解不了,特别是初学者。 JVM 内存有划分为栈和堆,局部变量和方法参数是在栈上分配的,引用类型占4个字节,基本类型看具体类型,例如 long 和 double 占8个字节。而对象所占的…

GD 32 产品配置参数存储方案

前言&#xff1a; ......... 产品配置参数存储方案 在实际项目开发过程中&#xff0c;常常会涉及到一些参数的掉电存储&#xff0c;这些参数占用存储空间不大&#xff0c;但需要具备。 可读可写的能力&#xff0c;而且这些参数往往扮演着重要的角色&#xff0c;比如Modbus地址…

python爬虫预备知识三-序列化和反序列化

序列化和反序列化 序列化是为了将内存中的数据保存在磁盘上或者用于传输&#xff0c;实现程序状态的保存和共享。反序列化反之。 序列化后的变量再被反序列化回来之后&#xff0c;两者之间已经没有任何关系。 序列化后的文件是在不同程序或者说不同语言之间传递数据的关键方…

2024第五届华数杯数学建模竞赛C题思路+代码

目录 原题背景背景分析 问题一原题思路Step1:数据读取与处理Step2:计算最高评分&#xff08;Best Score, BS&#xff09;Step3:统计各城市的最高评分&#xff08;BS&#xff09;景点数量 程序读取数据数据预处理 问题二原题思路Step1: 定义评价指标Step2: 收集数据Step3: 标准化…

python pip怎么安装包

按WinR键打开运行窗口&#xff0c;输入“cmd”&#xff0c;再按回车键&#xff0c;打开命令行窗口。 找到pip安装路径。 Python2/Python3安装路径是相同的&#xff0c;都在x:\Python xx\Scripts路径下。 拖动pip主应用程序到命令行窗口。 输入“install 模块/包名”&#xff…

Postman 接口测试详解

Postman 接口测试详解 Postman 接口测试详解1. Postman 基础知识1.1 什么是 Postman&#xff1f;1.2 Postman 的主要功能 2. 安装与设置2.1 安装 Postman2.2 创建 Postman 账户 3. Postman 的基本操作3.1 创建和发送请求3.2 解析响应数据3.3 使用环境和变量 4. 进阶功能4.1 编写…

Python学习笔记51:暂停篇

随便写点 最近因为公司项目的原因&#xff0c;学习进度变慢很多&#xff0c;但是也勉强支撑着把小游戏的项目写了个大概&#xff0c;其实后续很多的功能基本都是慢慢添加就可以&#xff0c;掌握了函数的调用&#xff0c;磕磕碰碰终究还是能把功能写好的&#xff0c;可能就是代…