数据结构之建哈夫曼树

数据结构建哈夫曼树

题目

给定n(n为偶数)个节点，以及节点上的权值（均为正数），建立这n个节点的哈夫曼树

字符 a b c d e f g h

频率 0.05 0.29 0.07 0.08 0.14 0.23 0.03 0.11

先来介绍下什么是哈夫曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

话不多说直接上代码

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct it
{
    char da[10];
    double fr;
    int vis;
} it;
int cmp(const void *p1, const void *p2)
{
    it *c = (it*)p1;
    it *d = (it*)p2;
    return c->fr > d->fr?1:0;
}
typedef struct BTNode
{
    char data;
    double fre;
    struct BTNode *lchild,*rchild;
} BTNode,* BITree;
int main()
{
    int n,i,j,m;
    it hash[200];
    printf("请输入个数\n");
    scanf("%d",&n);
    getchar();
    printf("请输入字符与频率\n");
    for(i=0; i<n; i++)
    {
        scanf("%s %lf",&hash[i].da,&hash[i].fr);
        getchar();
        hash[i].vis=0;
    }
    m=2*n-1;
    while(n!=m)
    {
        qsort(hash,n,sizeof(hash[0]),cmp);
        int flag=0;
        it l,r;
        for(i=0; i<n; i++)
        {
            if(hash[i].vis==0&&flag==0)
            {
                l=hash[i];
                hash[i].vis=1;
                flag++;
            }
            else if(hash[i].vis==0&&flag==1)
            {
                r=hash[i];
                hash[i].vis=1;
                flag++;
            }
            if(flag==2)break;
        }
        strcpy(hash[n].da,l.da);
        strcat(hash[n].da,"+");
        strcat(hash[n].da,r.da);
        hash[n].fr=l.fr+r.fr;
        hash[n].vis=0;
        printf("%s的频率是%lf %s的频率是%lf,一起构成了%s,频率为%lf\n",l.da,l.fr,r.da,r.fr,hash[n].da,hash[n].fr);
        n++;
    }
}

           

输入比较麻烦一点，必竟是小数，注意一点吧！

此代码仅供参考，请勿抄袭！

https://www.cnblogs.com/sench/p/7798064.html这里附上哈夫曼树的一些讲解的博客！