【PTA数据结构 | C语言版】左堆的合并操作

本专栏持续输出数据结构题目集，欢迎订阅。

题目

请将给定数据顺次插入初始为空的左堆，用此法建立两个左堆，再将两堆合并。为了验证结果的正确性，输出结果堆的前序和中序遍历序列。

输入格式：
输入先后给出两个堆的元素。每个堆元素输入的格式为：首先在一行中给出正整数 n（≤1000），即元素个数；随后一行给出 n 个元素的整数键值，范围不超过 int 型整数。

输出格式：
首先按照前序遍历、其次按照中序遍历，输出合并后堆的元素，格式为：每个元素占一行，以 key:npl 输出每个树结点的键值和空路径长度（即NPL）。

输入样例：
8
17 26 8 3 10 21 14 23
8
7 37 18 6 12 18 24 33

输出样例：
3:3
6:3
7:2
37:1
18:1
8:2
12:2
18:1
23:1
24:1
33:1
17:1
26:1
10:2
21:1
14:1
37:1
7:2
18:1
6:3
18:1
12:2
33:1
24:1
23:1
8:2
26:1
17:1
3:3
21:1
10:2
14:1

代码

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

// 定义左堆节点结构
typedef struct TreeNode *LeftHeap;
struct TreeNode {
    int key;        // 键值
    int npl;        // 零路径长度
    LeftHeap left;  // 左子树
    LeftHeap right; // 右子树
};

// 创建新节点
LeftHeap CreateNode(int key) {
    LeftHeap newNode = (LeftHeap)malloc(sizeof(struct TreeNode));
    newNode->key = key;
    newNode->npl = 1;  // 叶子节点的NPL为1，不是0
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 交换左右子树
void SwapChildren(LeftHeap H) {
    LeftHeap temp = H->left;
    H->left = H->right;
    H->right = temp;
}

// 合并两个左堆
LeftHeap Merge(LeftHeap H1, LeftHeap H2) {
    if (H1 == NULL) return H2;
    if (H2 == NULL) return H1;
    
    // 确保H1的键值小于等于H2的键值
    if (H1->key > H2->key) {
        LeftHeap temp = H1;
        H1 = H2;
        H2 = temp;
    }
    
    // 将H2合并到H1的右子树
    H1->right = Merge(H1->right, H2);
    
    // 确保左子树的NPL大于等于右子树的NPL
    if ((H1->left == NULL) || (H1->left->npl < H1->right->npl)) {
        SwapChildren(H1);
    }
    
    // 更新NPL值
    if (H1->right == NULL) {
        H1->npl = 1;  // 只有左子树时，NPL为1
    } else {
        H1->npl = H1->right->npl + 1;  // NPL为右子树NPL+1
    }
    
    return H1;
}

// 插入节点到左堆
LeftHeap Insert(LeftHeap H, int key) {
    LeftHeap newNode = CreateNode(key);
    return Merge(H, newNode);
}

// 前序遍历
void PreOrder(LeftHeap H) {
    if (H != NULL) {
        printf("%d:%d\n", H->key, H->npl);
        PreOrder(H->left);
        PreOrder(H->right);
    }
}

// 中序遍历
void InOrder(LeftHeap H) {
    if (H != NULL) {
        InOrder(H->left);
        printf("%d:%d\n", H->key, H->npl);
        InOrder(H->right);
    }
}

int main() {
    LeftHeap H1 = NULL, H2 = NULL;
    int n, key;
    int i;

    // 读取第一个堆的数据
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        H1 = Insert(H1, key);
    }

    // 读取第二个堆的数据
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        H2 = Insert(H2, key);
    }

    // 合并两个堆
    LeftHeap mergedHeap = Merge(H1, H2);

    // 输出前序遍历
    PreOrder(mergedHeap);

    // 输出中序遍历
    InOrder(mergedHeap);

    return 0;
}