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