构造一个哈夫曼树程序（设有ABCDEF，6个数据项，其出现的频度分别为654321，构造一棵哈夫曼树，）

本文目录

• 设有ABCDEF，6个数据项，其出现的频度分别为654321，构造一棵哈夫曼树，
• 求用c语言实现霍夫曼编码的程序，最好能带讲解的程序感谢！

设有ABCDEF，6个数据项，其出现的频度分别为654321，构造一棵哈夫曼树，

六个权值(频率)是 6 5 4 3 2 1
(1) 从小到大排序 1 2 3 4 5 6 (这是有序序列)
(2) 每次提取最小的两个结点,取结点1和结点2,组成新结点N3,其权值=1+2=3,
    取数值较小的结点作为左分支,1为左分支,2为右分支.
(3) 将新结点N3放入有序序列,保持从小到大排序:
    3 N3 4 5 6  (注意,新结点N3要放在结点3的后面)
(4) 重复步骤(2),提取最小的两个结点,结点3与N3组成新结点N6,其权值=3+3=6,
    结点3与N3权值一样,但是,将结点3看成较小,所以,结点3作为左分支,N3就作为右分支.
(5) 将新结点N6放入有序序列,保持从小到大排序:
    4 5 6 N6  (注意,新结点N6要放在结点6的后面)
(6) 重复步骤(2),提取最小的两个结点,结点4与结点5组成新结点N9,其权值=4+5=9,
    4的数值较小,作为左分支,5就作为右分支.
(7) 将新结点N9放入有序序列,保持从小到大排序:
    6 N6 N9
(8) 重复步骤(2),提取最小的两个结点,结点6与N6组成新结点N12,其权值=6+6=12,
    结点6作为左分支,N6就作为右分支.
(9) 将新结点N9放入有序序列,保持从小到如汪大排序:
    N9 N12
(10)重复步骤(2),提取剩下的两个结点,N9与N12组成新结点N21,其权值=9+12=21,
    数值较小的N9作为左分支,N12就作为右分支.
    有序序列已经没有结点,最后得到"哈夫曼树":
              N21
           /       \
          N9       N12            
         /  \     /   \
        4    5   6    N6
                     /  \
                    3   N3
                       /  \
                      1    2 
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N21到结点6,先经历右分支,后经历左分支,结点6的编码就是10
从根结点N21到结点5,先经历左分支,后经历右分支,结点5的编码就是01
从根结点N21到结点4,先后经历两次左分支,结点4的编码就是00
从根结枝大点N21到结点3,先经历两次右分猛橡竖支,最后经历左分支,结点3的编码就是110
从根结点N21到结点2,先后经历四次右分支,结点2的编码就是1111
从根结点N21到结点1,先经历三次右分支,最后经历左分支,结点1的编码就是1110
得出所有结点的"哈夫曼编码":
字符 A (频率6): 10
字符 B (频率5): 01
字符 C (频率4): 00
字符 D (频率3): 110
字符 E (频率2): 1111
字符 F (频率1): 1110
//C语言测试程序(来自其他网友)
//
//输入构造哈夫曼树中带权叶子结点数(n)：6
//输入6个整数作为权值：6 5 4 3 2 1
//可以得出哈夫曼树的广义表形式,以及哈夫曼编码.
#include《stdio.h》
#include《stdlib.h》
typedef int ElemType;
struct BTreeNode
{
    ElemType data;
    struct BTreeNode* left;
    struct BTreeNode* right;
};
//1、输出二叉树，可在前序遍历的基础上修改。
//   采用广义表格式，元素类型为int
void PrintBTree_int(struct BTreeNode* BT)
{
    if (BT != NULL)
    {
        printf("%d", BT-》data); //输出根结点的值
        if (BT-》left != NULL || BT-》right != NULL)
        {
            printf("(");
            PrintBTree_int(BT-》left); //输出左子树
            if (BT-》right != NULL)
                printf(",");
            PrintBTree_int(BT-》right); //输出右子树
            printf(")");
        }
    }
}
//2、根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针
struct BTreeNode* CreateHuffman(ElemType a, int n)
{
    int i, j;
    struct BTreeNode **b, *q;
    b = malloc(n*sizeof(struct BTreeNode));
    //初始化b指针数组，使每个指针元素指向a数组中对应的元素结点
    for (i = 0; i 《 n; i++)
    {
        b = malloc(sizeof(struct BTreeNode));
        b;
        b-》right = NULL;
    }
    for (i = 1; i 《 n; i++)//进行 n-1 次循环建立哈夫曼树
    {
        //k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
        int k1 = -1, k2;
        //让k1初始指向森林中第一棵树，k2指向第二棵
        for (j = 0; j 《 n; j++)
        {
            if (b != NULL && k1 == -1)
            {
                k1 = j;
                continue;
            }
            if (b != NULL)
            {
                k2 = j;
                break;
            }
        }
        //从当前森林中求出最小权值树和次最小
        for (j = k2; j 《 n; j++)
        {
            if (b != NULL)
            {
                if (b-》data)
                {
                    k2 = k1;
                    k1 = j;
                }
                else if (b-》data)
                    k2 = j;
            }
        }
        //由最小权值树和次最小权值树建立一棵新树，q指向树根结点
        q = malloc(sizeof(struct BTreeNode));
        q-》data = b-》data;
        q-》left = b;
        q-》right = b;
        b = q;//将指向新树的指针赋给b指针数组中k1位置
        b = NULL;//k2位置为空
    }
    free(b); //删除动态建立的数组b
    return q; //返回整个哈夫曼树的树根指针
}
//3、求哈夫曼树的带权路径长度
ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0
{
    if (FBT == NULL) //空树返回0
        return 0;
    else
    {
     if (FBT-》left == NULL && FBT-》right == NULL)//访问到叶子结点
     {
            printf("+ %d * %d ",FBT-》data,len);
            return FBT-》data * len;
     }
     else //访问到非叶子结点，进行递归调用，
     {    //返回左右子树的带权路径长度之和，len递增
     return WeightPathLength(FBT-》left,len+1)+WeightPathLength(FBT-》right,len+1);
     }
    }
}
//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）
void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0
{
    //定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一
    static int a;
    int i;
    //访问到叶子结点时输出其保存在数组a中的0和1序列编码
    if (FBT != NULL)
    {
        if (FBT-》left == NULL && FBT-》right == NULL)
        {
            printf("权值为%d的编码：", FBT-》data);
            for (i = 0; i 《 len; i++)
                printf("%d", a);
            printf("\n");
        }
        else //访问到非叶子结点时分别向左右子树递归调用，
        {    //并把分支上的0、1编码保存到数组a的对应元素中，
             //向下深入一层时len值增1
            a = 0;
            HuffManCoding(FBT-》left, len + 1);
            a = 1;
            HuffManCoding(FBT-》right, len + 1);
        }
    }
}
int main()
{
    int n, i;
    ElemType* a;
    struct BTreeNode* fbt;
    printf("输入构造哈夫曼树中带权叶子结点数(n)：");
    while(1)
    {
        scanf("%d", &n);
        if (n 》 1)
            break;
        else
            printf("重输n值：");
    }
    a = malloc(n*sizeof(ElemType));
    printf("输入%d个整数作为权值：", n);
    for (i = 0; i 《 n; i++)
        scanf(" %d", &a);
    fbt = CreateHuffman(a, n);
    printf("广义表形式的哈夫曼树：");
    PrintBTree_int(fbt);
    printf("\n");
    //printf("哈夫曼树的带权路径长度：\n");
    //printf("=");
    //printf("\n=%d\n", WeightPathLength(fbt, 0));
    printf("树中每个叶子结点的哈夫曼编码：\n");
    HuffManCoding(fbt, 0);
    return 0;
}

求用c语言实现霍夫曼编码的程序，最好能带讲解的程序感谢！

//* * * * * * * * * * * * * * * * * * * * * * * *
//哈夫曼树的构造哈夫曼树,哈夫曼编码 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include 《dos.h》
#include 《conio.h》
#include 《stdio.h》
#include 《stdlib.h》
#include 《string.h》
typedef struct
{unsigned int weight; //结点权值
unsigned int parent,lchild,rchild; //结点的父指针，左右孩子指针
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成一棵哈夫曼树
void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //对哈夫曼树进行编码
void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示哈夫曼编码
void Select(HuffmanTree,int,int&,int&); //在数组中寻找权值最小的两个结点
void main()
{HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
int n,i; //n是哈夫曼树叶子结点数
unsigned int *w; //w存放叶子结点权值
char j=’y’;
textbackground(3); //设定屏幕颜色
textcolor(15);
clrscr();
//程序解说
printf("本程序将演示构造哈夫曼树.\n");
printf("首先输入叶子结点数目.\n例如:8\n");
printf("然后输入每个叶子结点的权值.\n");
printf("例如:5 29 7 8 14 23 3 11\n");
printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n");
printf(" 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n");
printf(" 23---00\n 3---0111\n 11---010\n");
while(j!=’N’&&j!=’n’)
{printf("请输入叶子结点数目:");
scanf("%d",&n); //输入叶子结点数
if(n《=1) {printf("该数不合理!\n");continue;}
w=(unsigned int*)malloc(n*sizeof(unsigned int)); //开辟空间存放权值
printf("请输入各叶子结点的权值:\n");
for(i=0;i《n;i++) scanf("%d",&w); //输入各叶子结点权值
CreateHuffmanTree(HT,w,n); //生成哈夫曼树
HuffmanCoding(HT,HC,n); //进行哈夫曼编码
PrintHuffmanCode(HC,w,n); //显示哈夫曼编码
printf("哈夫曼树构造完毕，还要继续吗?(Y/N)");
scanf(" %c",&j);
}
}
void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)
{//w存放n个结点的权值，将构造一棵哈夫曼树HT
int i,m;
int s1,s2;
HuffmanTree p;
if(n《=1) return;
m=2*n-1; //n个叶子结点的哈夫曼树，有2*n-1个结点
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //开辟2*n各结点空间，0号单元不用
for(p=HT+1,i=1;i《=n;++i,++p,++w) //进行初始化
{p-》weight=*w;
p-》parent=0;
p-》lchild=0;
p-》rchild=0;
}
for(;i《=m;++i,++p)
{p-》weight=0;
p-》parent=0;
p-》lchild=0;
p-》rchild=0;
}
for(i=n+1;i《=m;++i) //建哈夫曼树
{Select(HT,i-1,s1,s2);
//从HT中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
HT.parent=i; //修改s1和s2结点的父指针parent
HT.rchild=s2; //修改i结点的左右孩子指针
HT.weight; //修改权值
}
}
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中
//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码
int i,c,f,start;
char *cd;
HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针向量
cd=(char *)malloc(n*sizeof(char)); //开辟一个求编码的工作空间
cd=’\0’; //编码结束符
for(i=1;i《=n;++i) //逐个地求哈夫曼编码
{start=n-1; //编码结束位置
for(c=i,f=HT.parent) //从叶子到根逆向求编码
if(HT=’0’; //若是左孩子编为’0’
else cd=’1’; //若是右孩子编为’1’
HC=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间
strcpy(HC); //将编码从cd复制到HC中
}
free(cd); //释放工作空间
}
void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)
{//显示有n个叶子结点的哈夫曼树的编码表
int i;
printf("HuffmanCode is :\n");
for(i=1;i《=n;i++)
{printf(" %3d---",w);
puts(HC);
}
printf("\n");
}
void Select(HuffmanTree HT,int t,int&s1,int&s2)
{//在HT中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2
int i,m,n;
m=n=10000;
for(i=1;i《=t;i++)
{if(HT.weight《n))
if(m《n)
{n=HT.weight;s2=i;}
else {m=HT.weight;s1=i;}
}
if(s1》s2) //s1放较小的序号
{i=s1;s1=s2;s2=i;}
}