haffmanTree_C/C++/C#

haffmanTree

#include

#define MaxN 10//初始设定的最大结点个数

#define MaxValue 10000//初始设定的权值最大值

#define MaxBit 4//初始设定的最大编码位数

typedef struct{

int weight;//权值

int flag;//标记，是否已经加入到哈夫曼树中

int parent;//双亲节点下标

int leftChild;//左孩子下标

int rightChile;//右孩子下标

int du;

}HaffNode;//哈夫曼树的结点构体

typedef struct{

int bit[MaxN];//数组

int start;//编码的起始下标

int weight;//字符的权值

}Code;//哈夫曼编码的结构

int wpl;

//建立哈夫曼树

void HaffmanTree(int weight[],int n,HaffNode haffTree[]){

//建立叶结点个数为n，权值数组为weight的哈夫曼树haffTree

int i,j,m1,m2,x1,x2;

//哈夫曼树的haffTree的初始化，n个叶节点的二叉树共有2n-1个结点

for(i=0;i<2*n-1;i++){

if(i

haffTree[i].weight=weight[i];

}else{

haffTree[i].weight=0;

}

haffTree[i].parent=-1;

haffTree[i].flag=0;

haffTree[i].leftChild=-1;

haffTree[i].rightChile=-1;

}

//构造哈夫曼树haffTree的n-1个非叶节点

for(i=0;i

m1=m2=MaxValue;

x1=x2;

for(j=0;j

if(haffTree[j].weight

//x1最小的下标，x2次小的下标，m1最小的权值，m2次小的权值

//flag==0表示还没有加入到哈夫曼树

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].rightChile=x2;

}

void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]){

//由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode

Code *cd=(Code *)malloc(sizeof(Code));

int i,j,child,parent;

//求n个叶结点的哈夫曼编码

for(i=0;i

cd->start=n-1;//不等长编码的最后一位为n-1

cd->weight=haffTree[i].weight;//取得编码对应的权值

child=i;

parent=haffTree[child].parent;

//由叶节点向上直到根结点

while(parent!=-1){

if(haffTree[parent].leftChild==child){

cd->bit[cd->start]=0;//左孩子分支编码0

}else{

cd->bit[cd->start]=1;//右孩子分支编码1

}

cd->start--;

child=parent;

parent=haffTree[child].parent;

}

for(j=cd->start+1;j

haffCode[i].bit[j]=cd->bit[j];//保存每个叶节点的编码

}

haffCode[i].start=cd->start+1;//保存叶结点编码的起始位

haffCode[i].weight=cd->weight;//保存编码对应的权值

}

void DU(HaffNode haffTree[],int n)

{

for(int i=0;i<2*n-1;i++){

haffTree[i].du=0;

if(haffTree[i].parent!=-1)haffTree[i].du++;

if(haffTree[i].leftChild!=-1)haffTree[i].du++;

if(haffTree[i].rightChile!=-1)haffTree[i].du++;

}

int main(){

int i,j,n;

wpl=0;

int weight[150];

for(scanf("%d",&n),i=0;i

HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n-1));

Code *myHaffCode=(Code *)malloc(sizeof(Code)*n);

HaffmanTree(weight,n,myHaffTree);

DU(myHaffTree,n);

for(int i=0;i<2*n-1;i++){

printf("weight=%d",myHaffTree[i].weight);

printf(" lchild:%d",myHaffTree[myHaffTree[i].leftChild].weight);

printf(" rchild:%d",myHaffTree[myHaffTree[i].rightChile].weight);

//printf(" 度: %d",myHaffTree[i].du);

printf("n");

printf(" %d",myHaffTree[ myHaffTree[i].parent].weight);

}

HaffmanCode(myHaffTree,n,myHaffCode);

//输出每个叶节点的哈夫曼编码

printf("HaffmanCode:n");

for(i=0;i

printf("Weight=%d Code=",myHaffCode[i].weight);

wpl+=(n-myHaffCode[i].start)*myHaffCode[i].weight;

for(j=myHaffCode[i].start;j

printf("%d",myHaffCode[i].bit[j]);

}

printf("n");

}

// printf("WPL: %d",wpl);

}

haffmanTree

C/C++/C#相关栏目本月热门文章