哈夫曼编码 急需！满意即追加分 谢谢了
哈夫曼树
一、 基本术语
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
里面有一段看了几个小时都看不懂
%哈夫曼编码的MATLAB实现（基于0、1编码）：
clc;
clear;
A=[0.4,0.2,0.15,0.1,0.1,0.05];%原概率序列
%A=A/sum(A);
%A=fliplr(sort(A));%按降序排列
T=A;
[m,n]=size(A);
B=zeros(n,n-1);%空的编码表（矩阵）
for i=1:n
B(i,1)=T(i);%生成编码表的第一列
end
r=B(i,1)+B(i-1,1);%最后两个元素相加
T(n-1)=r;
T(n)=0;
T=fliplr(sort(T));
t=n-1;
for j=2:n-1%生成编码表的其他各列
for i=1:t
B(i,j)=T(i);
end
K=find(T==r);
B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在该列的位置
r=(B(t-1,j)+B(t,j));%最后两个元素相加
T(t-1)=r;
T(t)=0;
T=fliplr(sort(T));
t=t-1;
end
B%输出编码表
END1=sym('[0,1]');%给最后一列的元素编码
END=END1;
t=3;
d=1;
j=2,i=1: 2
//-------------------------------
//从这里开始就看不懂，帮我注释一下行吗？还有这个算法有错吗？我觉得有点问题啊
for j=n-2:-1:1%从倒数第二列开始依次对各列元素编码
for i=1:t-2
if i>1 & B(i,j)==B(i-1,j)
d=d+1;
else
d=1;
end
B(B(n,j+1),j+1)=-1;
temp=B(:,j+1);
x=find(temp==B(i,j))
END(i)=END1(x(d));
end
y=B(n,j+1);
END(t-1)=[char(END1(y)),'0'];
END(t)=[char(END1(y)),'1'];
t=t+1;
END1=END;
END
end
//上面这段求帮忙了，看了几个小时都看不懂，求帮忙每个注释一下
A%排序后的原概率序列
END%编码结果
for i=1:n
[a,b]=size(char(END(i)));
L(i)=b;
end
avlen=sum(L.*A)%平均码长
H1=log2(A);
H=-A*(H1')%熵
P=H/avlen%编码效率
树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如
JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，
是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点
的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度
为叶结点的层数）。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)
，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径
长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼编码步骤：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
More：http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html
陟凯铃兰： #include<iostream> using namespace std; class Knap { friend int Knapsack(int p[],int w[],int c,int n ); public: void print() { cout<<＂最优解为:＂<<endl; for(int m=1;m<=n;m++) cout<<bestx[m]<<＂ ＂; cout<<endl; } private: int Bound(int i); void ...
沈阳市13576668908： 看看此C++程序(哈夫曼编码)？
陟凯铃兰： 1.任意性:用户输入任意的字符串,系统自动给出每个字符的哈夫曼编码和对应的哈夫曼树 2.友好性:界面要友好,输入有提示,尽量展示人性化 3.可读性:源程序代码清晰、有层次 4.健壮性:用户输入非法数据时,系统要及时给出警告信息
沈阳市13576668908： 哈夫曼编码算法 - ？
陟凯铃兰： 因为其中一个不能是另一个的前缀 所以只能是1111、1110、1101、1100
沈阳市13576668908： Huffman编码 - ？
陟凯铃兰： 先分析个字符的权值:a=3,b=7,c=2,d=3,e=5生成一棵霍夫曼树,得到各字符的编码:a=110,b=0,c=1111,d=1110,e=10平均码长为46/15
沈阳市13576668908： 高分求赫夫曼编码 - ？
陟凯铃兰： #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; // ...
沈阳市13576668908： 编写一个哈夫曼编码译码的程序,一定要是C++语言,C++,C++,C++!!谢谢谢谢不胜感激 - ？
陟凯铃兰： #include<iostream>#include<cstring>#include<iomanip>#include<cstdio> using namespace std; const int MaxSize = 100; struct Element { int weight; int lchild; int rchild; int parent; char cod[MaxSize];//编码 }; void Select(Element huffTree[],int n,...
沈阳市13576668908： 我急需知道当输入任意的字符串时,系统自动给出每个字符的哈夫曼编码和对应的哈夫曼树C++程序,谢谢!) - ？
陟凯铃兰： # include<stdio.h>#include<stdlib.h>#define MAXLEN 100 typedef struct Huffmantree { char ch; /*键值*/ int weight,mark; /*weight为权值,mark为标志域*/ struct Huffmantree *parent,*lchild,*rchild,*next; }Hftree,*linktree;/*整理输入的字符串,合并...
沈阳市13576668908： c语言设计哈夫曼编码 - ？
陟凯铃兰： %d\ } getch();n＂#define MAXBIT 50 / }HNodeType,s),m2.weight=0,count);n-1.lchild=x1.s.s=0; { char letter;*编码的最大位数*/,＂ a[j],n; int i;j<< typedef struct node / { HuffNode[i]; typedef struct /i++) { data[i];j++)/; %c ",我做的是电文出现概率...
沈阳市13576668908： 哈夫曼编码法的压缩和解压缩怎么实现? - ？
陟凯铃兰： 建立一棵赫夫曼树,设每个父节点的左子节点为1,右子节点为0,然后由根节点到所要编码的字符的叶节点的路径确定字符的编码.比如要编码a,假设a在第三层,则由根节点到a的路径为:根节点——右子节点(0)——左子节点(1).那么a的编码就为01.就这样把所有字符进行编码,建立一个赫夫曼编码表.利用这个编码表把字符串编码就是压缩了,解压缩就是把参照赫夫曼编码表把编码转为字符串.
沈阳市13576668908： 哈夫曼编解码 - ？
陟凯铃兰： #include #include #include typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; } HTNode,*HuffmanTree;/*动态分配数组存储哈夫曼树*/ typedef char **HuffmanCode;/*动态分配数组存储哈夫曼编码表*/ typedef struct { unsigned int...
