哈夫曼樹中節(jié)點(diǎn)的結(jié)構(gòu)體定義

/*
哈夫曼樹中每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)體
x:存放出現(xiàn)的概率
flag:標(biāo)志當(dāng)前節(jié)點(diǎn)是否有需要編碼
data:存放當(dāng)前數(shù)據(jù)
lchild:指向左孩子的指針
rchild:指向右孩子的指針
*/
struct Node
{
    float x;   //存放概率
    int flag;  //標(biāo)志當(dāng)前節(jié)點(diǎn)是否有對應(yīng)的數(shù)據(jù)
    char data; //存放數(shù)據(jù)
    Node *lchild;
    Node *rchild;
};

原理比較簡單，代碼中全部有注釋姿搜，應(yīng)該都可以看懂

PS:以下代碼在VScode中配合gdb調(diào)試工具能夠正常運(yùn)行，如果使用其他編譯器或者IDE可能需要做出修改候齿。

#include <stdio.h>
#include <stdlib.h>
#define N 10


/*
receive:將用戶輸入的信息錄入到數(shù)組中
input: 需要編碼的元素個(gè)數(shù)number
       用于存儲的數(shù)組data[]
*/
void receive(Node *data[], int number)
{
    char no;
    for (int i = 0; i < number; i++)
    {
        scanf("%c", &no); //消除輸入過程中的回車
        data[i] = (Node *)malloc(sizeof(Node));
        printf("Please input %dth data:", i);
        scanf("%c", &data[i]->data);
        printf("Rate:");
        scanf("%f", &data[i]->x);
        data[i]->flag = 1;
        data[i]->lchild = data[i]->rchild = NULL;
    }
}

/*
creat:根據(jù)存儲信息的數(shù)組創(chuàng)建哈夫曼樹
input: 存儲信息的數(shù)組data[]
       元素的個(gè)數(shù)number
return: 哈夫曼樹的根節(jié)點(diǎn)root
*/
Node *creat(Node *data[], int number)
{
    Node *temp;
    /*循環(huán)number-1次迄靠，創(chuàng)建哈夫曼樹*/
    for (int m = 1; m < number; m++)
    {
        int first = -1;
        int second = -1;
        /*first 指向第一個(gè)非NULL元素，second指向第二個(gè)非NULL元素*/
        for (int i = 0; i < number; i++)
        {
            if (first == -1 && data[i] != NULL)
            {
                first = i;
                continue;
            }
            if (second == -1 && data[i] != NULL)
            {
                second = i;
                continue;
            }
        }
        if (first != -1 && second != -1)
        {
            /*確保first是最小的卓缰，second是第二小的*/
            if (data[first]->x > data[second]->x)
            {
                float temp = first;
                first = second;
                second = temp;
            }
            /*尋找出森林中概率最小的兩個(gè)結(jié)點(diǎn)*/
            for (int j = 0; j < number; j++)
            {
                /*如果小于最小的元素计呈，則first和second都需要更新*/
                if (data[j] != NULL && data[j]->x < data[first]->x)
                {
                    second = first;
                    first = j;
                }
                /*如果只小于第二小的元素砰诵，則只更新second的位置*/
                else if (data[j] != NULL && j != first && data[j]->x < data[second]->x)
                {
                    second = j;
                }
            }
            /*利用最小的兩個(gè)節(jié)點(diǎn)構(gòu)建一個(gè)樹，并將此放入森林中*/
            temp = (Node *)malloc(sizeof(Node));
            temp->x = data[first]->x + data[first]->x;
            temp->lchild = data[first];
            temp->rchild = data[second];
            temp->flag = 0;   //合成節(jié)點(diǎn)并不需要編碼
            data[first] = temp;
            data[second] = NULL;
        }
    }
    return temp;
}
/*
show:顯示哈夫曼樹
input:哈夫曼樹的根節(jié)點(diǎn)root
*/
void show(Node *root)
{
    if (root != NULL)
    {
        if (root->flag == 1)
        {
            printf("%c", root->data);
        }
        if (root->lchild != NULL)
        {
            printf("(");
            show(root->lchild);
            if (root->rchild != NULL)
            {
                printf(",");
                show(root->rchild);
            }
            printf(")");
        }
    }
}
/*
HuffManCoding:給哈夫曼樹編碼
input: 哈夫曼樹的根節(jié)點(diǎn)root
       編碼的層次i
*/
void HuffManCoding(Node *root, int i)
{
    static int a[N];
    if (root->flag == 1)
    {
        printf("After coding %c is :", root->data);
        for (int j = 0; j < i; j++)
        {
            printf("%d", a[j]);
        }
        printf("\n");
    }
    else
    {
        /*左邊的編碼為0捌显，右邊編碼為1*/
        a[i] = 0;
        HuffManCoding(root->lchild, i + 1);
        a[i] = 1;
        HuffManCoding(root->rchild, i + 1);
    }
}

int main()
{
    int number;
    Node *data[N];
    Node *root;
    printf("Please input the number of data:");
    scanf("%d", &number);
    receive(data, number);
    root = creat(data, number);
    show(root);
    printf("\n");
    HuffManCoding(root,0);
    system("pause");
    return 0;
}