求助有关哈夫曼树的问题！急！满意的答案再加!

一道哈夫曼树笔试题!~

最小哈夫曼树如图，带权路径WPL=1078

在你没有任何成就之前就放下所谓的面子，越是自己感觉到不赶的事情 你就必须得去做 没事的 人与人之前就是要多沟通才好 你不要老是被动的 应当主动的多在陌生的场合试着和别人交流。不要有怕的感觉

哈夫曼树
一、 基本术语
1. 路径与路径长度
若在一棵树中存在一个结点序列 k1, k2, …., kj ，使得kj是kj+1的双亲（1<=i<j），则称结点序列是从k1到kj 的路径（如树中的某个结点到它的某个祖先，或者到它的某个后代的的包括它本身的一系列按顺序的结点序列称为路径），因树中的每个结点只有一个双亲结点，所以这是两个结点间的唯一路径，从k1到kj 所经过的分支数称为这两点之间的路径长度。它等于结点数-1。
如： 从结点A到结点J的结点序
列为A，B，E，J。
路径长度为3。

8 10

4 5 3
2. 结点的权和带权路径长度
如果根据需要给树中的结点赋予一个有某中意义的实数，则称此实数为该结点的权，结点带权路径长度规定为从树根结点到该结点之间的路径长度乘上该结点的权值所得到的乘积。
3. 树的带权路径长度
树的带权路径长度定义为树中所有叶结点的带权路径长度之和，通常记为：
n
WPL=∑ wili wi和li 分别代表叶结点ki的权值和ki到
i=1 根结点的路径长度
例如：上图的WPL=（4+5+3）*3+（8+10）*2=72
4. 哈夫曼树
哈夫曼树又称为最优二叉树，它是由n个带权叶结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
例如：有四个叶结点a，b，c，d，分别带权为9，4，5，2，可以构成三棵不同的二叉树（当然可以构成更多的二叉树）见下图：

9 4 5 2 WPL=（9+4+5+2）*2=40

4

2

5 9
WPL=（9+5）*3+2*2+4*1=50

4

2

5 9
WPL=（9+5）*3+2*2+4*1=50

9

5

4 2
WPL=9*1+5*2+（2+4）*3=37
可以证明最后一棵二叉树是哈夫曼树。
二、 构造哈夫曼树
1. 将n个叶结点构成独立的n棵二叉树，每棵二叉树只有一个根结点。
2. 选择两棵权值最小的二叉树合并成一棵二叉树，并以这两棵二叉树的权值之和作为这棵二叉树的权值，取消原来的两棵二叉树。
3. 重复2，知道只剩一棵二叉树为止。
例如：有6个带权叶结点的权值分别为：3，6，8，5，2，2，构造一棵哈夫曼树，并计算WPL的结果。
1.构造6棵二叉树

3 6 8 5 2 2
2选出两个权值最小的二叉树的组成一棵二叉树

2 2 合并权值为4

3 6 8 5
3 6 8 5 4
2 2
选出两个权值最小的二叉树的组成一棵二叉树

7 6 8 5

3

2 2
选出两个权值最小的二叉树的组成一棵二叉树

7 11 8

3
5 6
2 2
选出两个权值最小的二叉树的组成一棵二叉树

15 11

8
5 6
3

2 2

选出两个权值最小的二叉树的组成一棵二叉树（最终的哈夫曼树）

8
5 6
3

2 2
WPL=（2+2）*4+3*3+（5+6+8）*2=16+9+38=63
作业：P221/9

路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1～kj所经过的分支数称为这两结点间的路径长度。

结点的权和带权路径长度
在许多应用中，常为树中的结点赋上一有意义的实数，该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度

n

基本术语

路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1～kj所经过的分支数称为这两结点间的路径长度。

结点的权和带权路径长度
在许多应用中，常为树中的结点赋上一有意义的实数，该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度

n

树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为WPL= ∑ wili

i=1

哈夫曼树

哈夫曼(Huffman)树又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
构造哈夫曼树

构造算法如下：
(1) 根据与n个权值{w1,w2…wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2…Tn},其中第i棵二叉树Ti(1 ≤ i ≤ n)都只有一个权值为wi的根结点，其左、右子树均为空
(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和
(3) 从F中删除构成新树的那两棵，同时把新树加入F中
(4) 重复第(2)和第(3)步，直到F中只含有一棵为止，此树便为哈夫曼树
哈夫曼编码

等长编码缺点：使传送电文总长度很长

不等长编码缺点：译码的二义性或多义性

前缀编码：对某一字符集进行不等长编码时，任一字符编码都不是其它字符编码的前缀

哈夫曼编码：由编码哈夫曼树所得到的字符编码(由编码哈夫曼树所得到的字符编码)
例：在一电文中，六个字符A,B,C,D,E,F的出现频率依次为4，2，6，8，3，2,如图(a)

由此构造的哈夫曼编码树如图(b)所示

A、B、C、D、E、F的哈夫曼编码依次为：00、1010、01、11、100、1011
电文的最短传送长度L=WPL=4×2+2×4+6×2+8×2+3×3+2×4=61

既然这么急，就说是用什么语言啊，C/C++、Basic...
还有，英文词典里的单词统计前，是读带单词表的文件，还是自定义初始化赋值就可以了呢！
你说要用C，我用的是Turbo C 2 编译的，怎么不是C＋＋呢，我可是从百忙中啊！
其中假设英语词典以单词表形式保存在C:\word.txt中，且每一行一个单词。
代码如下：
-----------------------------------------------------------
/*
HuffmanCode BY TC 2
Author: ejau
Ver 1.00
Data:19/05/2006
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>

typedef struct {
float weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;

typedef char **HuffmanCode;

typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;

void Error(char *message);
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,float *kt,unsigned int n);
MinCode Select(HuffmanTree HT,unsigned int n);

void main()
{
HuffmanTree T=NULL;
HuffmanCode HC=NULL;
unsigned int *w=NULL;
unsigned int i,n=26;
printf("Default Input n = %d\n",n);
w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *));
float *kt=(float *)malloc((n+1)*sizeof(float *));
kt[0]=0;

for(i=0;i<=n;i++)
w[i] = 0;
char * count;
FILE * file1;
char filen[30] = "C:\\word.txt";
if((file1 = fopen(filen,"r"))==NULL)
{
printf("File Read Error!\n");
exit(0);
}
while(fscanf(file1,"%s",count)!=EOF)
{
int temp;
if(countofpoint[0]>='a'&&count[0]<='z')
temp = (int)count[0]-96;
if(countofpoint[0]>='A'&&count[0]<='Z')
temp = (int)count[0]-64;
w[temp]++;
}
fclose(file1);

int tatolnum=0;
for(i=0;i<=n;i++)
tatolnum=tatolnum+w[i];
for(i=1;i<=n;i++)
kt[i]=(float *)w[i]/tatolnum;
HC=HuffmanCoding(HT,HC,kt,n);
printf("HuffmanCode:\n");
printf("Letter\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%c\t\t%f\t\t%s\n",i+64,kt[i],HC[i]);
}

void Error(char *message)
{
fprintf(stderr,"Error:%s\n",message);
exit(1);
}

HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,float *kt,unsigned int n)
{
unsigned int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
unsigned int f,c,start,m;
MinCode min;
if(n<=1) Error("Code too small!");
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=0;i<=n;i++,p++,kt++)
{
p->weight=*kt;
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++)
{
min=Select(HT,i-1);
s1=min.s1;
s2=min.s2;
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
printf("HT List:\n");
printf("Letter\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(i=1;i<=m;i++)
printf("%c\t\t%f\t\t%d\t\t%d\t\t%d\n",i+64,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char *));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char *));
strcpy(HC[i],&cd[start]);
}
free(cd);
return HC;
}

MinCode Select(HuffmanTree HT,unsigned int n)
{
float min,secmin;
unsigned int temp;
unsigned int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}

基本术语

路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1～kj所经过的分支数称为这两结点间的路径长度。

结点的权和带权路径长度
在许多应用中，常为树中的结点赋上一有意义的实数，该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度

n

树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为WPL= ∑ wili

i=1

哈夫曼树

哈夫曼(Huffman)树又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
构造哈夫曼树

构造算法如下：
(1) 根据与n个权值{w1,w2…wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2…Tn},其中第i棵二叉树Ti(1 ≤ i ≤ n)都只有一个权值为wi的根结点，其左、右子树均为空
(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和
(3) 从F中删除构成新树的那两棵，同时把新树加入F中
(4) 重复第(2)和第(3)步，直到F中只含有一棵为止，此树便为哈夫曼树
哈夫曼编码

等长编码缺点：使传送电文总长度很长

不等长编码缺点：译码的二义性或多义性

前缀编码：对某一字符集进行不等长编码时，任一字符编码都不是其它字符编码的前缀

哈夫曼编码：由编码哈夫曼树所得到的字符编码(由编码哈夫曼树所得到的字符编码)
例：在一电文中，六个字符A,B,C,D,E,F的出现频率依次为4，2，6，8，3，2,如图(a)

由此构造的哈夫曼编码树如图(b)所示

A、B、C、D、E、F的哈夫曼编码依次为：00、1010、01、11、100、1011
电文的最短传送长度L=WPL=4×2+2×4+6×2+8×2+3×3+2×4=61

---

延津县15890974645： 哈夫曼树问题 - ？
臾珠接骨：[答案] 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree).

延津县15890974645： 关于哈夫曼树的问题由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为多少? - ？
臾珠接骨：[答案] 哈夫曼树如下: (24) (10) (14) (5) 5 6 8 2 3 带权路径长度为 2*3 + 3*3 +5*2 +6*2 +8*2 = 53

延津县15890974645： 有关构造哈夫曼树的问题 - ？
臾珠接骨： 1. 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn},其中每棵二叉树Ti中只有一个带权wi的根结点,左右子树均空. 2. 在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值...

延津县15890974645： 数据结构中哈夫曼树的问题用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是? - ？
臾珠接骨：[答案] 哈夫曼树为: 15 / \ 6 9 / \ / \ 3 【3】【4】 【5】 / \ 【1】 【2】 树的带权路径长度为树中所有叶子结点的带权路径长度之和,而结点的带权路径长度为结点到根节点之间的路径长度与该节点上权的乘积. WPL=3*(1+2)+2*3+2*(4+5)=33

延津县15890974645： 关于哈夫曼树的一题,望给出详细解释,感激不尽!在线等 - ？
臾珠接骨： (1)构造哈夫曼树:从备选节点中挑出两个权值最小的节点进行构造,构造完成后会生成新的节点(权值为和)放入备选节点中,重复操作 (2)构造哈夫曼树后,往左节点的路径为0往右为1,从根节点顺着路径到叶子,把路径上的0和1组合起来得到哈夫曼编码 (3)一个字符的编码的长度就是占用的二进制位数,8位为一个字节,根据出现次数和总字符数计算得到字节数 (4)根据(2)得到的编码,从左到右对应就行了

延津县15890974645： 数据结构中哈夫曼树的问题 - ？
臾珠接骨： 哈夫曼树为: 15 / \ 6 9 / \ / \ 3 【3】【4】 【5】 / \ 【1】 【2】 树的带权路径长度为树中所有叶子结点的带权路径长度之和,而结点的带权路径长度为结点到根节点之间的路径长度与该节点上权的乘积.WPL=3*(1+2)+2*3+2*(4+5)=33

延津县15890974645： 哈夫曼树是什么?求解 - ？
臾珠接骨： 哈夫曼编码是哈夫曼树的一个应用.哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码.首先介绍什么是哈夫曼树.哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树.所谓树的带权路径长度,就是树中所有的叶结点的权值乘上...

延津县15890974645： 求助有关哈夫曼树编码的问题?急! - ？
臾珠接骨： 我去年数据结构课程设计做的就是这个,具体什么意思也忘得差不多了 反正做了好多天的 把这段代码复制给你void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC, LNode &L,int n){ //构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC ...

延津县15890974645： C语言有关哈夫曼树的问题..救急呀!!!! - ？
臾珠接骨： #include ＂iostream＂ #include ＂iomanip＂ #include ＂string＂ using namespace std; #define MAX 256 typedef string *STR; void InputData(string &s); void DeCode(); typedef struct Huffnode { unsigned weight; //权值 字符出现频率 bool in; // ...

延津县15890974645： 求助,哈夫曼树的C语言编程问题万分 - ？
臾珠接骨： 根据数组 a 中 n 个权值建立一棵哈夫曼树,返回树根指针 struct BTreeNode* CreateHuffman(ElemType a[], int n) {int i, j;struct BTreeNode **b, *q;b = malloc(n*sizeof(struct BTreeNode));for (i = 0; i{b[i] = malloc(sizeof(struct BTreeNode));b[i]->...