定義
定義：它是由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("\n%s","inorder:");
zx(n+1,Woods);
printf("\n%s","postorder");
hx(n+1,Woods);
printf("\n"); //輸出先序,中序,後序序列
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,' ');
}
}
