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

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

题目

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

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

输出格式：
首先按照前序遍历、其次按照中序遍历，输出合并后堆的元素，格式为每个元素占一行。

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

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

代码

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

// 定义斜堆节点结构
typedef struct TreeNode *SkewHeap;
struct TreeNode {
    int key;         // 键值
    SkewHeap left;   // 左子树
    SkewHeap right;  // 右子树
};

// 创建新节点
SkewHeap CreateNode(int key) {
    SkewHeap newNode = (SkewHeap)malloc(sizeof(struct TreeNode));
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 合并两个斜堆
SkewHeap Merge(SkewHeap H1, SkewHeap H2) {
    if (H1 == NULL) return H2;
    if (H2 == NULL) return H1;
    
    // 确保H1的键值小于等于H2的键值
    if (H1->key > H2->key) {
        SkewHeap temp = H1;
        H1 = H2;
        H2 = temp;
    }
    
    // 递归合并到右子树
    H1->right = Merge(H1->right, H2);
    
    // 交换左右子树
    SkewHeap temp = H1->left;
    H1->left = H1->right;
    H1->right = temp;
    
    return H1;
}

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

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

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

int main() {
    SkewHeap 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);
    }

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

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

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

    return 0;
}