一、算法

第一步：从序列中选取权重 最小 和 第二小 的元素出来。
第二步：合并第一步所选出来的元素。
  注：在算法实现上的体现：①把两个元素标记为不存在 并 生成一个新元素
              ②更新 两个元素的父亲 及 新元素的左孩子和右孩子
第三步：重复 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