二叉树的顺序实现与堆结构详解

孩子兄弟表示法：树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法

struct TreeNode { 
    struct Node* child; // 最左边的孩子结点 
    struct Node* brother; // 指向其右边的下一个兄弟结点 
    int data; // 结点中的数据域 
};

1.4 树形结构实际应用场景

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。

二、二叉树

2.1 二叉树的概念与结构

二叉树（binary tree）是一种非线性数据结构，代表'祖先'与'后代'之间的派生关系，体现了'一分为二'的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

总结：

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

注意：对于任意的二叉树都是由以下几种情况复合而成的

2.2 二叉树的基本术语

• 根节点（root node）：位于二叉树顶层的节点，没有父节点。
• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None。
• 节点所在的层（level）：从顶至底递增，根节点所在层为 1。
• 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2。
• 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
• 节点的深度（depth）：从根节点到该节点所经过的边的数量。

节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

2.3 特殊二叉树

1. 完美二叉树 (满二叉树)

完美二叉树 (perfect binary tree) 所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0，其余所有节点的度都为 2；若树的高度为 h，则节点总数为 2^(h+1) - 1，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。

2. 完全二叉树

完全二叉树 (complete binary tree) 只有最底层的节点未被填满，且最底层节点尽量靠左填充。

2.4 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

2.4.1 顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。

2.4.2 链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。（红黑树等会用到三叉链。）

三、实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。

3.1 堆的概念与结构

堆是一种完全二叉树，具有以下性质：

最小堆：每个节点的值都小于或等于其子节点的值。

最大堆：每个节点的值都大于或等于其子节点的值。

堆常用于实现优先队列，因为它能有效地支持插入和删除操作。

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

3.2 堆的实现

我们以小堆为例进行实现：

3.2.1 存储结构

二叉树的顺序存储通常使用数组来实现。对于一个节点在数组中的索引 i，可以通过以下方式找到其父节点和子节点的索引： 父节点：(i - 1) / 2（取整） 左子节点：2 * i + 1 右子节点：2 * i + 2

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

这里可以看到堆的底层结构和动态顺序表一样。

3.2.2 相关操作

1. 初始化

// 初始化
void HPInit(HP* p) {
    assert(p);
    p->arr = NULL;
    p->size = p->capacity = 0;
}

2. 销毁

// 销毁
void HPDestroy(HP* p) {
    assert(p);
    if (p->arr) {
        free(p->arr);
    }
    p->arr = NULL;
    p->size = p->capacity = 0;
}

void Swap(int* x, int* y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

3. 向上调整

💡 向上调整算法 • 先将元素插入到堆的末尾，即最后一个孩子之后 • 插入之后如果堆的性质遭到破坏，将新插入结点顺着其双亲往上调整到合适位置即可

// 堆的向上调整
void AdjustUp(DataType* arr, int child) {
    int parent = (child - 1) / 2; // 父节点
    while (child > 0) { // 注意 child 可能会被调整到根节点，这时候就不能再调整了
        if (arr[child] < arr[parent]) { // 如果条件语句不成立，就说明堆已经成型
            Swap(&arr[child], &arr[parent]);
            child = parent;
            parent = (child - 1) / 2; // 循环以上步骤
        } else {
            break;
        }
    }
}

4. 堆的插入

将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。

// 插入
void HPPush(HP* p, DataType x) {
    assert(p);
    if (p->size == p->capacity) { // 判断空间是否足够
        // 扩容
        int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;
        DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1);
        }
        p->arr = tmp;
        p->capacity = NewCap;
    }
    p->arr[p->size] = x;
    AdjustUp(p->arr, p->size);
    ++p->size;
}

5. 向下调整法

💡 向下调整算法 • 将堆顶元素与堆中最后一个元素进行交换 • 删除堆中最后一个元素 • 将堆顶元素向下调整到满足堆特性为止 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

// 堆的向下调整
void AdjustDown(DataType* 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;
        }
    }
}

6. 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

// 删除，出堆顶数据
void HPPop(HP* p) {
    assert(p && p->size);
    Swap(&p->arr[0], &p->arr[p->size - 1]);
    --p->size;
    AdjustDown(p->arr, 0, p->size);
}

7. 判空

// 判空
bool HPEmpty(HP* p) {
    assert(p);
    return p->size == 0;
}

8. 返回堆顶元素

// 返回堆顶元素
DataType HPTop(HP* p) {
    assert(p && p->size);
    return p->arr[0];
}

四、完整代码

Heap.h

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

// 定义堆的结构--数组
typedef int DataType;
typedef struct Heap {// 小堆为例
    DataType *arr;
    int size;
    int capacity;
} HP;

// 初始化
void HPInit(HP* p);
// 销毁
void HPDestroy(HP* p);
// 插入
void HPPush(HP* p, DataType x);
// 删除，出堆顶数据
void HPPop(HP* p);
// 判空
bool HPEmpty(HP* p);
// 返回堆顶元素
DataType HPTop(HP* p);

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"

// 初始化
void HPInit(HP* p) {
    assert(p);
    p->arr = NULL;
    p->size = p->capacity = 0;
}

// 销毁
void HPDestroy(HP* p) {
    assert(p);
    if (p->arr) {
        free(p->arr);
    }
    p->arr = NULL;
    p->size = p->capacity = 0;
}

void Swap(int* x, int* y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

// 堆的向上调整
void AdjustUp(DataType* arr, int child) {
    int parent = (child - 1) / 2; // 父节点
    while (child > 0) { // 注意 child 可能会被调整到根节点，这时候就不能再调整了
        if (arr[child] < arr[parent]) { // 如果条件语句不成立，就说明堆已经成型
            Swap(&arr[child], &arr[parent]);
            child = parent;
            parent = (child - 1) / 2; // 循环以上步骤
        } else {
            break;
        }
    }
}

// 插入
void HPPush(HP* p, DataType x) {
    assert(p);
    if (p->size == p->capacity) { // 判断空间是否足够
        // 扩容
        int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;
        DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1);
        }
        p->arr = tmp;
        p->capacity = NewCap;
    }
    p->arr[p->size] = x;
    AdjustUp(p->arr, p->size);
    ++p->size;
}

// 堆的向下调整
void AdjustDown(DataType* 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;
        }
    }
}

// 删除，出堆顶数据
void HPPop(HP* p) {
    assert(p && p->size);
    Swap(&p->arr[0], &p->arr[p->size - 1]);
    --p->size;
    AdjustDown(p->arr, 0, p->size);
}

// 判空
bool HPEmpty(HP* p) {
    assert(p);
    return p->size == 0;
}

// 返回堆顶元素
DataType HPTop(HP* p) {
    assert(p && p->size);
    return p->arr[0];
}

main.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"

void test01() {
    HP hp;
    HPInit(&hp);
    int arr[] = { 17, 20, 10, 13, 19, 15 };
    for (int i = 0; i < 6; i++) {
        HPPush(&hp, arr[i]);
    }
    // HPPop(&hp);
    while (!HPEmpty(&hp)) {
        printf("%d-", HPTop(&hp));
        HPPop(&hp);
    }
    HPDestroy(&hp);
}

int main() {
    test01();
    return 0;
}

五、总结

通过顺序实现的方式，我们可以高效地存储和操作二叉树。堆作为一种特殊的二叉树，提供了快速的插入和删除操作，非常适合优先队列的实现。在许多应用场景中，如任务调度、图算法等，堆结构都发挥着重要作用。