哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
创新互联建站专注于企业成都全网营销推广、网站重做改版、泾县网站定制设计、自适应品牌网站建设、H5建站、商城网站开发、集团公司官网建设、外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为泾县等各大城市提供网站开发制作服务。
例子：
1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3、从森林中删除选取的两棵树，并将新树加入森林；
4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
扩展资料：
按照哈夫曼编码构思程序流程：
1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；
2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。
3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。
4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可
5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。
参考资料来源:百度百科——哈夫曼树
有6个字符,分别是A,B,C,D,E,F,对应的权值分别是6,5,4,3,2,1,
也就是说字符A的权值是6,字符B的权值是5,按此顺序,最后的字符F的权值是1.
求这6个字符的哈夫曼编码.
运行程序:
输入叶子结点的总个数(n): 6
输入6个叶子结点的字符(Data)和权值(Weight):
No.1=Data:A
Weight:6
No.2=Data:B
Weight:5
No.3=Data:C
Weight:4
No.4=Data:D
Weight:3
No.5=Data:E
Weight:2
No.6=Data:F
Weight:1
输出哈夫曼编码:
A (6): 10
B (5): 01
C (4): 00
D (3): 110
E (2): 1111
F (1): 1110
对应的哈夫曼树(带权值):
N21
/ \
N9 N12
/ \ / \
4 5 6 N6
/ \
3 N3
/ \
1 2
对应的哈夫曼树(带字符):
( 注:哈夫曼树的左分支代表0,右分支代表1 )
N21
/ \
N9 N12
/ \ / \
C B A N6
/ \
D N3
/ \
F E
例如:
从根结点N21到结点A,先经历右分支,后经历左分支,结点A的编码就是10
从根结点N21到结点F,先经历三次右分支,最后经历左分支,结点F的编码就是1110
#includestdio.h
#define max 21
struct huffnode
{
char data;
int weight;
int parent;
int left;
int right;
};
struct huffcode
{
char cd[max];
int start;
};
int main() //原代码main()
{
struct huffnode ht[2*max];
struct huffcode hcd[max],d;
int i,k,f,l,r,n,c,m1,m2;
//printf("please input n \n");
printf("输入叶子结点的总个数(n): ");
scanf("%d",n);
printf("输入%d个叶子结点的字符(Data)和权值(Weight):\n",n);
for(i=1;i=n;i++)
{
getchar(); //吸收掉回车符'\n'
//原代码printf("NO.d=Data:",i);
printf("NO.%d=Data:",i);
scanf("%c",ht[i].data);
printf("\t Weight:");
scanf("%d",ht[i].weight);
}
for(i=1;i=2*n-1;i++) //所有结点初始化
{
ht[i].parent=ht[i].left=ht[i].right=0;
}
//创建"哈夫曼树"
//原代码for(i=1;i=2*n-1;i++)
for(i=1;in;i++)
{
//查找"最小值"和"次最小值"的下标
//l是最小值的下标,r是次最小值的下标
m1=32767;
l=r=0;
//原代码for(k=1;k=i-1;k++)
for(k=1;k=n+i-1;k++)
{
//原代码if(ht[k].weight==0)
if(ht[k].parent==0)
{
if(ht[k].weightm1)
{
m2=m1;
r=l; //原代码r=1;
m1=ht[k].weight;
l=k;
}
else if(ht[k].weightm2)
{
m2=ht[k].weight;
r=k;
}
}
}
//原代码ht[l].parent=i;
//原代码ht[r].parent=i;
//原代码ht[i].weight=ht[l].weight+ht[r].weight;
//原代码ht[i].left=l;
//原代码ht[i].right=r;
ht[l].parent=n+i;
ht[r].parent=n+i;
ht[n+i].weight=ht[l].weight+ht[r].weight; //新结点
ht[n+i].left=l;
ht[n+i].right=r;
}
//编码过程
for(i=1;i=n;i++)
{
d.start=n;
c=i;
f=ht[i].parent;
while(f!=0)
{
if(ht[f].left==c)
{
d.cd[d.start]='0';
}
else
{
d.cd[d.start]='1';
}
d.start=d.start-1;
c=f;
f=ht[f].parent;
}
//原代码hcd[i]=d;
hcd[i].start=d.start;
for(k=d.start+1; k=n; k++)
{
hcd[i].cd[k]=d.cd[k];
}
}
//输出每个叶子结点的哈夫曼编码
//printf("output huff_code:\n");
printf("输出哈夫曼编码:\n");
for(i=1;i=n;i++)
{
printf("%c (%d): ",ht[i].data,ht[i].weight);
//原代码for(k=hcd[i].start;k=n;k++)
for(k=hcd[i].start+1;k=n;k++)
{
printf("%c",hcd[i].cd[k]);
}
printf("\n");
}
return 0; //int main()要有返回值
}
写给你了，请发JAVA版块
package other;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* 定义了一种接口，要进行编码的最小单元类必需实现些接口
*
*/
interface CombinableT extends ComparableT {
T combinate(T a, T b);
}
/**
*
* the huffman tree Class 哈夫曼树，包括当前节点数据信息，左节点，右节点信息。
*/
class HuffmanTreeT extends CombinableT implements
ComparableHuffmanTreeT {
/** the root of huffman tree */
private T root;
/** the left node of huffman tree */
private HuffmanTreeT left;
/** the right node of huffman tree */
private HuffmanTreeT right;
/** 哈夫曼编码字符串，如:0000110 */
private String huffmanCodeString = "";
/** 是否对最终生成的哈夫曼进行过编码操作 */
private static boolean isSettedHuffmanCoderString = false;
public T getRoot() {
return root;
}
public void setRoot(T root) {
this.root = root;
}
public HuffmanTreeT getLeft() {
return left;
}
public void setLeft(HuffmanTreeT left) {
this.left = left;
}
public HuffmanTreeT getRight() {
return right;
}
public void setRight(HuffmanTreeT right) {
this.right = right;
}
/**
*
* 重写此方法用于递归合并节点后进行排序操作
*
*/
public int compareTo(HuffmanTreeT o) {
return o.getRoot().compareTo(this.getRoot());
}
public String toString() {
return "the root:" + this.getRoot() + "\r\nthe left:" + this.getLeft()
+ "\r\nthe right:" + this.getRight();
}
/**
*
* 对最终生成的树进行哈夫曼编码，使每个叶子节点生成01的路径编码
*
*/
private void setHuffmanCoderString() {
HuffmanTreeT left = this.getLeft();
// 如果有左节点则在路径中追加"0"
if (left != null) {
left.huffmanCodeString = this.huffmanCodeString + "0";
left.setHuffmanCoderString();// 递归编码
}
HuffmanTreeT right = this.getRight();
// 如果有右节点则在路径中追加"1"
if (right != null) {
right.huffmanCodeString = this.huffmanCodeString + "1";
right.setHuffmanCoderString();// 递归编码
}
}
public void printHuffmanCoderString() {
// 打印最终生成树的哈夫曼编码前要进行编码操作，
// 且此操作只执行一次，所以用全局标识变量判断
if (!HuffmanTree.isSettedHuffmanCoderString) {
this.setHuffmanCoderString();
HuffmanTree.isSettedHuffmanCoderString = true;// 标识已执行过编码
}
// 如果是叶子节点（即要编码的单元），则打印出编码信息，如果是非叶子结点（中间临时生成的节点），则不打印
if (this.left == null this.right == null)
System.out.println("the " + this.getRoot() + " huffmanCoder:"
+ this.huffmanCodeString);
if (this.left != null)
this.left.printHuffmanCoderString();// 递归打印
if (this.right != null)
this.right.printHuffmanCoderString();// 递归打印
}
}
/**
*
* 用类用于生成一个哈夫曼树
*/
class HuffmanTreeFactoryT extends CombinableT {
/** 初始时一个list列表当作要编码的单元类的容器 */
private ListHuffmanTreeT HuffmanTreeCollection;
/**
*
* @param unitClasses
* 待编码的单元类集合
*
*/
public HuffmanTreeFactory(ListT unitClasses) {
if (unitClasses == null || unitClasses.size() == 0)
throw new IllegalArgumentException(
"the unit classes collection can't be empty");
HuffmanTreeCollection = new LinkedListHuffmanTreeT();
// 初始化哈夫曼集合容器
for (T unitClass : unitClasses) {
HuffmanTreeT huffmanTree = new HuffmanTreeT();
huffmanTree.setRoot(unitClass);
huffmanTree.setLeft(null);
huffmanTree.setLeft(null);
HuffmanTreeCollection.add(huffmanTree);
}
Collections.sort(HuffmanTreeCollection);
}
/**
* 将待编码的哈夫曼集合处理成只含有一个元素的集合，则这最后一个元素 即为最终生成的哈夫曼树
*/
private void generateHuffmanTree() {
while (true) {
if (HuffmanTreeCollection == null
|| HuffmanTreeCollection.size() = 1)
break;
// 处理之前一定要重新排序，这是哈夫曼编码的关键原理
Collections.sort(HuffmanTreeCollection);
HuffmanTreeT huffmanTreeOne = HuffmanTreeCollection.remove(0);
HuffmanTreeT huffmanTreeTwo = HuffmanTreeCollection.remove(0);
HuffmanTreeT huffmanTreeNew = new HuffmanTreeT();
// 将集合中前面两个元素合并成一个元素插到集合中去
// 并将第一个元素和第二个元素分别作为新元素的左，右节点
huffmanTreeNew.setRoot(huffmanTreeOne.getRoot().combinate(
huffmanTreeOne.getRoot(), huffmanTreeTwo.getRoot()));
huffmanTreeNew.setLeft(huffmanTreeOne);
huffmanTreeNew.setRight(huffmanTreeTwo);
HuffmanTreeCollection.add(huffmanTreeNew);
}
}
/**
*
*
*
* @return 生成最终的哈夫曼树
*
*/
public HuffmanTreeT getHuffmanTree() {
generateHuffmanTree();
return this.HuffmanTreeCollection.get(0);
}
}
/**
* 自定义一个用于测试的单元类
*/
class UnitClass implements Serializable, CombinableUnitClass {
/** 出现概率数据 */
private int rate;
public UnitClass(int rate) {
this.rate = rate;
}
public int getRate() {
return rate;
}
public void setRate(int rate) {
this.rate = rate;
}
/**
* implements thid compartTo() in order to sort the
*
* collection stored from unitclass
*/
public int compareTo(UnitClass o) {
return o.getRate() this.rate ? 1 : o.getRate() this.rate ? -1 : 0;
}
public String toString() {
return "the rate is:" + rate;
}
/**
*
* 重写此方法用于哈夫曼编码时可以合并两个分支点信息
*
*/
public UnitClass combinate(UnitClass a, UnitClass b) {
if (a == null || b == null)
return null;
return new UnitClass(a.getRate() + b.getRate());
}
}
public class Test {
public static int counter(String s, char c) {
int count = 0;
for (int i = 0; i s.length(); i++) {
if (s.charAt(i) == c) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String str = "你好呵呵123abbeab啊";
ListUnitClass l = new ArrayListUnitClass();
for (int i = 0; i str.length(); i++) {
char c = str.charAt(i);
System.out.println(c + "出现了" + counter(str, c) + "次");
l.add(new UnitClass(c));
}
HuffmanTreeFactoryUnitClass factory = new HuffmanTreeFactoryUnitClass(
l);
factory.getHuffmanTree().printHuffmanCoderString();
}
}
#includestdio.h
#includestring.h
#define N 50 //叶子结点数
#define M 2*N-1 //树中结点总数
typedef struct
{ char data[5]; //节点值
int weight; //权重
int parent; //双亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
}htnode;
typedef struct
{ char cd[N]; //存放哈夫曼码
int start;
}hcode;
void createht(htnode ht[],int n) //构造哈夫曼树
{ int i,k,lnode,rnode;
int min1,min2;
for(i=0;i2*n-1;i++) //所有结点的相关域置初值-1
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for(i=n;i2*n-1;i++) //构造哈夫曼树
{ min1=min2=32767; //lchild和rchild为最小权重的两个结点位置
lnode=rnode=-1;
for(k=0;k=i-1;k++)
if(ht[k].parent==-1) //只在尚未构造二叉树的结点中查找
{ if(ht[k].weightmin1)
{ min2=min1;
rnode=lnode;
min1=ht[k].weight;
lnode=k;
}
else if(ht[k].weightmin2)
{ min2=ht[k].weight;
rnode=k;
}
}
ht[lnode].parent=i;
ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;
ht[i].rchild=rnode;
}
}
void createhcode(htnode ht[],hcode hcd[],int n) //构造哈夫曼编码
{ int i,f,c;
hcode hc;
for(i=0;in;i++) //根据哈夫曼树求哈夫曼编码
{ hc.start=n;
c=i;
f=ht[i].parent;
while(f!=-1) //循序直到树根结点
{ if(ht[f].lchild==c) //处理左孩子结点
hc.cd[hc.start--]='0';
else
hc.cd[hc.start--]='1'; //处理右孩子结点
c=f;
f=ht[f].parent;
}
hc.start++; //start指向哈夫曼编码最开始字符
hcd[i]=hc;
}
}
void disphcode(htnode ht[],hcode hcd[],int n) // 输出哈夫曼编码
{ int i,k;
int sum=0,m=0,j;
printf("输出哈夫曼编码：\n");
for(i=0;in;i++)
{ j=0;
printf(" %s:\t",ht[i].data);
for(k=hcd[i].start;k=n;k++)
{ printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n平均长度=%g\n",1.0*sum/m);
}
void main()
{ int n=15,i;
char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
htnode ht[M];
hcode hcd[N];
for(i=0;in;i++)
{ strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
createht(ht,n);
createhcode(ht,hcd,n);
disphcode(ht,hcd,n);
printf("\n");
}
