c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.
https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343
给大家分享一句我很喜欢我话: 知不足而奋进,望远山而前行!!! 铁铁们,成功的路上必然是孤独且艰难的,但是我们不可以放弃,远山就在前方,但我们能力仍然不足,所有我们更要奋进前行!!! 今天我们更新了二叉树内容, 🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
首先我们为大家说一下树的概念和结构,树是一种非线性的数据结构,它是由n(n >= 0)个有限结点组成的一个具有层次关系的集合,把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
其中这些概念中第 4、6、7条较为重要,其余了解一下即可。
相对于线性表,树的结构就复杂很多了。最常用的表示方法——孩子兄弟表示法。
与普通的树最大的不同是它最多只有两个子树。
完全二叉树是个效率很高的数据结构,完全二叉树是由满二叉树引出来的。
假设树的高度是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;
}
#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;
}
#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;
}
#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);