【数据结构】二叉树顺序实现（大堆）--＞赋源码

2024-06-13 1340阅读

欢迎来到我的Blog，点击关注哦💕

【数据结构】二叉树顺序实现（大堆）--＞赋源码
（图片来源网络，侵删）

前言

在前面的顺序表、链表、都是线性表。今天的所介绍的二叉树是一种非线性数据结构。

树的概念以及介绍

定义

树是一种非线性的数据结构，它由n（n>0）个有限结点组成一个具有层次关系的集合。

树的相关概念（类比人类血缘关系）

  • 结点的度：一个结点含有的子树的个数称为该结点的度。

  • 叶结点或终端结点：度为0的结点称为叶结点。

  • 非终端结点或分支结点：度不为0的结点。

  • 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点。

  • 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点。

  • 兄弟结点：具有相同父结点的结点互称为兄弟结点。

  • 树的度：一棵树中，最大的结点的度称为树的度。

  • 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。

  • 树的高度或深度：树中结点的最大层次。

  • 堂兄弟结点：双亲在同一层的结点互为堂兄弟。

  • 结点的祖先：从根到该结点所经分支上的所有结点。

  • 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。

  • 森林：由m（m>0）棵互不相交的树的集合称为森林

    二叉树的概念

    二叉树是树的一种特殊形式，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

    满二叉树

    满二叉树的定义

    1.满二叉树是一种特殊的二叉树，它的特点是每一层的节点数都达到最大值，即每一层的节点数都恰好为2的幂次（除了最后一层以外）。

    2.如果满二叉树的深度为k，那么它的节点总数为2^k - 1。在满二叉树中，除了最后一层的节点之外，其余每一层的节点都是完全填满的，而且最后一层的节点也是从左到右连续排列的

    满二叉树性质
    1. 满二叉树的深度为k，节点总数为2^k - 1。
    2. 满二叉树的每一层的节点数都达到最大值，即每一层的节点数为2^(i-1)，其中i是层数。
    3. 满二叉树的叶子节点全部位于最后一层。
    4. 满二叉树的节点要么是叶子节点（度为0），要么是度为2的节点，不存在度为1的节点

    如下图：

    完全二叉树

    完全二叉树的定义
    1. 除了最后一层外，其他每一层的节点数都达到最大数量，即该层的节点数等于2的幂减去1。
    2. 最后一层的节点都集中在最左边，并且右边的节点可以少，但不能有空位。
    完全二叉树的性质

    1.完全二叉树的节点编号从1开始，对于编号为i的节点，其左子节点的编号为2i，右子节点的编号为2i+1。

    2.如果一棵完全二叉树有n个节点，那么它的深度大约为log2(n)+1。

    3.完全二叉树的特点是叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。

    二叉树的顺序实现

    堆

    堆的定义

    堆是一种特殊的完全二叉树，它可以被视为一种特殊的顺序表。

    堆的分类

    堆的特点是父节点的值总是大于或小于其子节点的值，根据这个特点，堆可以分为大根堆和小根堆。在大根堆中，根节点的值是最大的，而在小根堆中，根节点的值是最小的。

    二叉树的实现（本质：顺序表，形式：大根堆）

    二叉树的功能

    //初始化
void HeapInit(Heap* hp);
//扩容
void CheckCapacity(Heap* hp);
//插入数据
void HeapPush(Heap* hp, HPDataType x);
//删除数据
void HeapPop(Heap* hp);
//顶数据
HPDataType HeapTop(Heap* hp);
//大小
int HeapSize(Heap* hp);
//堆是否为空
bool HeapEmpty(Heap* hp);
//销毁
void HeapDestory(Heap* hp);

    二叉树的定义以及初始化

    定义
    typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;
    初始化

    本质就是顺序表，没有太大的变化，开辟初始空间。

    //初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
	if (hp->a == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	hp->capacity = 4;
	hp->size = 0;
}

    二叉树空间扩容

    //扩容
void CheckCapacity(Heap* hp)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * hp->capacity * 2);
		if(tmp == NULL)
		{
			perror("malloc fail");
			return NULL;
		}
		hp->a = tmp;
		hp->capacity *= 2;
	}
}

    二叉树的插入数据

    数据从尾部插入，但是要保证大堆结构，我们调用函数 AdjustUp（向上调整）。

    插入
    //插入数据
void HeapPush(Heap* hp,HPDataType x)
{
	assert(hp);
	CheckCapacity(hp);
	hp->a[hp->size++] = x;
	AdjustUp(hp,hp->size-1);
}
    AdjustUp（向上调整）

    在这里，由于孩子结点和父亲结点的关系是：父亲 = （孩子-1）/ 2. （顺序表本质就是数组，首元素下标就是0）

    如图：结点为4 父亲节点为 （4-1）/ 2 = 1。

    如果发现，孩子节点大于父亲节点，进行交换。

    //向上调整
void AdjustUp(Heap* hp, int child)
{
	assert(hp);
	int parent = (child - 1) / 2;
	while (child >= 0)
	{
		if (hp->a[child] > hp->a[parent])
		{
			Swap(&(hp->a[child]), &(hp->a[parent]));
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
    Swap(交换)
    //交换
void Swap(HPDataType* child, HPDataType* parent)
{
	HPDataType tmp = *child;
	*child = *parent;
	*parent = tmp;
}

    二叉树数据的删除

    在这展示的是首节点的删除，尾节点删除的意义不大

    删除

    删除操作是首节点，和尾节点进行互换，删除尾节点。

    • 保证了删除效率
    • 保证了堆的原始关系

      由于尾结点互换到了头结点，需要进行AdjustDown（向下调整）

      //删除数据
void HeapPop(Heap* hp)
{
	assert(hp);
	
	hp->a[0] = hp->a[hp->size - 1];
	hp->size--;
	AdjustDown(hp,hp->size);
}
      AdjustDown（向下调整）

      在这里，由于孩子结点和父亲结点的关系是：孩子 = 父亲*2 + 1.

      如图：1. 孩子结点 5 = 2 * 2 +1

      ​ 2. 孩子结点 6 = 2 * 2 + 1 +1

      //向下调整
void AdjustDown(Heap* hp,int size)
{
	assert(hp);
	int parent = 0;
	int child = parent * 2 + 1;
	while (child a[parent] a[child])
		{
			Swap(&hp->a[parent], &hp->a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

      二叉树顶数据

      //顶数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}

      二叉树大小

      //大小
int HeapSize(Heap* hp)
{
	assert(hp);
	
	return hp->size;
}

      二叉树是否为空

      //堆是否为空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

      二叉树销毁

      //销毁
void HeapDestory(Heap* hp)
{
	free(hp->a);
	hp->a == NULL;
}

      源码

      Heap.h

      #pragma once
#include 
#include 
#include 
#include 
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;
//初始化
void HeapInit(Heap* hp);
//扩容
void CheckCapacity(Heap* hp);
//插入数据
void HeapPush(Heap* hp, HPDataType x);
//删除数据
void HeapPop(Heap* hp);
//顶数据
HPDataType HeapTop(Heap* hp);
//大小
int HeapSize(Heap* hp);
//堆是否为空
bool HeapEmpty(Heap* hp);
//销毁
void HeapDestory(Heap* hp);

      Heap.c

      #define _CRT_SECURE_NO_WARNINGS  1
#include "heap.h"
//初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
	if (hp->a == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	hp->capacity = 4;
	hp->size = 0;
}
//扩容
void CheckCapacity(Heap* hp)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * hp->capacity * 2);
		if(tmp == NULL)
		{
			perror("malloc fail");
			return NULL;
		}
		hp->a = tmp;
		hp->capacity *= 2;
	}
}
//交换
void Swap(HPDataType* child, HPDataType* parent)
{
	HPDataType tmp = *child;
	*child = *parent;
	*parent = tmp;
}
//向上调整
void AdjustUp(Heap* hp, int child)
{
	assert(hp);
	int parent = (child - 1) / 2;
	while (child >= 0)
	{
		if (hp->a[child] > hp->a[parent])
		{
			Swap(&(hp->a[child]), &(hp->a[parent]));
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入数据
void HeapPush(Heap* hp,HPDataType x)
{
	assert(hp);
	CheckCapacity(hp);
	hp->a[hp->size++] = x;
	AdjustUp(hp,hp->size-1);
}
//向下调整
void AdjustDown(Heap* hp,int size)
{
	assert(hp);
	int parent = 0;
	int child = parent * 2 + 1;
	while (child a[parent] a[child])
		{
			Swap(&hp->a[parent], &hp->a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//删除数据
void HeapPop(Heap* hp)
{
	assert(hp);
	
	hp->a[0] = hp->a[hp->size - 1];
	hp->size--;
	AdjustDown(hp,hp->size);
}
//顶数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}
//大小
int HeapSize(Heap* hp)
{
	assert(hp);
	
	return hp->size;
}
//堆是否为空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}
//销毁
void HeapDestory(Heap* hp)
{
	free(hp->a);
	hp->a == NULL;
}

      test.c

      #define _CRT_SECURE_NO_WARNINGS  1
#include "heap.h"
void Heaptest()
{
	Heap HP;
	HeapInit(&HP);
	HeapPush(&HP, 3);
	HeapPush(&HP, 5);
	HeapPush(&HP, 40);
	HeapPush(&HP, 70);
	HeapPush(&HP, 18);
	HeapPush(&HP, 25);
	while (!HeapEmpty(&HP))
	{
		printf("%d ", HeapTop(&HP));
		HeapPop(&HP);
	}
	HeapDestory(&HP);
}

int main()
{
	Heaptest();
	return 0;
}
VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]