1020打卡

哈夫曼树

#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;
}