【数据结构】C++语言实现二叉树的介绍及堆的实现(详细解读)

9efbcbc3d25747719da38c01b3fa9b4f.gif

 c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343

给大家分享一句我很喜欢我话:

知不足而奋进,望远山而前行!!!

铁铁们,成功的路上必然是孤独且艰难的,但是我们不可以放弃,远山就在前方,但我们能力仍然不足,所有我们更要奋进前行!!!

今天我们更新了二叉树内容,

🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

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

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

有关树的一些概念:

  1. 节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的为6
  2. 叶节点或终端节点:度为0的节点称为叶节点;如上图:B、C、H、I…等节点为叶节点非终端节点或分支节点:度不为0的节点;如上图:D、E、F、G…等节点为分支节点
  3. 兄弟节点:具有相同父节点的节点互称为兄弟节点;如上图:B、C是兄弟节点
  4. 树的度:一棵树中,最大的节点的度称为树的度;如上图:树的度为6
  5. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
  6. 树的高度或深度:树中节点的最大层次;如上图:树的高度为4(有两种说法-从0开始还是从1开始,空树-1,空树0)
  7. 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
  8. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
  9. 森林:由m (m>0)棵互不相交的多颗树的集合称为森林;(数据结构中的学习并查集本质就是一个森林)——(日常很少碰到森林,并查集就是一个森林)

其中这些概念中第 4、6、7条较为重要,其余了解一下即可。

树的要求:

  • 子树是不相交的
  • 除了根结点之外,每个结点有且仅有一个父结点
  • 一个N个结点的树有N-1条边

树的表示

相对于线性表,树的结构就复杂很多了。最常用的表示方法——孩子兄弟表示法。

二叉树

与普通的树最大的不同是它最多只有两个子树。

特殊的二叉树

  1. 满二叉树:每一层都是满的。

    假设一棵满二叉树的高度是 h,那么它的总结点个数是:20+21+22+…2(h-1) =N。

    推导公式:2^h-1 = N;h = log2N+1以2位底N的对数+1。

  2. 完全二叉树

完全二叉树是个效率很高的数据结构,完全二叉树是由满二叉树引出来的。

假设树的高度是h,前h-1层是满的,最后一层不满,但是最后一层从左往右都是连续的。

最后一层最少有一个结点。

结点个数为:2^h-1-X= N,高度近似为:h = log2N+1+X以二为底N的对数+1

图有点难看不要介意

这些就是关于树的一些基本概念,下面我们来介绍一下关于树的实现。

堆的实现:

这里我们将会分为初始化、销毁、建堆、堆的删除、取出堆顶元素、判断是否为空、向上调整和向下调整这几步来完成。

头文件及堆结构的定义:

#pragma once
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<algorithm>
#include<cmath>
#include<utility>



typedef int HPDataType;

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

初始化:

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

}

销毁:

void HPDestroy(HP* php)
{
	assert(php);

	free(php);
	php->a = NULL;
	php->capacity = php->size = 0;
	
}

向上调整:

//向上调整(小根堆)
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])//小于就换就相当于建小堆
		//if (a[child] > a[parent])//大于就换就会变成大堆
		{
			std::swap(a[child], a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

建堆:

void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc failed!!!");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size++] = x;

	//向上调整
	AdjustUp(php->a, php->size - 1);
}

向下调整:

void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设法
	//假设左孩子小
	int child = parent * 2 + 1;

	while(child<n)
	{
		if (child + 1 < n &&a[child + 1] < a[child])//这里如果是左孩子大于右孩子,就要再加加child
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			std::swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
	
}

删除堆顶的数据:

HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);


	return php->a[0];
}

判空:

bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

总代码:

TEST.c:

#include"Heap.h"


void TestHeap1()
{
	int a[] = { 4,2,8,1,5,6,7,9 };
	HP hp;
	HPInit(&hp);
	for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}

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


	HPDestroy(&hp);
}

void HeapSort(int* a, int n)
{
	//首先建堆
	//升序:建大堆
	//降序:建小堆
	for (int i=0;i<n;i++)
	{
		AdjustUp(a, i);
	}

	int end = n - 1;
	///这里>0即可,因为=0时只剩下最后一个,就不再需要继续进行了
	while (end>0)//思路就是:比如我们升序排序,那么我们就利用大根堆,每次都将最大的那个数放在最顶上,然后将它和最后一个交换,然后让整体的大小--,那么最后一个就不再会受影响
	{
		std::swap(a[0], a[end]);
		AdjustDown(a, end, 0);
		--end;
	}


}

void TestHeap2()
{
	int a[] = { 4,2,8,1,5,6,9,7,3,10,23,14,125 };
	HeapSort(a, sizeof(a) / sizeof(0));

	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		std::cout << a[i] << " ";
	}
}

int main()
{
	TestHeap2();

	return 0;
}

Heap.c:

#include"Heap.h"


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

}


//销毁
void HPDestroy(HP* php)
{
	assert(php);

	free(php);
	php->a = NULL;
	php->capacity = php->size = 0;
	
}


//向上调整(小根堆)
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])//小于就换就相当于建小堆
		//if (a[child] > a[parent])//大于就换就会变成大堆
		{
			std::swap(a[child], a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}



//建堆
void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc failed!!!");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size++] = x;

	//向上调整
	AdjustUp(php->a, php->size - 1);
}

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设法
	//假设左孩子小
	int child = parent * 2 + 1;

	while(child<n)
	{
		if (child + 1 < n &&a[child + 1] < a[child])//这里如果是左孩子大于右孩子,就要再加加child
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			std::swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
	
}

//删除堆顶的数据
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	std::swap(php->a[0], php->a[php->size - 1]);//就是将第一个与最后一个换掉,然后将他们向下调整,
	php->size--;//直接size--删去最后一个元素

	AdjustDown(php->a, php->size, 0);
}



//取出堆顶数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);


	return php->a[0];
}



bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

Heap.h:

#pragma once
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<algorithm>
#include<cmath>
#include<utility>



typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	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);

void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-16 01:40:12       0 阅读
  2. QT--气泡框的实现

    2024-05-16 01:40:12       1 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-16 01:40:12       0 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-16 01:40:12       0 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-16 01:40:12       0 阅读
  6. C 语言设计模式(结构型)

    2024-05-16 01:40:12       0 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-16 01:40:12       0 阅读
  8. kafka防止消息丢失配置

    2024-05-16 01:40:12       0 阅读

热门阅读

  1. 单例模式介绍

    2024-05-16 01:40:12       3 阅读
  2. 调用外部的webservice示例

    2024-05-16 01:40:12       3 阅读
  3. 局域网路由器 交换机 ap模式

    2024-05-16 01:40:12       2 阅读
  4. Spring-Cloud-OpenFeign源码解析-02-OpenFeign自动装配

    2024-05-16 01:40:12       2 阅读
  5. 【鱼眼+普通相机】相机标定

    2024-05-16 01:40:12       3 阅读
  6. FastAdmin菜单规则树形结构分类显示

    2024-05-16 01:40:12       2 阅读