构造哈夫曼树并求带权路径长度（c语言/CodeBlocks实现）
#include <iostream>
#include <>
#include <>
#include <>
#include <algorithm>
using namespace std;
int w[100], n, wpl = 0;
typedef struct node{
int data;
struct node *l, *r;
}HfmNode;
void CreateHfmTree(int *w, int n)
{
int i, j;
HfmNode *b[100], *p;
for(i = 0; i < n; i++){ //构造n棵仅有一个根节点的树b[i]
b[i] = (HfmNode *)malloc(sizeof(HfmNode*));
b[i]->data = w[i];
b[i]->l = NULL;
b[i]->r = NULL;
}
for(i = 0; i < n - 1; i++){ //注意这里是n-1次循环，即最后得到的根节点不用再循环一次了
int k1 = -1, k2; //k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
for(j = 0; j < n; j++){ //让k1初始指向森林中第一棵树，k2指向第二棵;b[j]=NULL表示删除另外这棵树
if(b[j] != NULL && k1 == -1){//至于为什么要让k1=-1，只是个标志而已，为了让k1指向第一个非空结点
k1 = j;
continue;
}
if(b[j] != NULL){
k2 = j;
break;
}
}
for(j = k2; j < n; j++){ //从当前森林中求出最小权值树和次最小
if(b[j] != NULL){
if(b[j]->data < b[k1]->data){
k2 = k1;
k1 = j;
}
else if(b[j]->data < b[k2]->data)
k2 = j;
}
}
p = (HfmNode *)malloc(sizeof(HfmNode*));
p->data = b[k1]->data + b[k2]->data;
wpl += p->data; //求带权路径长
p->l = b[k1];
p->r = b[k2];
b[k1] = p; //添加p这棵树到b[k1]
b[k2] = NULL; //删除b[k2]这棵树
}
free(b);
return;
//return p; 可返回整棵树的根指针
};
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &w[i]);
CreateHfmTree(w, n);
printf("%d\n", wpl);
return 0;
}