哈夫曼算法
哈夫曼算法
哈夫曼树是一种树形结构，用哈夫曼树的方法解编程题的算法就叫做哈夫曼算法。树并不是指植物，而是一种数据结构，因为其存放方式颇有点象一棵树有树叉因而称为树。 最简哈夫曼树是由德国数学家冯。哈夫曼 发现的，此树的特点就是引出的路程最短。 概念理解：1.路径 从树中一个节点到另一个节点之间的分支构成这两个节点之间的路径。2.路径长度 路径上的分支数目称作路径长度。
定义
定义：它是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。
因为这种树最早由哈弗曼（Huffman）研究，所以称为哈弗曼树，又叫最优二叉树。
概述
1.初始化： 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。
2. 找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。
4. 判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树
实现
用C语言最简单的哈夫曼算法实现
#include <stdio.h>
#include <conio.h>
struct BinaryTree
{
long data;
int lchild,rchild;
};
//定义一个二叉树结构
void sort(struct BinaryTree cc[],int l,int r);
void xx(long kk,struct BinaryTree cc[]);
void zx(long kk,struct BinaryTree cc[]);
void hx(long kk,struct BinaryTree cc[]);
//对函数的声明
main(void)
{
struct BinaryTree Woods[101];
long i,j,n,xs,k;
scanf("%d",&n);
for ( i=1; i<=n; ++i)
{
scanf("%d",&Woods.data);
Woods.lchild=0;
Woods.rchild=0;
} //依次读入权值
k=n;
xs=1;
--n;
while (k>1)
{
sort(Woods,xs,n+1);
Woods[n+2].data=Woods[xs].data+Woods[xs+1].data; //将根结点权值为左子树也右子树权值之和
Woods[n+2].lchild=xs; //对左子树和右子树的设置
Woods[n+2].rchild=xs+1;
++n;
xs=xs+2;
--k;
} //哈夫曼算法
printf("%s","preorder:");
xx(n+1,Woods);
printf("\%s","inorder:");
zx(n+1,Woods);
printf("\%s","postorder");
hx(n+1,Woods);
printf("\"); //输出先序,中序,后序序列
getch();
}
//快速排序
void sort(struct BinaryTree cc[],int l,int r)
{
long x,y;
int i,j,rc,lc;
i=l;
j=r;
x=cc[(l+r)/2].data;
if (r<l)
return;
do
{
while(cc.data<x)
++i;
while(x<cc[j].data)
--j;
if (i<j)
{
y=cc.data;
rc=cc.rchild;
lc=cc.lchild;
cc.data=cc[j].data;
cc.lchild=cc[j].lchild;
cc.rchild=cc[j].rchild;
cc[j].data=y;
cc[j].lchild=lc;
cc[j].rchild=rc;
++i;
--j;
}
}
while(i>j);
if (i<r)
sort(cc,i,r);
if (j>l)
sort(cc,l,j);
}
//先序序列
void xx(long kk,struct BinaryTree cc[])
{
if (cc[kk].data!=0)
{
printf("%d%c",cc[kk].data,'' '');
if (cc[kk].lchild!=0)
xx(cc[kk].lchild,cc);
if (cc[kk].rchild!=0)
xx(cc[kk].rchild,cc);
}
}
//中序序列
void zx(long kk,struct BinaryTree cc[])
{
if (cc[kk].data!=0)
{
if (cc[kk].lchild!=0)
zx(cc[kk].lchild,cc);
printf("%d%c",cc[kk].data,'' '');
if (cc[kk].rchild!=0)
zx(cc[kk].rchild,cc);
}
}
//后序序列
void hx(long kk,struct BinaryTree cc[])
{
if (cc[kk].data!=0)
{
if (cc[kk].lchild!=0)
hx(cc[kk].lchild,cc);
if (cc[kk].rchild!=0)
hx(cc[kk].rchild,cc);
printf("%d%c",cc[kk].data,'' '');
}
}