【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，不是0newNode->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大于等于右子树的NPLif ((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;
}