#include
#include
typedef?int?DataType;
#define?MaxValue?10000
#define?MaxBit?10
#define?MaxN?100
#define?N?100;
int?n1=0;
char?c[100];
typedef?struct?Node?
{
?DataType?data;
?struct?Node?*leftChild;
struct?Node?*rightChild;
}BiTreeNode;
typedef?struct
{
????int?weight;
????int?flag;
????int?parent;
????int?leftChild;
????int?rightChild;
}HaffNode;

typedef?struct
{
????int?bit[MaxN];
????int?start;
????int?weight;
}Code;

struct?worder
{
?char?words;??????????????????????????/*字符*/
}word[100];
struct?weighted
{
??int?weighter;??????????????????????/*轉換權值有利于文件的存儲*/
}weight[100]?;
void?Initiate（BiTreeNode?**root）????????/*初始化二叉樹*/
{
*root=（BiTreeNode?*?）malloc（sizeof（BiTreeNode））;
?（*root）->leftChild=NULL;
?（*root）->rightChild=NULL;
}
BiTreeNode?*InsertLeftNode（BiTreeNode?*currDataType?x）??/*插入左子樹*/
{
BiTreeNode?*s*t;
if（curr==NULL）??return?NULL;
t=curr->leftChild;
s=（BiTreeNode?*）malloc（sizeof（BiTreeNode））;
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return?curr->leftChild;
}

BiTreeNode?*InsertRightNode（BiTreeNode?*curr?DataType?x）???/*插入右子樹*/
{
BiTreeNode?*s*t;
if（curr==NULL）
?return?NULL;
t=curr->rightChild;
s=（BiTreeNode?*）malloc（sizeof（BiTreeNode））;
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return?curr->rightChild;
}


void?Haffman（int?weigh[]int?nHaffNode?haffTree[]int?a[][3]）?/*建立哈夫曼樹*/
{
????int?ijm1m2x1x2;

?????for（i=0;i<2*n-1;i++）
????{

????????if（i??????????haffTree[i].weight=weigh[i];
????????else?haffTree[i].weight=0;
????????haffTree[i].parent=-1;
????????haffTree[i].flag=0;
????????haffTree[i].leftChild=-1;
????????haffTree[i].rightChild=-1;
????}

????for（i=0;i????{
????????m1=m2=MaxValue;
????????x1=x2=0;
????????for（j=0;j????????{
????????????if（haffTree[j].weight????????????{
????????????????m2=m1;
????????????????x2=x1;
????????????????m1=haffTree[j].weight;
????????????????x1=j;
????????????}
????????????else?if（haffTree[j].weight????????????{
????????????????m2=haffTree[j].weight;
????????????????x2=j;
????????????}
????????}
????????haffTree[x1].parent=n+i;
????????haffTree[x2].parent=n+i;
????????haffTree[x1].flag=1;
????????haffTree[x2].flag=1;
????????haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
????????haffTree[n+i].leftChild=x1;
????????haffTree[n+i].rightChild=x2;
????????a[i+1][0]=haffTree[x1].weight;
????????a[i+1][1]=haffTree[x2].weight;???????/*將每個權值賦值給二維數組a[][]利用這個二維數組可以進行建立二叉樹*/
????????a[i+1][2]=haffTree[n+i].weight;
????}
}


void?HaffmanCode（HaffNode?haffTree[]int?nCode?haffCode[]）???/*對已經建立好的哈夫曼樹進行編碼*/
{
????Code?*cd=（Code?*）malloc（sizeof（Code））;
????int?ijchildparent;

????for（i=0;i????{
????????cd->start=n-1;
????????cd->weight=haffTree[i].weight;
????????child=i;
????????parent=haffTree[child