数据结构——二叉树（上）

03-11 1060阅读

 数据结构——二叉树（上）

🌇个人主页：_麦麦_

📚今日名言：原来喜欢一个人的时候，无论做什么事情，哪怕只是发呆都会觉得很开心。——林苏

数据结构——二叉树（上）

目录

一、前言

二、树概念及结构

2 .1树的概念及结构

 2.2树的相关概念

2.3树的表示

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

三、二叉树概念及结构

3.1概念

3.2现实中的二叉树 

3.3特殊的二叉树

3.4二叉树的性质

 3.5二叉树的存储结构

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

4.1二叉树的顺序结构

4.2堆的概念及结构

4.3堆的实现

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

 4.3.2堆的销毁

 4.3.3堆的判空

 4.3.4堆的数据个数

 4.3.5堆的堆顶数据

 4.3.6堆的插入

 4.3.7堆的删除

 五、完整代码

 六、结语

一、前言

        许久未见，今日为小伙伴们带来关于数据结构中二叉树的讲解，希望小伙伴们能够从中有所收获，就是对作者的最大鼓励！！！

二、树概念及结构

2 .1树的概念及结构

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

●有一个特殊的结点，称为根结点，根结点没有前驱结点

●除根结点外，其余结点被分成M（M>0）个互不相交的集合T1、T2……Tm，其中每一个Ti（1a = a; php->capacity = 4; php->size = 0; }

 4.3.2堆的销毁

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

        具体代码如下：

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

 4.3.3堆的判空

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

        具体代码如下：

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

 4.3.4堆的数据个数

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

        具体代码如下：

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

 4.3.5堆的堆顶数据

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

        具体代码如下：

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

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] 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);
}

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  a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
	//小堆
	while (child a[0], &php->a[php->size - 1]);
	//删除数据
	php->size--;
	//调整数据
	AdjustDown(php->a, php->size, 0);

 五、完整代码

//heap.h
#pragma once
#include 
#include 
#include 
#include 
#include 
//数据类型定义
typedef int HeapDataType;
//结构体定义
typedef struct Heap
{
	HeapDataType* a;
	int size;
	int capacity;
}HP;
	
void HeapInit(HP* php);								//堆的初始化
void HeapDestroy(HP* php);							//堆的销毁
void HeapPush(HP* php, HeapDataType x);				//堆的插入
void HeapPop(HP* php);								//堆的删除
int HeapSize(HP* php);								//返回堆的元素个数
int HeapSort(int*a,int n);							//堆排序
bool HeapEmpty(HP* php);							//判断堆是否为空
HeapDataType HeapTop(HP* php);						//返回堆顶元素
void AdjustUp(HeapDataType* a, int child);			    //堆的向上调整
void AdjustDown(HeapDataType* a, int n, int parent);	//堆的向下调整
//heap.c
#include "heap.h"
//堆的初始化
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;
}
//堆的销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
//交换数据
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//堆的向上调整
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] 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);
}
//
void AdjustDown(HeapDataType* a, int n, int parent)
{
	int child = 2 * parent + 1;
	//大堆
	while (child  a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
	//小堆
	while (child size == 0;
}
//堆的删除
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);
}
//返回堆顶元素
HeapDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}
//返回堆的数据个数
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
//堆排序[升序--大堆排序]
int HeapSort(int* a, int n)
{
	//向上调整法建堆
	for (int i = 0; i = 0; i--)
	//{
	//	void AdjustDown(a, n, i);	//堆的向下调整
	//}
	//对堆进行升序排序
	for(int i = 0; i  

六、结语
 
 
 
        到此为止，关于二叉树的学习就告一段落了，在后面文章中我们将会继续讲解堆的应用及其TOP-K问题等等。
 
 
       关注我 _麦麦_分享更多干货：_麦麦_的博客_CSDN博客-领域博主
      大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！
 
 
数据结构——二叉树（上）       
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]