顺序储存的二叉树（堆）

顺序储存的二叉树（堆）

引用

CSDN

1.

https://blog.csdn.net/2403_87752060/article/details/145795411

本节我们将开始学习数据结构中一个重要的结构——树。

1：树

1：树的结构和概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

注意点：

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

子树是不相交的（如果存在相交就是图了，图以后得课程会有讲解）

除了根结点外，每个结点有且仅有1个父结点

一棵N个结点的树有N-1条边

2：树的某些名词

2：二叉树

1：二叉树的概念

在树形结构中，我们最常用的就是二叉树，一棵二叉树是结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空。

从上面的二叉树图片我们可以总结出二叉树的重要特性：

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

2：特殊的二叉树

1. 满二叉树

顾名思义二叉树每一层都是满的

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

如图：

2. 完全二叉树

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

3：二叉树的储存法

1. 顺序储存，使用数组
2. 链式储存，使用链表

我们本节重点学习使用数组的表示方法，它还有一个名字叫做堆。

3：堆的实现

1：堆的结构体

都知道堆是顺序储存，所以结构体和顺序表一样，一个表示大小，一个表示下标，动态申请空间

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

我们让数组元素重新命名，让我们可以轻松修改元素的类型，方便其他时候使用。

2：堆的方法，次要方法

//堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HPEmpty(Heap* hp);

3：堆次要方法的实现

void HeapInit(Heap* hp)
{
    hp->a = NULL;
    hp->capacity = hp->size = 0;
}
void HeapDestory(Heap* hp)
{
    free(hp->a);
    hp->a = NULL;
    hp->capacity = hp->size = 0;
}
int HeapSize(Heap* hp)
{
    return hp->size;
}
bool HPEmpty(Heap* php)
{
    assert(php);
    return php->size == 0;
}

4：堆里面的重要方法（为堆排序打基础）

堆排序是一种非常重要的排序算法，我们先学堆排序的基础，向上调整和向下调整很重要！

1. 向上调整算法

void AdjustUp(HPDataType* arr, int child)
{
    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;
        }
    }
}

子节点和父节点的关系，向上调整算法，是子节点和父节点对比交换（交换函数自行定义），然后通过循环，互换子节点和父节点的位置，然后子节点和父节点向上移。

2. 向下调整算法

void AdjustDown(HPDataType* arr, int parent, int n)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && arr[child] < arr[child + 1])
        {
            child++;
        }
        if (arr[child] > arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

我们需要把堆传递和需要调整的节点parent和堆的元素个数size传递过去。依然是通过子节点和父节点的比较进行调整。

5：堆的增删查改

1. 堆的插入

void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if (hp->capacity == hp->size)
    {
        int newcapcity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
        HPDataType* arr = (HPDataType*)realloc(hp->a, newcapcity * sizeof(HPDataType));
        if (arr == NULL)
        {
            perror("realloc fail");
            exit(1);
        }
        hp->a = arr;
        hp->capacity = newcapcity;
        hp->a[hp->size] = x;
        AdjustUp(hp->a, hp->size);
    }
}

2. 堆的删除（默认删除堆顶元素）

void HeapPop(Heap* hp)
{
    assert(!HPEmpty(hp));
    Swap(&hp->a[0], &hp->a[hp->size - 1]);
    --hp->size;
    AdjustDown(hp->a, 0, hp->size);
}

3. 获取堆顶元素

HPDataType HeapTop(Heap* hp)
{
    assert(!HPEmpty(hp));
    return hp->a[0];
}

4：堆排序（important）

void HeapSort(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        AdjustUp(a, i);
    }
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, 0, end);
        end--;
    }
}