数据结构核心：二叉树、堆与遍历算法实现

1. 树

树是一种非线性的数据结构，由 n 个有限结点组成一个具有层次关系的集合。之所以称为树，是因为它看起来像一棵倒挂的树。

• 根结点：有一个特殊的结点，没有前驱结点。
• 子树：除了根结点之外，其余结点被分为 M 个互不相交的集合，每一个集合又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或者多个后继。因此，树是递归定义的。
• 结构约束：树形结构中，子树之间不能有交集，否则就不是树形结构。

1.1 基本概念

• 父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点。
• 子结点/孩子结点：一个结点含有的子树的根结点称为该结点的子结点。
• 结点的度：有几个孩子，就为几度。
• 树的度：最大结点的度即为树的度。
• 叶子结点/终端结点：度为 0 的结点。
• 分支结点/非终端结点：度不为 0 的结点。
• 兄弟结点：具有相同的父结点。
• 结点的层次：从根开始定义，根为第一层，根的孩子为第二层……
• 树的高度/深度：树中结点的最大层次。
• 结点的祖先：从根结点到该结点所经分支上的所有结点。
• 路径：一条从树中任意节点出发，沿父节点 - 子节点连接，达到任意节点的序列。
• 子孙：以某结点为根的 subtree 中任一结点都称为该结点的子孙。
• 森林：由多棵互不相交的树组成的集合。

1.2 树的表示

常用的一种表示方法是孩子兄弟表示法（Left-Child Right-Sibling Representation）：

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

通过这种结构，可以将任意树转换为二叉树形式，便于计算机处理。

1.3 应用

文件系统是树形结构的典型应用场景。它利用树形结构来组织和管理文件和文件夹，通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。

2. 二叉树

2.1 概念与结构

二叉树是树形结构的一种特例。一棵二叉树是结点的一个有限集合，该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成。

二叉树的特点：

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

2.2 特殊的二叉树

2.2.1 满二叉树

每一层的结点都达到最大值，则这个二叉树就是满二叉树。结点的总数就是 $2^k - 1$。

2.2.2 完全二叉树

完全二叉树是效率很高的数据结构，是由满二叉树引申出来的。需要注意的是，满二叉树是一种特殊的完全二叉树。

特点：假设二叉树的层次为 K 层，则除了第 K 层外，每层结点的个数达到最大结点数，第 K 层不一定达到最大结点数。且完全二叉树结点的顺序是从左到右顺序放置的。

2.3 二叉树的存储结构

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

2.3.1 顺序结构

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

2.3.2 链式结构

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

3. 实现顺序结构二叉树（堆）

堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。

3.1 堆的概念与结构

分为小根堆和大根堆。

堆具有以下性质：

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

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

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

3.2 堆的实现

3.2.1 堆的初始化与销毁

初始化与销毁逻辑较为常规，此处不再赘述，重点聚焦核心操作。

3.2.2 堆数据的插入

由于插入的数据是随机的，我们不确定插入数据的大小，而大堆和小堆之间的数据的顺序是有一定规律的，因此，我们要通过适当的方法来进行插入。这里采用堆的向上调整方法。

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

void AdjustUp(HPDataType* arr, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) { // 不需要等于 0，child 只要走到了根结点的位置，根结点不需要交换了
        if (arr[child] < arr[parent]) {
            Swap(&arr[child], &arr[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

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

3.2.3 堆数据的删除

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

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;
        }
    }
}

void HPPop(HP* php) {
    assert(php && php->size);
    Swap(&php->arr[0], &php->arr[php->size - 1]);
    --php->size;
    AdjustDown(php->arr, 0, php->size);
}

3.3 堆的应用---TOP-K 问题

TOP-K 问题：即求数据集合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。

当数据量太大的时候，就不能用排序的方法，这时，我们可以用堆来解决问题。

思路：拿 K 个数据来建堆，然后让取到的数据分别与原始的 K 个数据进行比较，最后所得即为所求。时间复杂度为 O(N)，空间复杂度为 O(K)。根据上述的分析可得，找最小的 K 个数据，建大堆；找最大的 K 个数据，建小堆。

代码实现如下：

void CreateNDate() {
    // 造数据
    int n = 100000;
    srand(time(0));
    const char* file = "data.txt";
    FILE* fin = fopen(file, "w");
    if (fin == NULL) {
        perror("fopen error");
        return;
    }
    for (int i = 0; i < n; i++) {
        int x = (rand() + i) % 1000000;
        fprintf(fin, "%d\n", x);
    }
    fclose(fin);
}

void TOPK() {
    int k = 0;
    printf("请输入 K:");
    scanf("%d", &k);
    // 从文件中读取前 K 个数据
    const char* file = "data.txt";
    FILE* fout = fopen(file, "r");
    if (fout == NULL) {
        perror("fopen fail!");
        exit(1);
    }
    int* minHeap = (int*)malloc(k * sizeof(int));
    if (minHeap == NULL) {
        perror("malloc fail!");
        exit(0);
    }
    for (int i = 0; i < k; i++) {
        fscanf(fout, "%d", &minHeap[i]);
    }
    // 建堆
    for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(minHeap, i, k);
    }
    int x = 0;
    while (fscanf(fout, "%d", &x) != EOF) {
        if (x > minHeap[0]) {
            minHeap[0] = x;
            AdjustDown(minHeap, 0, k);
        }
    }
    for (int i = 0; i < k; i++) {
        printf("%d ", minHeap[i]);
    }
    fclose(fout);
}

int main() {
    // test01();
    CreateNDate();
    TOPK();
    return 0;
}

4. 实现链式结构二叉树

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

一般来说，我们用的是二叉链表的结构来实现的。

4.1 前中后序遍历

1. 前序遍历 (Preorder Traversal)：访问根结点的操作发生在遍历其左右子树之前。访问顺序为：根结点、左子树、右子树。
2. 中序遍历 (Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）。访问顺序为：左子树、根结点、右子树。
3. 后序遍历 (Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后。访问顺序为：左子树、右子树、根结点。

4.1.1 前序遍历

void PreOrder(BTNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

这本质上利用了递归的特性，具体执行路径可结合图示理解。

4.1.2 中序遍历

// 中序
void InOrder(BTNode* root) {
    if (root == NULL) {
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

4.1.3 后序遍历

// 后序
void PostOrder(BTNode* root) {
    if (root == NULL) {
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

4.2 结点个数以及高度等

实现下列问题：

// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第 k 层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
// 二叉树查找值为 x 的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

相关逻辑均基于递归思想，以下直接展示代码。

// 二叉树结点个数
int BinaryTreeSize(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    return (1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right));
}

// 二叉树叶子结点个数，即没有孩子结点的个数
int BinaryTreeLeafSize(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// 二叉树第 k 层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k) {
    // 思路：左子树第 K 层结点的个数 + 右子树第 K 层结点的个数
    if (root == NULL) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

// 二叉树的深度/高度（即层数）
int BinaryTreeDepth(BTNode* root) {
    // 1 + 左 + 右
    if (root == NULL) {
        return 0;
    }
    int leftdep = BinaryTreeDepth(root->left);
    int rightdep = BinaryTreeDepth(root->right);
    return leftdep > rightdep ? leftdep + 1 : rightdep + 1;
}

// 二叉树查找值为 x 的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
    if (root == NULL) {
        return NULL;
    }
    if (root->data == x) {
        return root;
    }
    BTNode* leftFind = BinaryTreeFind(root->left, x);
    if (leftFind) {
        return leftFind;
    }
    BTNode* rightFind = BinaryTreeFind(root->right, x);
    if (rightFind) {
        return rightFind;
    }
    return NULL;
}

// 二叉树销毁
void BinaryTreeDestory(BTNode** root) {
    // 先左后右，最后根结点
    if (*root == NULL) return;
    BinaryTreeDestory(&((*root)->left));
    BinaryTreeDestory(&((*root)->right));
    free(*root);
    *root = NULL; // 修复原代码中的赋值错误
}

4.3 层序遍历

设二叉树的根结点所在层数为 1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第 2 层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

我们借助队列来解决（先进先出）。

// 层序遍历
void LevelOrder(BTNode* root) {
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q)) {
        BTNode* top = QueueFront(&q);
        printf("%d ", top->data);
        // 出队
        QueuePop(&q);
        if (top->left) {
            QueuePush(&q, top->left);
        }
        if (top->right) {
            QueuePush(&q, top->right);
        }
    }
    QueueDestroy(&q);
}

4.4 判断是否为完全二叉树

涉及到层，所以我们还采用队列的方法来进行运算。

bool BinaryTreeComplete(BTNode* root) {
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q)) {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL) break;
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while (!QueueEmpty(&q)) {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front != NULL) {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}