devbox
一键难忘520
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

最新数据结构——二叉树（上）_文件系统是二叉树还是树(2)

作者：一键难忘520 | 2024-07-26 23:33:05

赞

踩

最新数据结构——二叉树（上）_文件系统是二叉树还是树(2)

注：树形结构中，子树中不能有交集，否则就不是树形结构

2.2树的相关概念

●节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

●叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点

●非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

●****双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

●孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

●兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

●树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

●节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

●树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

●堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为堂兄弟节点

●节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

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

2.3树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的**孩子兄弟表示法，**又称左孩子右兄弟表示法。

那么什么是孩子兄弟表示法呢，就是一个结点中除了所要存储的数据的变量以外，还需要两个指针变量分别指向它的兄弟结点和第一个孩子结点。

具体代码如下：

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

2.4 树在实际中的应用（表示文件系统的目录树结构）

其实树在实际中的应用无处不在，尤体现在文件系统中。在生活中，我们往往要点开一个文件夹、新建一个文件夹，又或者将文件夹全部展开。那么体现在代码上是什么样子的呢单次点击文件夹就相当于对链表的遍历，而新建一个文件夹就相当于链表的尾插，对文件夹的全部展开就是一种深度递归了。

不过在数据结构中，我们更常用的树的其中一种类型——二叉树，下面就来详细地向小伙伴们讲讲二叉树。

三、二叉树概念及结构

3.1概念

一颗二叉树是结点的一个有限集合，该集合共有两种情况：

①为空，即该结点下无结点

②由一个根结点加上两颗分别称为左子树和右子树的二叉树组成

即对于二叉树而言，一个结点下只能有0、1或2个结点，也有人戏称二叉树是经过计划生育的树。

从上图我们也可以看出：

①二叉树不存在度大于2的结点

②二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由一下几种情况符合而成的：

3.2现实中的二叉树

当一名普通人看到这样一颗树，可能会想：好标准的一棵树

当一个程序猿看到这样一棵树，可能会想：好像数据结构中的二叉树，并且还是一颗满二叉树

甚至有人开玩笑说，有些公司甚至会不惜重金将这样一颗满二叉树买回来，种植在公司的门口，当员工每天经过树旁都要拜一拜，并且低声祈福：拜拜二叉树，bug都消失不见。足以看出二叉树在数据结构的地位之重了，所以小伙伴们一定要认真看完这篇文章呀！

3.3特殊的二叉树

在了解完二叉树的基础概念之后，在其中还存在着两颗特殊的树：

①满二叉树：一个二叉树且每一个层的结点数都达到最大值，也就是说，如果一个二叉树的层数为K，且结点总数是2＾（k一1） ，则它就是满二叉树。

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

注：完全二叉树在去掉最后一层后就是一颗满二叉树

3.4二叉树的性质

以下的的知识点小伙伴们一定要收藏好呀，做题的时候经常会用到滴！

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

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

③对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0＝n2 ＋1,也就是度为0的永远比度为2的多一个

④若规定根节点的层数为1，具有n个结点的满二叉树的深度h=log2（n+1） (ps： 是log以2 为底，n+1为对数)

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

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

  2. 若2i+1=n否则无左孩子

  3. 若2i+2=n否则无右孩子

3.5二叉树的存储结构

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

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

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

具体代码如下：

typedef int BTDataType;

// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft;     // 指向当前节点左孩子
 struct BinTreeNode* _pRight;    // 指向当前节点右孩子
 BTDataType _data;               // 当前节点值域
}

// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent;   // 指向当前节点的双亲
 struct BinTreeNode* _pLeft;     // 指向当前节点左孩子
 struct BinTreeNode* _pRight;    // 指向当前节点右孩子
 BTDataType _data;               // 当前节点值域
}；

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

四、二叉树的顺序结构及实现

4.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

4.2堆的概念及结构

如果有一个关键码的集合K = {k0 ,k1 ,k2,…,kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： Ki<=K2*i+1 且 Ki<=K2*i+2 （ Ki>=K2*i+1 且 Ki>=K2*i+2） i = 0，1， 2…，则称为小堆(或大堆)。通俗的来说，在大堆中，双亲结点总是大于等于子结点，而在小堆中，双亲结点重视小于等于子结点。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

●堆中某个节点的值总是不大于或不小于其父节点的值；

●堆总是一棵完全二叉树。

4.3堆的实现

4.3.1数据类型的定义与结构体

与数据结构的其他内容一样，在进行堆的功能实现之前，我们需要堆所存储的数据类型进行定义以及在调用这个堆的时候所使用的的结构体的定义。两者皆可根据读者的实际需求进行个性化定义，本文只是采取其中一种进行编写。

本文对堆的数据类型采取整形的形式，而对于结构体的定义，我们在其中定义了三个变量，分别是存储数据的数组a、数组元素的个数size、数组的最大存储元素个数capacity ，之所以要定义size和capacity两边变量是为了后续对数组内存储的元素个数与数组存储容量进行比较，从而进行扩容的操作。

具体代码如下：

//堆的初始化声明
void HeapInit(HP* php);	

//堆的初始化实现
void HeapInit (HP* php)
{
	assert(php);
	HeapDataType* a = (HeapDataType)malloc(sizeof(HeapDataType) * 4);
	if (a == NULL)
	{
		perror("malloc failed");
		return;
	}
	php->a = a;
	php->capacity = 4;
	php->size = 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
4.3.2堆的销毁

对于堆的销毁是十分简单的，只需将数组的空间释放，并将指针置空，变量置零即可

具体代码如下：

//堆的销毁声明
void HeapDestroy(HP* php);

//堆的销毁实现
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
4.3.3堆的判空

由于前面我们在对结构体的变量定义中引入了**“size”变量来记录堆中所存储的元素个数**，因此我们只需要对“size”的值进行判断就可以知道此时堆是否为空

具体代码如下：

//堆的判空声明
bool HeapEmpty(HP* php);	

//堆的判空实现
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
4.3.4堆的数据个数

本功能的实现与堆的判空实现类似，通过返回“size”的值便能得到堆所存储的数据个数

具体代码如下：

//返回堆的数据个数声明
int HeapSize(HP* php);	

//返回堆的数据个数实现
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
4.3.5堆的堆顶数据

由于我们采取的是数组的形式来实现堆，因此堆顶的数据便对应数组中下标为0的元素，因此只需返回数组内下标为0的元素即可

具体代码如下：

//堆的堆顶数据函数声明
HeapDataType HeapTop(HP* php);						

//堆的堆顶数据函数实现
HeapDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
4.3.6堆的插入

相比于前面几个功能的实现，堆的插入和删除就略显复杂了。那么堆的插入该如何实现呢？

对于堆的插入共分两步走：第一步就是先将数据插入到数组数据的末端，即尾插数据；不过在插入数据后，这个数据可能刚刚好满足我们大/小堆的要求，但也有可能破坏原有的堆结构，因此就有了第二步：调整堆内的数据，使其符合大/小堆的要求，但是如何调整数据呢，采取的是“**向上调整”**算法。

具体思路【以大堆为例】和代码如下：

//堆的向上调整声明
void AdjustUp(HeapDataType* a, int child);	

//堆的向上调整实现
void AdjustUp(HeapDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//大堆调整
	while (parent >= 0 && parent != child)	//或者以child>0作为判断条件,,parent >= 0 && parent!=child
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
	
	//小堆调整
	while (parent >= 0 && parent != child)	//或者以child>0作为判断条件,,parent >= 0 && parent!=child
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

//堆的插入声明
void HeapPop(HP* php);	

//堆的插入实现
void HeapPush(HP* php, HeapDataType x)
{
	assert(php);
	//判断堆是否满
	if (php->size == php->capacity)
	{
		HeapDataType* tmp = (HeapDataType*)realloc(php->a,sizeof(HeapDataType)* php->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc failed");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	//插入数据
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
4.3.7堆的删除

堆的删除一般是删除是堆顶的元素，有的小伙伴可能就想这还不简单吗，直接删除数组内下标为0的元素，再对堆进行调整不就好了。

从逻辑上说没啥问题，但是我们堆的物理结构并不是如此，由于采取数组的形式，是一种线性结构，一旦将栈顶元素移除，就会将堆的结构破坏，就可能出现以下这种情况，当栈顶元素没删除之前，咱们两个结点还是兄弟结点，但是删除之后，可能我们两就是就是父子结点，也就是我把你当兄弟，你却想当我爸爸，而这种调整在正常情况下是不会出现的，这可不滑稽极了。

于是就出现了以下这种思路：

①先将栈顶元素与栈尾元素互换位置

②“”删除”栈尾元素

③从栈顶开始进行“向下调整”算法

具体图片和代码如下：

//堆的向下调整声明
AdjustDown(HeapDataType* a, int n, int parent);

//堆的向下调整实现
void AdjustDown(HeapDataType* a, int n, int parent)
{
	int child = 2 * parent + 1;
	//大堆
	while (child < n )
	{
		//选出左右孩子中大的那一个
		if (child+1<n && a[child+1]>a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}

	//小堆
	while (child < n)
	{
		//选出左右孩子中小的那一个
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

//堆的删除声明
void HeapPop(HP* php);		

//堆的删除实现
void HeapPop(HP* php)
{
	assert(php);
	//判断堆是否为空
	assert(!HeapEmpty(&php));
	//交换数据
	Swap(&php->a[0], &php->a[php->size - 1]);
	//删除数据
	php->size--;
	//调整数据
	AdjustDown(php->a, php->size, 0);

						

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65

五、完整代码

//heap.h


![img](https://img-blog.csdnimg.cn/img_convert/a28846c2226537846da20782a48a92d4.png)
![img](https://img-blog.csdnimg.cn/img_convert/33fb93112bba33910b6ff8e029ad461a.png)

**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**

**[需要这份系统化资料的朋友，可以戳这里获取](https://bbs.csdn.net/topics/618545628)**


**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**

nt + 1;
		}
		else
		{
			break;
		}
	}
}

//堆的删除声明
void HeapPop(HP* php);		

//堆的删除实现
void HeapPop(HP* php)
{
	assert(php);
	//判断堆是否为空
	assert(!HeapEmpty(&php));
	//交换数据
	Swap(&php->a[0], &php->a[php->size - 1]);
	//删除数据
	php->size--;
	//调整数据
	AdjustDown(php->a, php->size, 0);

						

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

五、完整代码

//heap.h


[外链图片转存中...(img-7N7UR4O6-1714829664936)]
[外链图片转存中...(img-tLyf91xF-1714829664937)]

**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**

**[需要这份系统化资料的朋友，可以戳这里获取](https://bbs.csdn.net/topics/618545628)**


**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/887680
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号