首页 > 其他分享 >数据结构:二叉树 （Heap堆篇） 手把手带你入门数据结构~ （简单易懂超详细~）

数据结构:二叉树 （Heap堆篇） 手把手带你入门数据结构~ （简单易懂超详细~）

时间：2024-09-24 23:20:07浏览次数：3  
标签：arr php int HP 结点 二叉树 Heap child 数据结构

文章目录

前言

在这里插入图片描述

在学习完栈和队列过后，我们一起来学习数据结构中的二叉树——堆~

一、树的概念

1. 树的概念与结构

树是⼀种⾮线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
在这里插入图片描述
数据结构中的树
在这里插入图片描述

2. 树的特性

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

树形结构中，⼦树之间不能有交集，否则就不是树形结构

⾮树形结构：
在这里插入图片描述

• ⼦树是不相交的，如果存在相交就是图了
• 除了根结点外，每个结点有且仅有⼀个⽗结点
• ⼀棵N个结点的树有N-1条边

3. 树的相关术语

  1. 父结点/双亲结点：

    • 定义：一个结点如果拥有一个或多个子结点，那么这个结点就被称为其子结点的父结点（或双亲结点）。父结点负责连接并支撑其下的子结点，是子结点向上级的直接连接者。

  2. 子结点：

    • 定义：一个结点的直接下一级的连接点称为其子结点。子结点是从该结点（父结点）出发形成的子树的根结点。在树结构中，一个结点可以有多个子结点。

  3. 结点的度：

    • 定义：结点的度是指该结点所拥有的子结点的数量。度用来描述结点的“扩展”程度，度越大，表明该结点直接拥有的子结点越多。

  4. 树的度：

    • 定义：树的度是树中所有结点的度中的最大值。换句话说，树中度最大的那个结点的度，代表了整棵树的度，反映了树中最复杂结点的分支情况。

  5. 叶子结点/终端结点：

    • 定义：度为 0 的结点称为叶子结点或终端结点。这类结点没有子结点，是树结构的“末端”结点，意味着它们不再延展分支。

  6. 分支结点/非终端结点：

    • 定义：度不为 0 的结点称为分支结点或非终端结点。这些结点至少拥有一个子结点，因此它们可以继续产生新的分支，处于树的中间层次。

  7. 兄弟结点：

    • 定义：具有相同父结点的多个结点互称为兄弟结点。兄弟结点之间共享同一个父结点，且位于同一层级的不同分支上。

  8. 结点的层次：

    • 定义：从树的根结点开始，根结点被定义为第 1 层，根的直接子结点为第 2 层，以此类推，每一层表示一个从根向下的层次。

  9. 树的高度/深度：

    • 定义：树的高度或深度是树中结点的最大层次数，也即从根结点到叶子结点所经过的最长路径的层次。树的高度反映了其纵向的最大扩展程度。

  10. 结点的祖先：

    • 定义：结点的祖先指的是从树的根结点到该结点路径上所经过的所有父结点。祖先结点是当前结点向上的所有直接或间接父结点。

  11. 路径：

    • 定义：路径是在树中，从一个结点沿着父结点与子结点之间的连接到达另一个结点的所有经过的结点序列。路径用于描述从起始结点到目标结点的连接过程。

  12. 子孙：

    • 定义：子孙指的是以某个结点为根结点的子树中的所有结点。所有这些结点与该根结点有直接或间接的父子关系，因此称为该结点的子孙。

  13. 森林：

    • 定义：森林是由若干棵（m > 0）互不相交的树构成的集合。在一个森林中，每棵树都是独立的结构，没有任何交叉或共享结点。

4. 树的表示方法

孩⼦兄弟表⽰法：

树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表⽰⽅式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法.
在这里插入图片描述

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

5. 树形结构实际场景

⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。

在这里插入图片描述

二、二叉树

1. 二叉树的概念

在树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。

在这里插入图片描述
在这里插入图片描述

2. 二叉树的结构

在这里插入图片描述

从上图可以看出⼆叉树具备以下特点：

  1. ⼆叉树不存在度⼤于 2 的结点
  2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树
    注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的。

3. 满二叉树

满⼆叉树:

⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为 K ，且结点总数是 2^k − 1 ，则它就是满⼆叉树。

在这里插入图片描述

3. 完全二叉树

1. 完全二叉树的概念

完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的，有 n 个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
在这里插入图片描述

2. 完全二叉树的性质

根据满⼆叉树的特点可知：

1）若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2^(i−1) 个结点

2）若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数 是 2^h − 1

3）若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 h = log2 (n + 1) ( log以2为底， n+1 为对数)

3. 完全二叉树的结构

⼆叉树⼀般可以使⽤两种结构存储，⼀种顺序结构，⼀种链式结构。

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

在这里插入图片描述

现实中我们通常把堆（⼀种⼆叉树）使⽤顺序结构的数组来存储，需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。

⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 。链式结构⼜分为⼆叉链和三叉链，当前我们学习中⼀般都是⼆叉链。
在这里插入图片描述

三、堆

1. 堆的概念

堆是一种特殊的完全二叉树，满足以下两个特点：

  1. 堆的结构性质：堆必须是完全二叉树，即除最后一层外，其他层的节点必须是满的，并且最后一层的节点从左到右依次排列。

  2. 堆的堆序性质：

    • 最大堆（大顶堆）：在最大堆中，每个父节点的值都大于或等于其子节点的值。因此，堆顶元素（根节点）是整个堆中的最大值。
    • 最小堆（小顶堆）：在最小堆中，每个父节点的值都小于或等于其子节点的值。因此，堆顶元素（根节点）是整个堆中的最小值。

堆常用于实现优先队列，因为它可以高效地插入数据和取出最大（或最小）值，时间复杂度为 O(log n)。
在这里插入图片描述
完全二叉树是一种特殊的二叉树，具有以下几个关键性质：

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

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

2.若 2i+1<n，左孩子序号:2i+1，2i+1>=n 否则无左孩子

3.若 2i+2<n ，右孩子序号:2i+2,2i+2>=n 否则无右孩子

2. 堆的实现

1. 堆的结构

前面说到，堆底层是用数组做到的，他和顺序表有一样的结构。

//堆的结构定义
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}HP;

2. 堆的初始化

//堆的初始化
void HPInit(HP* php);

将堆中所有元素至为初始值，NULL/0

//堆的初始化
void HPInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

3. 堆的销毁

//堆的销毁
void HPDestroy(HP* php);

像顺序表一样销毁数据

//堆的销毁
void HPDestroy(HP* php)
{
	if (php->arr)
	{
		free(php->arr);
	}
	php->arr = NULL;
	php->capacity = php->size = 0;
}

4. 堆的插入

//往堆中插入元素
void HPPush(HP* php, HPDataType x);

先看一张图~
以小根堆为例，这是我们事先拥有的小根堆。
在这里插入图片描述
假设我们要插入的数据是 6
可以直接插在尾部吗?
在这里插入图片描述
如果直接插在尾部就不再是小根堆了，因此插完过后，我们要将 6 这个元素向上调整。

我们通过parent = (child - 1) / 2，来记录parent 的位置，如果child比较小，就向上与parent交换位置。
在这里插入图片描述

//交换堆中数据
void Swap(int* x, int* y)
{
	int tem = *x;
	*x = *y;
	*y = tem;
}



//堆中数据向上调整
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

向上调整过后就可以完成我们的插入了

//往堆中插入元素
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tem = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
		if (tem == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}

		php->arr = tem;
		php->capacity = newcapacity;
	}

	php->arr[php->size] = x;
	AdjustUp(php->arr, php->size);
	php->size++;
}

5. 堆的删除

//删除堆中数据，删的是堆顶的数据
void HPPop(HP* php);

删除元素首先要判断堆是否为空，如果为空则不能删除元素。

//判断堆中数据是否为空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

我们说的删除堆中元素，指的是堆顶的元素。
如果直接删除堆顶的话，原来的小根堆就不再是小根堆了，而且堆顶的数据很难删除。

在这里插入图片描述

对于数组来说，删处第一个数据，要遍历数组将所有数据前移，但删除最后一个数据要简单很多。因此我们先将要删除的数据和最后一个数据交换。

直接让size-- 后将堆顶元素向下调整。
在这里插入图片描述

//删除堆中数据，删的是堆顶的数据
void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	Adjustdown(php->arr, 0, php->size);
}

6. 获取堆顶元素

//获取堆顶数据
HPDataType HPTop(HP* php);

//获取堆顶数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));

	return php->arr[0];

}

总结

到这里相信大家对堆有一个深入的了解了，最后的总结堆实现的源码奉上需要的小伙伴们自取哦~

//Head.c
#include"Heap.h"

//堆的初始化
void HPInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

//堆的销毁
void HPDestroy(HP* php)
{
	if (php->arr)
	{
		free(php->arr);
	}
	php->arr = NULL;
	php->capacity = php->size = 0;
}


//交换堆中数据
void Swap(int* x, int* y)
{
	int tem = *x;
	*x = *y;
	*y = tem;
}



//堆中数据向上调整
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

//往堆中插入元素
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tem = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
		if (tem == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}

		php->arr = tem;
		php->capacity = newcapacity;
	}

	php->arr[php->size] = x;
	AdjustUp(php->arr, php->size);
	php->size++;
}


//判断堆中数据是否为空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}


//向下调整
void Adjustdown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//删除堆中数据，删的是堆顶的数据
void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	Adjustdown(php->arr, 0, php->size);
}

//获取堆顶数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));

	return php->arr[0];

}

//Head.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//堆的结构定义
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}HP;


//堆的初始化
void HPInit(HP* php);

//堆的销毁
void HPDestroy(HP* php);

//往堆中插入元素
void HPPush(HP* php, HPDataType x);

//删除堆中数据
void HPPop(HP* php);

//获取堆顶元素
HPDataType HPTop(HP* php);

bool HPEmpty(HP* php);

//测试样例
#include"Heap.h"

void test01()
{
	HP hp;
	HPInit(&hp);

	int arr[] = { 17,20,10,13,19,15 };
	for (int i = 0; i < 6; i++)
	{
		HPPush(&hp, arr[i]);
	}

	//HPPop(&hp);

	while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}


	HPDestroy(&hp);
}

int main()
{
	test01();
	return 0;
}

真相永远只有一个！

在这里插入图片描述

标签：arr,php,int,HP,结点,二叉树,Heap,child,数据结构
From： https://blog.csdn.net/Jdxxwu/article/details/142446172

相关文章

  • 数据结构:双向链表（Doubly Linked List篇）手把手带你入门数据结构~
    文章目录前言一、双向链表的概念1.结构特点：2.优点：二、双向链表的实现1.双向链表的结构2.双向链表初始化3.双向链表销毁4.双向链表打印5.双向链表尾插6.双向链表头插7.双向链表尾删8.双向链表头删9.双向链表查找10.双向链表指定位置插入11.双向链表指定位置......
  • 662. 二叉树最大宽度
    题目链接662.二叉树最大宽度思路BFS+层次遍历题解链接官方题解关键点与传统层次遍历的差异点：为节点进行编码，最大宽度为队列中最后节点与最初节点之间的节点数量时间复杂度\(O(n)\)空间复杂度\(O(n)\)代码实现：classSolution:defwidthOfBina......
  • 16年408-数据结构
    第一题：解析：经过查表可知：a的链接地址是1010H，而1010H正是表中e所在的位置。由题可知f存放的位置是1014H，要将f链接在a和e的中间，则a后面要链接f，f后面要链接e，e的链接地址不变因此答案是1014H，1004H，1010H，答案选D第二题：解析：选D。p->next->prev：p的后一个节点的prev指针......
  • 15年408-数据结构
    第一题解析：栈第一次应该存main的信息。然后进入到main里面，要输出S(1)，将S(1)存入栈内，进入到S(1)中，1>0,所以还要调用S(0)S(0)进入栈中，此时栈内从下至上依次是main(),S(1),S(0)答案选A第二题：解析：先序序列个数为0时，二叉树个数是1：先序序列个数为1时，二叉树个数是1：......
  • 数据结构算法题
    目录轮转数组原地移除数组中所有元素val删除有序数组中的重复项合并两个有序数组轮转数组思路1：1.利用循环将最后一位数据放到临时变量（n）中2.利用第二层循环将数据往后移一位3.将变量（n）的数据放到数组第一位时间复杂度：O(N^2)空间复杂度：O(1)思路2：1.创建一个空间......
  • 数据结构：单链表
    单链表单链表概念与结构节点链表的性质单链表的打印实现单链表创建新的节点在末尾插入数据在头部插入数据删除尾部数据删除第一个节点在链表中寻找目标数据在指定位置之前插入数据在指定位置之后插⼊数据删除pos结点删除pos之后的结点销毁链表单链表测试单链表概念与......
  • 基础数据结构之链表
    链表1)概述定义在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续Incomputerscience,alinkedlistisalinearcollectionofdataelementswhoseorderisnotgivenbytheirphysicalplacementinmemory.Instead,eachelem......
  • [Python手撕]二叉树的序列化和反序列化
    #Definitionforabinarytreenode.#classTreeNode(object):#def__init__(self,x):#self.val=x#self.left=None#self.right=NoneclassCodec:defserialize(self,root):defdfs(root):ifr......
  • C语言结构体、指针和常见数据结构
    在学习C语言时，结构体、指针和常见的数据结构如链表、栈、队列、二叉树等，是绕不开的重点。本篇博客用通俗易懂的方式，介绍这些概念，结合简单的代码示例，带你逐步掌握这些基础知识。1.结构体和指针我们先来看一眼结构体和指针,不懂这些的话,下面的代码肯定看不懂,没学过......
  • 数据结构-线性表的单链式存储结构图解及C语言实现
    概念链式存储：结点在存储器中的位置是任意的，即逻辑相邻的数据元素在物理上不一定相邻链式存储结构也称非顺序映像或链式映像图解链式存储结构中结点一般有两个部分组成，即数据域(data)和指针域，数据域是用于存放数据的，指针域是用来指向下一结点的地址的，其中头节点指向该链表......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99