【数据结构】二叉树（上）
文章目录
- 二叉树的概念
- 特殊的二叉树
- 二叉树的性质
- 二叉树的存储结构
- 二叉树的顺序结构
- 堆的概念及结构
- 堆的实现
- 向上调整法
- 向下调整法
- 堆的应用
- 堆排序
- TOP-K问题
二叉树的概念
二叉树是一种树的度不大于2的树，也就是它的节点的度都是小于等于2的。二叉树的子树有左右之分，左右的次序不能颠倒，因此二叉树是一个有序树。任意的二叉树都由空树、只有根节点、只有左子树、只有右子树、左右子树均存在这几种情况复合而成。
特殊的二叉树
完全二叉树：完全二叉树是一种效率很高的数据结构，如果一个二叉树的深度为k，节点总数不小于2k-1，同时不大于2k-1，并且在最后一层时，每个节点从左到右保持连续，则它就是完全二叉树。
满二叉树：每一层的节点数都达到了最大值即为满二叉树。如果说一个二叉树的深度为k，且节点总数是2k-1，那它就是一个满二叉树，我们可以通过这个公式来判断一个二叉树是不是满二叉树。本质上来说，满二叉树是一种特殊的完全二叉树。
需要注意的是，虽然满二叉树是一种特殊的完全二叉树，但是完全二叉树是由满二叉树引出来的。
二叉树的性质
- 一颗非空二叉树的第 i 层上最多有2i-1个节点；
- 深度为h的二叉树的最大节点数是2h-1；
- 对任何一棵二叉树，如果度为0其叶节点的个数为n0，度为2的分子节点个数为n2，则有n0=n2+1；
- 假设具有n个节点的满二叉树的深度h，则有h=log2(n+1)；
- 对于具有n个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的节点有：
①若i>0，i位置节点的父节点序号：(i-1)/2（取商舍余）；
②若2i+1<n，左孩子序号：2i+1，若2i+1>=n则无左孩子；
③若2i+2<n，右孩子序号：2i+2，若2i+2>=n则无右孩子。
二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
- 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间浪费。而实际开发中只有堆待会使用数组来存储，二叉树顺序存储物理上是一个数组，在逻辑上是一颗二叉树。 - 链式存储
二叉树的链式存储是指用链表来表示一棵二叉树，通常的方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来指向左右孩子的存储地址。链式结构分为二叉链和三叉链，一般情况下我们二叉树所用到的是二叉链，但是如红黑树这些使用的则是三叉链。
typedef int HPDataType;
//顺序存储
typedef struct Heap
{
HPDataType* a;//指向数组
int size;//有几个值
int capacity;//容量
}Heap;
typedef int BTDataType;
//二叉链
struct BinaryTreeNode
{
struct BinTreeNode* pleft;//指向当前节点左孩子
struct BinTreeNode* pright;//指向当前节点右孩子
BTDataType data;//当前节点值
}
//三叉链
struct BinaryTreeNode
{
struct BinTreeNode* pparent;//指向当前节点的双亲
struct BinTreeNode* pleft;//指向当前节点左孩子
struct BinTreeNode* pright;//指向当前节点右孩子
BTDataType data;//当前节点值
二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。但是完全二叉树是适用顺序机构存储的。现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆是一种数据结构的名字，而不是操作系统中虚拟进程地址空间中的堆。操作系统中的堆是管理内存的一块区域分段。
堆的概念及结构
堆是一个特殊的完全二叉树，一个堆一定是一棵完全二叉树，但是一棵完全二叉树不一定是一个堆。一棵完全二叉树中某个节点的值总是不大于或不小于其父节点的值那这就是一个堆。
堆分为大堆和小堆，如果堆中某个节点的值总是不大于其父节点的值，这就是一个大堆；如果堆中某个节点的值总是不小于其父节点的值，这就是一个小堆。
堆的实现
向上调整法
在堆插入数据的时候，新插入的数据可能需要调整位置，这时候就要用到向上调整法。它的原理是利用二叉树子节点找父节点的规则，i节点的父节点=(i-1)/2，找到父节点之后，进行大小比较。根据堆是大堆还是小堆进行调整。
向下调整法
向下调整法在堆的构建和删除时使用，构建的时候，每次进入新数据比较一下看是否向下调整；删除的时候涉及到一个思想，如果我们删除堆顶元素之后，将子孙依次向上挪动以为会导致所有子孙的关系全部被破坏。所以堆顶元素被删除后，我们采用的做法是将最后一个叶子移动到堆顶，然后将它与左右孩子中大的或者小的一个进行比较（具体和哪个比较由堆是大堆还是小堆决定），然后根据比较结果进行决定是否向下调整。
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
// 向下调整
void AdjustDown(HPDataType* a, int n, int parent);
// 向上调整
void AdjustUp(HPDataType* a, int child);
// 交换函数
void Swap(HPDataType* p1, HPDataType* p2);
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
// 堆的初始化
void HeapInit(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//如果空间满了，就扩容
if (hp->size == hp->capacity)
{
int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp->a, hp->size - 1);
}
// 堆的删除
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
//将最后一位移动到根节点，以确保根节点左右子树的结构完整性
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
AdjustDown(hp->a, hp->size, 0);
}
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 向上调整
void AdjustUp(HPDataType* a, int child)
{
//通过孩子找父母
int parent = (child - 1) / 2;
while (child > 0)
{
//孩子大于父亲，交换，继续向上调整；孩子小于父亲，调整结束
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
// 向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
//确认child指向值大的那个孩子
if (child + 1 < n && a[child + 1] < a[child])
{
child++;
}
//孩子大于父亲，交换，继续向下调整；孩子小于父亲，调整结束
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
assert(hp);
//为空则返回真
return hp->size == 0;
}
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
//开空间
hp->a = (HPDataType*)malloc(hp->a, sizeof(HPDataType) * n);
if(hp->a == NULL)
{
perror("malloc fail");
exit(-1);
}
memcpy(hp->a, a, sizeof(HPDataType) * n);
hp->size = hp->capacity = n;
//建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
}
堆的应用
堆排序
利用向下调整法根据大堆还是小堆实现升序或者降序。
TOP-K问题
求数据结合中前K个最大的或最小的元素，一般情况下数据量都比较大；
对于TOP-K问题，最简单的方法就是排序。但是如果数据量过于庞大，排序就不太行了，这里就需要用堆来解决。
思路：用数据集合中前K个元素建堆，用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。
void PrintTopK(int* a, int n, int k)
{
int* minHeap = malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
exit(-1);
}
for (int i = 0; i < k; i++)
{
minHeap[i] = a[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minHeap, k, i);
}
for (int i = k; i < n; i++)
{
if (a[i] > minHeap[0])
{
minHeap[0] = a[i];
AdjustDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}
printf("\n");
}
