数据结构精讲：树 → 二叉树 → 堆从入门到实战

2401_89021466

516人浏览 · 2026-04-21 14:55:59

2401_89021466 · 2026-04-21 14:55:59 发布

数据结构精讲：树 → 二叉树 → 堆从入门到实战

一、树：一切树形结构的基础

1.1 树的概念与结构

树是由 n(n≥0) 个有限节点组成的非线性层次结构，形态像一棵根朝上、叶朝下的倒挂树。

核心规则

有且仅有一个根节点，无双亲。
其余节点分为互不相交的子树，子树也是树。
N 个节点 ⇔ N-1 条边。
除根外，每个节点仅有一个父节点。

1.2 树的常用术语

节点的度：孩子个数
树的度：所有节点度的最大值
叶子节点：度为 0 的节点
兄弟节点：同一个父节点的节点
高度/深度：节点最大层次数
森林：多棵互不相交的树的集合

1.3 孩子兄弟表示法（C 语言完整实现）

// 孩子兄弟表示法：通用树结构
struct TreeNode
{
    int data;               // 数据域
    struct TreeNode* firstChild;  // 指向第一个孩子
    struct TreeNode* nextBrother; // 指向右兄弟
};

✅ 作用：可将任意树转为二叉树存储，是树与二叉树的桥梁。

二、二叉树：最常用的树形结构

2.1 二叉树基本概念

二叉树是每个节点最多有两个子树的有序树，左子树、右子树严格区分，不能颠倒。

特点

节点度 ≤ 2
是有序树
递归定义：根 + 左子树 + 右子树

2.2 两种特殊二叉树

满二叉树
每一层节点数都达到最大值。
节点总数：2ʰ - 1（h 为高度）
完全二叉树
除最后一层外，其他层满节点；最后一层节点靠左连续排列。
✅ 满二叉树是特殊的完全二叉树。

2.3 二叉树重要性质

第 i 层最多有 2ⁱ⁻¹ 个节点
高度 h，最多 2ʰ - 1 个节点
n₀ = n₂ + 1（叶子节点数 = 度2节点数 + 1）
完全二叉树高度：h = ⌊log₂n⌋ + 1

2.4 二叉树存储结构

（1）顺序存储（数组）

适合完全二叉树，否则空间浪费大。
常用于堆的实现。

（2）链式存储（二叉链）

// 二叉树链式节点定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;   // 左孩子
    struct BinaryTreeNode* right;  // 右孩子
} BTNode;

2.5 二叉树遍历（递归版完整代码）

// 前序遍历：根 → 左 → 右
void PreOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }
    printf("%d ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

// 中序遍历：左 → 根 → 右
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

// 后序遍历：左 → 右 → 根
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

三、堆：完全二叉树的经典应用

堆是用数组实现的完全二叉树，满足堆序性质。

3.1 堆的核心概念

大根堆：父节点 ≥ 孩子节点，堆顶最大
小根堆：父节点 ≤ 孩子节点，堆顶最小

下标公式

双亲：(i - 1) / 2
左孩子：2 * i + 1
右孩子：2 * i + 2

3.2 堆结构定义

typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    int size;       // 当前元素个数
    int capacity;   // 容量
} HP;

3.3 向上调整（插入用）

// 向上调整（大堆）
void AdjustUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] > a[parent])
        {
            // 交换
            HPDataType tmp = a[child];
            a[child] = a[parent];
            a[parent] = tmp;

            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

3.4 向下调整（删除/建堆用）

// 向下调整（大堆）
void AdjustDown(HPDataType* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        // 取较大孩子
        if (child + 1 < n && a[child + 1] > a[child])
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            HPDataType tmp = a[child];
            a[child] = a[parent];
            a[parent] = tmp;

            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

3.5 堆插入、删除（完整代码）

// 堆插入
void HPPush(HP* php, HPDataType x)
{
    assert(php);
    // 扩容
    if (php->size == php->capacity)
    {
        int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        php->a = tmp;
        php->capacity = newCapacity;
    }
    php->a[php->size++] = x;
    AdjustUp(php->a, php->size - 1);
}

// 堆删除（删堆顶）
void HPPop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    // 交换堆顶与最后一个元素
    HPDataType tmp = php->a[0];
    php->a[0] = php->a[php->size - 1];
    php->a[php->size - 1] = tmp;

    php->size--;
    AdjustDown(php->a, php->size, 0);
}