数据结构：二叉树基础概念与堆实现详解

孩子表示法

核心思想是每个节点的所有孩子节点用单链表存储，再用数组记录每个节点的数据和孩子链表的头指针。

typedef struct CTNode { 
    int child; // 孩子节点的数组下标 
    struct CTNode* next; // 指向下一个孩子 
} ChildPtr; 
typedef struct { 
    int data; // 数据域 
    ChildPtr* firstchild; // 孩子链表头指针 
} CTBox; 
typedef struct { 
    CTBox nodes[MAX_TREE_SIZE]; // 节点数组 
    int r, n; // 根节点位置、总节点数 
} CTree; 

• 优点：查找孩子节点高效（直接遍历链表）。
• 缺点：查找双亲节点需遍历所有节点（O(n)）。
• 适用场景：频繁查询子节点的场景（如多叉树的遍历）。

孩子双亲表示法

结合前两种方法，每个节点同时记录双亲下标和孩子链表头指针，兼顾双亲与孩子的查询效率。

其中最常用的是孩子兄弟表示法。此部分作为了解即可，在实际应用中很少使用这种复杂的树结果，像二叉树这种结构的应用相对来说更广泛。

树的应用场景

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

二叉树部分知识讲解

一、二叉树概念与结构

在树形结构中，我们最常用的是二叉树。定义为：

二叉树是由 n(n≥0) 个节点组成的有限集合，满足：空集合（空二叉树）；或由一个根节点和两棵互不相交的左子树、右子树组成，左、右子树本身也是二叉树。

基本形态有 5 种：空二叉树、仅含根节点、根节点 + 左子树、根节点 + 右子树、根节点 + 左子树 + 右子树。

补充说明：

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

二、特殊二叉树类型

特殊二叉树是在普通二叉树基础上，通过结构约束或功能特性形成的特定形态。

1. 满二叉树

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

注：判断方法：深度为 k 且节点总数为 2^k - 1 的二叉树，每一层节点数达到最大值，所有叶子节点集中在最底层。每个节点要么是叶子节点（度为 0），要么有两个子节点（度为 2），不存在度为 1 的节点。

2. 完全二叉树

对于深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。注意满二叉树是一种特殊的完全二叉树。

完全二叉树注意：

• 叶子节点仅在最后两层，且最底层叶子靠左连续排列。
• 若有度为 1 的节点，最多 1 个且仅含左孩子。
• 满二叉树是完全二叉树的特殊情况，但反之不成立。

3. 性质补充

• 若规定根结点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2^(i−1) 个结点。
• 若规定根结点的层数为 1，则深度为 h 的二叉树的最大结点数是 2^h − 1。
• 若规定根结点的层数为 1，具有 n 个结点的满二叉树的深度 h = log₂(n + 1)。

三、二叉树存储结构

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

顺序结构

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

至于为什么完全二叉树更适合使用顺序结构存储，与它的值的结构有关。为了访问到各个节点，需要将所有的节点存入数组中，但如果树中有很多的空节点，不存储任何值，我们也需要为空节点开辟空间，那样会造成空间上的浪费。

应用：现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储。需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

链式结构

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

四、堆的概念与结构

1. 实现顺序结构二叉树

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

2. 堆的概念与结构

概念：如果有一个关键码的集合 K = {k₀, k₁, k₂, ..., kₙ₋₁}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Kᵢ ≤ K₂ᵢ₊₁ 且 Kᵢ ≤ K₂ᵢ₊₂ (i = 0, 1, 2...)，则称为小堆 (或小顶堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

简单来说：大根堆的根节点值最大，小根堆的根节点值最小。堆中某个结点的值总是不大于或不小于其父结点的值；堆总是一棵完全二叉树。

性质：对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：

• 若 i > 0，i 的位置结点的双亲序号：(i - 1) / 2；i = 0，i 为根结点编号，无双亲结点。
• 若 2i + 1 < n，左孩子序号：2i + 1，2i + 1 >= n，则无左孩子。
• 若 2i + 2 < n，右孩子序号：2i + 2，2i + 2 >= n，则无右孩子。

3. 堆的实现

堆底层结构为数组，因此定义堆的结构也与顺序表相同：

typedef int type; 
typedef struct Heap { 
    type* a; 
    int size; 
    int capacity; 
} HP; 

操作方面，也与顺序表相同，不同点是，堆是有大根堆、小根堆的结构要求的，所以实现时也不是那么容易。

五、堆的实现代码部分

本次实现选取大堆为例。

1. 堆的初始化

堆的初始化是创建一个空堆并设置其初始容量、指针等基本属性的过程，通常分为大顶堆（父节点值≥子节点）和小顶堆（父节点值≤子节点）两种类型。

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

讲解：由于堆的底层是顺序表，所以初始化的实现与顺序表的实现基本一致。

2. 堆的销毁

堆的销毁函数核心目标是释放动态分配的内存，避免内存泄漏，并将堆重置为空状态，实现也与顺序表一样。

void HPDestroy(HP* h) {
    assert(h);
    if (h->a) {
        free(h->a);
    }
    h->capacity = h->size = 0;
}

3. 堆的插入数据

注意：堆的插入，是有大根堆、小根堆要求的，所以每当我们插入一个值时，都要进行堆调整。

需遵循'先插入元素，再向上调整'的核心逻辑。

至于向上调整，举例：未插入之前符合该结构的状态，插入的值如果使树不符合该结构，则需让新插入的元素'上浮'到正确位置，恢复堆的性质。

所应用的函数：

• void HPPush(HP* h, type x) // 插入函数
• void AdjustUp(type* a, int child) // 向上调整算法
• void swap(int* a, int* b) // 交换值函数

代码：（由于只有入堆会引起扩容，所以扩容代码写在了插入函数内）

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void AdjustUp(type* a, int child) {
    assert(a);
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[parent] < a[child]) {
            swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

void HPPush(HP* h, type x) {
    assert(h);
    if (h->capacity == h->size) {
        int n = h->capacity == 0 ? 4 : 2 * h->capacity;
        type* tmp = (type*)realloc(h->a, n * sizeof(type));
        if (tmp == NULL) {
            perror("realloc failed");
            return;
        }
        h->a = tmp;
        h->capacity = n;
    }
    h->a[h->size++] = x;
    AdjustUp(h->a, h->size - 1);
}

讲解：堆的插入操作实现，包含 swap（交换）、AdjustUp（向上调整）和 HPPush（堆插入）三个函数，核心是通过'扩容→插入→调整'维持堆的性质（以大顶堆为例）。

4. 堆打印值

堆打印值实际上与顺序表的值的打印一样，只是结果是按照堆的值的顺序。

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

六、现有的堆代码的测试

接下来展示完整代码部分，本代码分三个文件完成：

heap.h

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

typedef int type;
typedef struct Heap {
    type* a;
    int size;
    int capacity;
} HP;

void HPInit(HP* h);
void HPDestroy(HP* h);
void HPPush(HP* h, type x);
void AdjustUp(type* a, int child);
void swap(int* a, int* b);
void HPPrint(HP* h);

heap.c

#include"heap.h"

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

void HPDestroy(HP* h) {
    assert(h);
    if (h->a) {
        free(h->a);
    }
    h->capacity = h->size = 0;
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void AdjustUp(type* a, int child) {
    assert(a);
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[parent] < a[child]) {
            swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

void HPPush(HP* h, type x) {
    assert(h);
    if (h->capacity == h->size) {
        int n = h->capacity == 0 ? 4 : 2 * h->capacity;
        type* tmp = (type*)realloc(h->a, n * sizeof(type));
        if (tmp == NULL) {
            perror("realloc failed");
            return;
        }
        h->a = tmp;
        h->capacity = n;
    }
    h->a[h->size++] = x;
    AdjustUp(h->a, h->size - 1);
}

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

main.c

#include"heap.h"

void test() {
    HP h;
    HPInit(&h);
    HPPush(&h, 10); // 10
    HPPush(&h, 20); // 20 10
    HPPush(&h, 6);  // 20 10 6
    HPPrint(&h);
    HPPush(&h, 30); // 30 20 6 10
    HPPrint(&h);
    HPPush(&h, 60); // 60 30 6 10 20
    HPPrint(&h);
    HPDestroy(&h);
}

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

测试结果验证了堆的插入和调整逻辑是正确的，大根堆的根节点始终为最大值。