数据结构：二叉树详解与堆实现

通过上述的图片我们可以比较清晰地了解该方法。

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) {
        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);
    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() {
    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 BinaryTreeDestroy(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) {
    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) {
    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 BinaryTreeDestroy(BTNode** root) {
    if (*root == NULL) return;
    BinaryTreeDestroy(&((*root)->left));
    BinaryTreeDestroy(&((*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;
}