[数据结构]：4.二叉树_堆

二叉树_堆

• 前言
• 一，树
• • 1.1树的概念
  • 1.2树的存储结构
• 二，二叉树
• • 2.1 二叉树的概念
  • 2.2二叉树的性质
  • 2.3二叉树的存储结构
• 三，完全二叉树
• • 3.1完全二叉树
  • • 3.1.1完全二叉树的存储结构
  • 3.2满二叉树
• 四，堆
• • 4.1堆的概念
  • 4.2堆的结构
  • 4.3堆的实现
  • 4.4堆的应用

前言

嗨，我是firdawn，本章将简单介绍，树，二叉树，满二叉树的概念，以及堆的实现和相关应用。下面的图是本章的思维导图，那么，让我们开始吧！

一，树

1.1树的概念

树是一种非线性的结构，它是由n(n >= 0)个有限结构组合的一个具有层次关系的集合。因为这种结构看起来像一颗倒挂的树，所以我们把它叫做树。 任何一颗树都可以看作是以下部分组成的： 1.根结点 2.n颗子树 其中，子树又可以看作是由一个根结点和n颗子树构成的。因此，‘‘树是递归定义的’’ 。 不过，我们需要注意的是，树形结构中，子树是不能有交集的，否则就不是树形结构。 树的相关概念： 结点的度: 一个结点含有的子树的个数称为该结点的度； 如上图：A的为6 叶结点或终端结点： 度为0的结点称为叶结点； 如上图：B、C、H、I…等结点为叶结点 非终端结点或分支结点： 度不为0的结点； 如上图：D、E、F、G…等结点为分支结点 双亲结点或父结点： 若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点 孩子结点或子结点： 一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点 兄弟结点： 具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点 树的度： 一棵树中，最大的结点的度称为树的度； 如上图：树的度为6 结点的层次： 从根开始定义起，根为第1层，根的子结点为第2层，以此类推 树的高度或深度： 树中结点的最大层次； 如上图：树的高度为4 堂兄弟结点： 双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点 结点的祖先： 从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先 子孙： 以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙 森林： 由m（m>0）棵互不相交的树的集合称为森林

1.2树的存储结构

对于存储树结构，我们不仅要保存结点的值，也要保存结点之间的关系。所以我们可以用链表来存储树，用链表结点存储树结点的值，链表结点内存储的指针来表示结点之间的关系，但是，每一个结点的子树个数是不确定的，所以结点指针的个数也是不确定的，那么我们应该怎么存储树呢，其实树的存储结构其实有很多种，这里我们列举两种： 1.我们可以使用动态开辟的数组来存储指针，如果结点的子树为k，我们就存储k个指针。代码如下：

typedef int TreeDataType;

typedef struct Child
{
struct TreeNode* arr;
int size;
int capacity;
}Child;

struct TreeNode
{
TreeDataType val;
Child child;
};

2.采用左孩子右兄弟表示法，对于每个树的结点存储指向孩子的指针和指向兄弟的指针。这是一个非常厉害的表示方法，不管一个结点有几个孩子，我们只需要两个指针就可以表示它的所有孩子。

typedef int TreeDataType;

typedef struct TreeNode
{
TreeDataType val;
struct TreeNode* leftchild;
struct TreeNode* rightbrother;
}TNode;

二，二叉树

2.1 二叉树的概念

二叉树指的是树的度最大为2的树，二叉树可以是空树，也可以只有一个结点，一个结点可以只有一个孩子，可以只有左子树或者右子树，亦或者左右子树都存在。 **二叉树概念：**一棵二叉树是结点的一个有限集合，该集合: 1.或者为空 2.由一个根结点加上两棵别称为左子树和右子树的二叉树组成 从上图可以看出：

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树 注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2二叉树的性质

2.3二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。 1.顺序存储 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。 2.链式存储 二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* parent; // 指向当前结点的双亲
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}；

三，完全二叉树

3.1完全二叉树

完全二叉树： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

满二叉树： 满二叉树是特殊的完全二叉树，一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k-1，则它就是满二叉树。

3.1.1完全二叉树的存储结构

参见2.3

3.2满二叉树

参见3.1

四，堆

4.1堆的概念

要得到堆首先需要树是完全二叉树，其次每个根结点都大于或者小于左子树和右子树。我们把每个根结点都大于左右子树的完全二叉树叫作大堆，把每个根结点都大于左右子树的完全二叉树叫作小堆。 堆的性质： 1.堆中某个结点的值总是不大于或不小于其父结点的值 2.堆总是一棵完全二叉树

4.2堆的结构

堆的结构是怎样的呢，以下是相关代码

Heap.h

#pragma once

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int HPDataType;

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

void HeapInit(HP* php);
void HeapDestroy(HP* php);

void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);

HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

void Swap(HPDataType* p1, HPDataType* p2);
void adjustUp(HPDataType* arr, int child);
void adjustDown(HPDataType* arr, int size, int parent);

Heap.c

#include"Heap.h"

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

php->arr = NULL;
php->size = 0;
php->capacity = 0;
}
void HeapDestroy(HP* php)
{
assert(php);

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

void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

void adjustUp(HPDataType* arr, int child)
{
assert(arr);

int parent = (child – 1) / 2;
while (child > 0)
{
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child – 1) / 2;
}
else
{
break;
}

}
}

void adjustDown(HPDataType* arr, int size, int parent)
{
assert(arr);

int child = parent * 2 + 1;//child指向更小的孩子节点

while (child < size)
{
if (child + 1 < size && arr[child + 1] < arr[child])
{
Swap(&arr[child], &arr[child + 1]);

}

if (arr[child] < arr[parent])
{
Swap(&(arr[child]), &(arr[parent]));
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

void HeapPush(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->arr,newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr[php->size] = x;
php->size++;

adjustUp(php->arr, php->size – 1);
}
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);

Swap(&(php->arr[0]), &(php->arr[php->size – 1]));
php->size—;

//向下调整
adjustDown(php->arr, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);

return php->arr[0];
}
bool HeapEmpty(HP* php)
{
assert(php);

return php->size == 0;
}
int HeapSize(HP* php)
{
assert(php);

return php->size;
}

Test.c

#include"Heap.h"

void HPSortUp(HPDataType* arr, int size)
{
assert(arr);

int k = size;
while (k—)
{
Swap(&arr[0], &arr[size – 1]);
size—;
adjustDown(arr, size, 0);
}

}

//void HPSortDown(HPDataType* arr, int size)
//{
//assert(arr);
//
//
//int k = size;
//while (k–)
//{
//Swap(&arr[0], &arr[size-1]);
//size–;
//adjustDown(arr, size, 0);
//}
//
//
//}

void Test()
{

//降序 小堆
//升序 大堆

//降序

int arr[] = { 2,5,14,7,10,42,34,1,0,27 };

////采取插入，也就是向上调整的方式进行排序
//
//for (int i = 1; i < sizeof(arr) / sizeof(int); i++)//将数组转化为堆的结构
//{
//adjustUp(arr, i);
//}
//HPSortUp(arr, sizeof(arr) / sizeof(int));

//采取向下调整的方式进行排序

int size = sizeof(arr) / sizeof(int);
for (int i = (size – 1 – 1) / 2; i >= 0; i—)
{
adjustDown(arr, size, i);
}

HPSortUp(arr, sizeof(arr) / sizeof(int));
}

int main()
{
/*HP hp;
HeapInit(&hp);*/

//int arr[] = { 2,5,14,7,10,42,34,1,0,27 };
//for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
//{
//HeapPush(&hp, arr[i]);
//}
//HPDataType* tmp = (HPDataType*)malloc(sizeof(arr));

//while (!HeapEmpty(&hp))
//{
//int i=0;
////printf("%d ", HeapTop(&hp));
//tmp[i++] = HeapTop(&hp);//将排序好的数值存储起来
//HeapPop(&hp);
//}

Test();

//HeapDestroy(&hp);

return 0;
}

4.3堆的实现

int array[] = {27,15,19,18,28,34,65,49,25,37};

上面的代码块中，我们给出了一个数组。如果我们要对其建堆，我们应该怎么做呢？ 1.我们比较容易想到的是先上调整建堆，假设我们有一个空二叉树，我们可以不停地对其插入数据，然后向上调整，就可以得到堆啦。这种方法的时间复杂度为O(n*log₂n)

int arr[] = { 2,5,14,7,10,42,34,1,0,27 };
for (int i = 1; i < sizeof(arr) / sizeof(int); i++)//对数组进行建堆
{
adjustUp(arr, i);
}

2.第二种方法就是向下调整建堆，不过向下调整算法有一个前提：左右子树必须是一个堆，才能调整，所以我们要调整向下调整根结点，需要先将他的左右子树调整为堆，而对子树调整为堆时，需要子树的左右子树为堆，然后调整根结点，依此类推，我们就需要从最后一个有孩子的父亲结点也就是最后一个叶子结点的父亲结点开始向下调整。这种方法的时间复杂度为O(n)

//采取向下调整的方式建堆
int size = sizeof(arr) / sizeof(int);
for (int i = (size – 1 – 1) / 2; i >= 0; i—)
{
adjustDown(arr, size, i);
}

向下调整建堆时间复杂度推导如下：

因为第二种方法，向下调整的方式建堆的时间复杂度更小，所以我们一般采用第二种方法进行建堆。

4.4堆的应用

4.4.1 堆排序 堆排序即利用堆的思想来进行排序，总共分为两个步骤 1.建堆 ： 升序，建大堆 降序，建小堆 2.利用堆删除思想来进行排序 ： 建堆和堆删除都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

4.4.2 TOP-K问题 TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下： 1.用数据集合中前K个元素来建堆 1.1前k个最大的元素，则建小堆 1.2前k个最小的元素，则建大堆

2.用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void CreatData()
{
srand(time(0));

int N = 100000;
const char* file= "test.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}

for(int i=0;i<N;i++)
{
int num = (rand() + i)%N;
fprintf(fin, "%d\\n", num);
}

fclose(fin);
}

void PrintTopK()
{
int k = 0;
printf("请输入k:>");
scanf("%d", &k);

//打开文件
const char* file = "test.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}

int num = 0;
int* arr = (int*)malloc(k * sizeof(int));
if (arr = NULL)
{
perror("malloc fail");
return;
}

//向数组中写入k个数据
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &num);
}
//向下调整建堆，时间复杂度为O(n)
for (int i = (k–1–1)/2; i >0; i—)
{
AdjustDown(arr, k, num);
}
while (fscanf(fout, "%d", &num) > 0)
{
if (num > arr[0])
{
arr[0] = num;
AdjustDown(arr, k, 0);

}
}

for (int i = 0; i < k; i++)
{
printf("%d ", arr[i]);
}

}

void Test2()
{
//CreatData();
PrintTopK();
}

int main()
{
//Test1();

//Test2();

return 0;
}