《数据结构修炼手册》----二叉树的顺序结构及实现

二叉树的顺序结构及实现

1. 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2. 堆的概念及结构

如果有一个关键码的集合K = { k0，k1 ,k2…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足：Ki<= K2i+1且 Ki<=K2*i+2 ( Ki>=
K2i+1且Ki<=K2*i+2) i = 0，1，
2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

简单描述：

大堆(大根堆)：树中父亲都大于（等于）孩子。

小堆（小根堆）：树中父亲都小于（等于）孩子。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

应用场景：堆排序、topk。

3.线性堆的模拟实现

3.1 堆的基本结构定义

typedef int HPDataType;//堆中存放的数据，假设是整型
typedef struct Heap
{
    HPDataType* a;//指针指向堆中存储的数据
    size_t size;//堆中当前元素的数目
    size_t capacity;//堆中所能存储数据的容量
}HP;

3.2 堆的初始化

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

3.3 堆的销毁

void HeapDestory(HP* php)
{
    assert(php);
    free(php->a);
    php->a = NULL;
}

3.4 堆数据的插入

思路：

时间复杂度：log(N)

void Swap(HPDataType* pa, HPDataType* pb)//交换函数：交换数组中的两个元素
{
    HPDataType tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
void AdjustUp(HPDataType* a, size_t child )//堆的向上调整
{
    size_t parant = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parant])//此处如果是<就是小堆，如果是>就是大堆
        {
            Swap(&a[child], &a[parant]);
            child = parant;
            parant = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
void HeapPush(HP* php, HPDataType x)
{
    assert(php);
    //判断是否需要扩充并进行扩充
    if (php->size == php->capacity)
    {
        size_t newCapacity = php->capacity == 0 ? 2 : 2 * php->capacity;
        HPDataType*tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
        if (tmp == NULL)
        {
            printf("realloc failed\n");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newCapacity;
    }
    php->a[php->size] = x;
    php->size++;
    //向上调整，控制保持是堆
    AdjustUp(php->a, php->size - 1);
}

3.5 堆的删除

思路：

1. 第一个数与最后一个位置的数进行交换
2. 删除最后一个数据
3. 向下调整下面是向下调整的图示：时间复杂度：O(log2N)

void Swap(HPDataType* pa, HPDataType* pb)//交换函数：交换数组中的两个元素
{
    HPDataType tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

void AdjustDown(HPDataType* a, size_t size,size_t root)
{
    size_t parant = root;
    size_t child = 2*parant+1;
    
    while (child<size)
    {
        if (child+1<size &&a[child + 1] < a[child])//此时后面的这个如果是<就是小堆，如果是>就是大堆
            ++child;
        if (a[child] < a[parant])//如果是<就是小堆，如果是>就是大堆
        {
            Swap(&a[child], &a[parant]);
            parant = child;
            child = 2 * parant + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapPop(HP* php)
{
    assert(php);
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}

问：堆的删除为什么不直接从后向前进行覆盖，把第一个元素覆盖掉？

答：首先时间复杂度是O(N)，其次堆原来的结构可能会被打乱，同时也可能丧失堆原来的性质变得不再是堆，除非堆原来的数组元素是从小到大或者从大到小是有序的情况下才一定能够保持堆的性质，但即使这种情况下堆的结构仍然会被打乱，即它们的父子关系被破坏掉。

3.6 线性堆判断是否为空

bool HeapEmpty(HP* php)
{
    assert(php);
    return php->size == 0;
}

3.7 求线性堆元素的数目

size_t HeapSize(HP* php)
{
    assert(php);
    return php->size;
}

3.8 返回线性堆头的元素

HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}

3.9 打印线性堆的元素

void HeapPrint(HP* php)
{
    assert(php);
    for (size_t i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");
}