数据结构：哈夫曼树

￡神魔★判官ぃ 2022-05-30 03:49 186阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    struct BTreeNode {
        int data;
        struct BTreeNode* left;
        struct BTreeNode* right;
    };
    
    struct BTreeNode* createHuffman (int a[], int n) {//根据数组a中n个权值建立一颗哈弗曼树，返回树根指针
        int i, j;
        struct BTreeNode *b[n], *q;
        //b = (struct BTreeNode **)malloc(n * sizeof(struct BTreeNode));
        for (i=0; i<n; i++) {//初始化b指针数组，使每个指针元素指向a数组中对应的元素节点
            b[i] = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
            b[i] -> data = a[i];
            b[i] -> left = b[i] -> right = NULL;
        }
        for (i=1; i<n; i++) {//进行n-1次循环建立哈弗曼树
            int k1 = -1, k2;//k1表示森林中具有最小权值的树根节点的下标，k2为次最小的下标
            for (j=0; j<n; j++) {//让k1初始指向森林中第一颗树,k2指向第二颗
                if (b[j] != NULL && k1 == -1) {
                    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;
                    }
                }
            }
            //由最小权值树和次最小权值树建立一颗新树
            q = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
            q -> data = b[k1] -> data + b[k2] -> data;
            q -> left = b[k1];
            q -> right = b[k2];
    
            b[k1] = q;
            b[k2] = NULL;
        }
        free(b);
        return q;
    }
    
    void printBTree(struct BTreeNode* node) {
        if (node != NULL) {
            printf("%d", node -> data);
            if (node -> left != NULL || node -> right != NULL) {
                printf("(");
                printBTree(node -> left);
                if (node -> right != NULL) {
                    printf(",");
                }
                printBTree(node -> right);
                printf(")");
            }
        }
    }
    
    int WPL (struct BTreeNode* root, int len) {
        if (root == NULL) {
            return 0;
        }
        else {
            if (root -> left == NULL && root -> right == NULL) {
                return root -> data * len;
            }
            else {
                return WPL(root -> left, len + 1) + WPL(root -> right, len + 1);
            }
        }
    }
    
    void huffmanCoding (struct BTreeNode* root, int len) {
        static int a[10];
        if (root != NULL) {
            if (root -> left == NULL && root -> right == NULL) {
                int i;
                printf("节点权值为%d的编码:", root -> data);
                for (i=0; i<len; i++) {
                    printf("%d", a[i]);
                }
                printf("\n");
            }
            else {
                a[len] = 0;
                huffmanCoding(root -> left, len + 1);
                a[len] = 1;
                huffmanCoding(root -> right, len + 1);
            }
        }
    }
    
    int main (int argc, char **argv) {
        int n, i;
        int *a;
        struct BTreeNode* root;
        printf("从键盘输入待构造的哈弗曼树中带权叶子节点数n:");
        while (1) {
            scanf("%d", &n);
            if (n > 1) {
                break;
            }
            else {
                printf("重输n值:");
            }
        }
        a = (int *)malloc(n * sizeof(int));
        printf("输入%d个整数作为权值:", n);
        for (i=0; i<n; i++) {
            scanf("%d", &a[i]);
        }
        root = createHuffman(a, n);
        printBTree(root);
        printf("\n");
        printf("%d", WPL(root, 0));
        printf("\n");
        huffmanCoding(root, 0);
        return 0;
    }

![20180304144359513][]

[20180304144359513]: /images/20220530/e472a3279cc9421da54d8d1e798e96d8.png