一、算法
第一步：从序列中选取权重 最小 和 第二小 的元素出来。
第二步：合并第一步所选出来的元素。
注：在算法实现上的体现：①把两个元素标记为不存在 并 生成一个新元素
②更新 两个元素的父亲 及 新元素的左孩子和右孩子
第三步：重复 n-1 遍上述步骤 （n 个元素需要合并 n-1 次）
二、代码（cpp）
#include <cstdio>
#include <iostream>
using namespace std;
int ans = 0;
struct node {
int weight;
int left;
int right;
int parent;
bool exist;
};
node a[1005];
void select(int n,int &k1,int &k2) {//找到最小和次小节点
int min1 = 1e9;
int min2 = 1e9;
for(int i=0;i<n;i++) {
if(a[i].exist == true) {
if(a[i].weight < min1) {
min2 = min1;
k2 = k1;
min1 = a[i].weight;
k1 = i;
} else {
if(a[i].weight < min2) {
min2 = a[i].weight;
k2 = i;
}
}
}
}
}
void createHuff(int n0) {
int n = n0;
for(int i=0;i<n0-1;i++) {
int k1,k2;
select(n,k1,k2);
a[k1].exist = false;
a[k2].exist = false;
a[k1].parent = n;
a[k2].parent = n;
a[n].exist = true;
a[n].left = k1;
a[n].right = k2;
a[n].parent = -1;
a[n].weight = a[k1].weight + a[k2].weight;
n++;
}
}
int main(void) {
int n0;
cin >> n0;
for(int i=0;i<n0;i++) {
int w;
cin >> w;
a[i].weight = w;
a[i].left = -1;
a[i].right = -1;
a[i].parent = -1;
a[i].exist = true;
}
createHuff(n0);
return 0;
}
三、参考视频
懒猫老师-哈夫曼树 https://www.bilibili.com/video/BV1MK411j7CR?t=1121
