哈夫曼树
#include <iostream>
using namespace std;
struct node {
int lchild;
int rchild;
int parent;
int weight;
};
struct hftree {
node* data;
int length;
};
hftree* inithf(int* weight, int length) {
hftree* t = new hftree;
t->data = new node[length * 2 - 1];
t->length = length;
for (int i = 0; i < length; i++) {
t->data[i].weight = weight[i];
t->data[i].lchild = -1;
t->data[i].rchild = -1;
t->data[i].parent = 0;
}
return t;
}
int* selectmin(hftree* t) {
int* min = new int[2];
int min1 = 100000000;
int min2 = 100000000;
int minindex1 = -1;
int minindex2 = -1;
for (int i = 0; i < t->length; i++) {
if (t->data[i].parent == 0) {
if (t->data[i].weight < min1) {
min2 = min1;
minindex2 = minindex1;
min1 = t->data[i].weight;
minindex1 = i;
}
else if (t->data[i].weight < min2) {
min2 = t->data[i].weight;
minindex2 = i;
}
}
}
min[0] = minindex1;
min[1] = minindex2;
return min;
}
void creathftree(hftree* t) {
int n = t->length;
for (int i = n; i < 2 * n - 1; i++) {
int* min = selectmin(t);
t->data[min[0]].parent = i;
t->data[min[1]].parent = i;
t->data[i].weight = t->data[min[1]].weight + t->data[min[0]].weight;
t->data[i].lchild = min[0];
t->data[i].rchild = min[1];
t->data[i].parent = 0;
t->length++;
}
}
void printhftree(hftree* t, int index) {
if (index != -1) {
cout << t->data[index].weight << ' ';
printhftree(t, t->data[index].lchild);
printhftree(t, t->data[index].rchild);
}
}
int main() {
int weight[7] = { 5,1,3,6,11,2,4};
hftree* t = inithf(weight, 7);
creathftree(t);
printhftree(t, t->length - 1);
return 0;
}