哈夫曼树的构造matlab（编写一个程序，构造一棵哈夫曼树）

本文目录

• 编写一个程序，构造一棵哈夫曼树
• 哈夫曼编码的程序实现
• 给定一组权值{6,5,10,9,22,45},构造相应的哈夫曼树,要求写出构造步骤并求出加权路径
• 如何用matlab实现哈夫曼树

编写一个程序，构造一棵哈夫曼树

#include《stdio.h》
#include《string.h》
#define N 50 //叶子结点数
#define M 2*N-1 //树中结点总数
typedef struct
{ char data; //节点值
int weight; //权重
int parent; //双亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
}htnode;
typedef struct
{ char cd; //存放哈夫曼码
int start;
}hcode;
void createht(htnode ht,int n) //构造哈夫曼树
{ int i,k,lnode,rnode;
int min1,min2;
for(i=0;i《2*n-1;i++) //所有结点的相关域置初值-1
ht.rchild=-1;
for(i=n;i《2*n-1;i++) //构造哈夫曼树
{ min1=min2=32767; //lchild和rchild为最小权重的两个结点位置
lnode=rnode=-1;
for(k=0;k《=i-1;k++)
if(ht.parent==-1) //只在尚未构造二叉树的结点中查找
{ if(ht.weight《min1)
{ min2=min1;
rnode=lnode;
min1=ht.weight;
lnode=k;
}
else if(ht.weight《min2)
{ min2=ht.weight;
rnode=k;
}
}
ht.parent=i;
ht.parent=i;
ht.weight;
ht.lchild=lnode;
ht.rchild=rnode;
}
}
void createhcode(htnode ht,int n) //构造哈夫曼编码
{ int i,f,c;
hcode hc;
for(i=0;i《n;i++) //根据哈夫曼树求哈夫曼编码
{ hc.start=n;
c=i;
f=ht.parent;
while(f!=-1) //循序直到树根结点
{ if(ht.lchild==c) //处理左孩子结点
hc.cd=’0’;
else
hc.cd=’1’; //处理右孩子结点
c=f;
f=ht.parent;
}
hc.start++; //start指向哈夫曼编码最开始字符
hcd=hc;
}
}
void disphcode(htnode ht,int n) // 输出哈夫曼编码
{ int i,k;
int sum=0,m=0,j;
printf("输出哈夫曼编码：\n");
for(i=0;i《n;i++)
{ j=0;
printf(" %s:\t",ht.data);
for(k=hcd.start;k《=n;k++)
{ printf("%c",hcd);
j++;
}
m+=ht.weight;
sum+=ht.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;
hcode hcd;
for(i=0;i《n;i++)
{ strcpy(ht);
ht;
}
printf("\n");
createht(ht,n);
createhcode(ht,hcd,n);
disphcode(ht,hcd,n);
printf("\n");
}

哈夫曼编码的程序实现

#include 《stdio.h》
#include 《stdlib.h》
#include 《string.h》
#include 《math.h》
#define M 100
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode;
typedef struct node
{
int start;
int end;
struct node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
//建立队列
void EnterQueue(LinkQueue *q,int s,int e)
{
LinkQueueNode *NewNode;
//生成新节点
NewNode=(LinkQueueNode*)malloc(sizeof( LinkQueueNode ));
if(NewNode!=NULL)
{
NewNode-》start=s;
NewNode-》end=e;
NewNode-》next=NULL;
q-》rear-》next=NewNode;
q-》rear=NewNode;
}
else
{
printf(Error!);
exit(-1);
}
}
//按权分组
void Divide(FanoNode f,int s,int *m,int e)
{
int i;
float sum,sum1;
sum=0;
for(i=s;i《=e;i++)
sum+=f.weight;//
*m=s;
sum1=0;
for(i=s;i《e;i++)
{
sum1+=f.weight;
*m=fabs(sum-2*sum1)》fabs(sum-2*sum1-2*f.weight)?(i+1):*m;
if(*m==i) break;
}
}
void main()
{
int i,j,n,max,m,h;
int sta,end;
float w;
char c,fc;
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//初始化队Q
Q=(LinkQueue *)malloc(sizeof(LinkQueue));
Q-》front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
Q-》rear=Q-》front;
Q-》front-》next=NULL;
printf(\t***FanoCoding***\n);
printf(Please input the number of node:);
//输入信息
scanf(%d,&n);
//超过定义M,退出
if(n》=M)
{
printf(》=%d,M);
exit(-1);
}
i=1; //从第二个元素开始录入
while(i《=n)
{
printf(%d weight and node:,i);
scanf(%f %c,&FN.ch);
for(j=1;j《i;j++)
{
if(FN.ch)//查找重复
{
printf(Same node!!!\n); break;
}
}
if(i==j)
i++;
}
//排序(降序)
for(i=1;i《=n;i++)
{
max=i+1;
for(j=max;j《=n;j++)
max=FN.weight?j:max;
if(FN.weight)
{
w=FN.weight;
FN.weight;
FN.weight=w;
c=FN.ch;
FN.ch;
FN.ch=c;
}
}
for(i=1;i《=n;i++) //初始化h
h=0;
EnterQueue(Q,1,n); //1和n进队
while(Q-》front-》next!=NULL)
{
p=Q-》front-》next; //出队
Q-》front-》next=p-》next;
if(p==Q-》rear)
Q-》rear=Q-》front;
sta=p-》start;
end=p-》end;
free(p);
Divide(FN,sta,&m,end); /*按权分组*/
for(i=sta;i《=m;i++)
{
fc=’0’;
++h;
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc=’\0’;
for(i=m+1;i《=end;i++)
{
fc=’1’;
++h;
}
if(m==sta&&(m+1)==end)
//如果分组后首元素的下标与中间元素的相等，
//并且和最后元素的下标相差为1，则编码码字字符串结束
{
fc=’\0’;
fc=’\0’;
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i《=n;i++) /*打印编码信息*/
{
printf(%c:,FN.ch);
printf(%s\n,fc);
}
system(pause);
} #include 《stdio.h》
#include 《stdlib.h》
#include 《string.h》
#define N 100
#define M 2*N-1
typedef char * HuffmanCode;//haffman编码
typedef struct
{
int weight;//权值
int parent;//父节节点
int LChild;//左子节点
int RChild;//右子节点
}HTNode,Huffman;//huffman树
typedef struct Node
{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}WNode,WeightNode;
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch,int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for(i=0;ch!=’\0’;i++)
{
tag=1;
for(j=0;j《i;j++)
if(ch)
{
tag=0;
break;
}
if(tag)
{
CW;
CW.weight=1;
for(k=i+1;ch!=’\0’;k++)
if(ch)
CW.weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i《=n;i++)
{
ht.weight;
ht.parent=0;
ht.LChild=0;
ht.RChild=0;
}
for(i=n+1;i《=2*n-1;i++)
{
ht.weight=0;
ht.parent=0;
ht.LChild=0;
ht.RChild=0;
}
for(i=n+1;i《=2*n-1;i++)
{
for(j=1;j《=i-1;j++)
if(!ht.parent)
break;
s1=j; //找到第一个双亲为零的结点
for(;j《=i-1;j++)
if(!ht.parent)
s1=ht.weight?j:s1;
ht.parent=i;
ht.LChild=s1;
for(j=1;j《=i-1;j++)
if(!ht.parent)
break;
s2=j; //找到第二个双亲为零的结点
for(;j《=i-1;j++)
if(!ht.parent)
s2=ht.weight?j:s2;
ht.parent=i;
ht.RChild=s2;
ht.weight;//权值累加
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd=’\0’;//末尾置0
for(i=1;i《=n;i++)
{
start=n-1; //cd串每次从末尾开始
c=i;
p=ht.parent;//p在n+1至2n-1
while(p) //沿父亲方向遍历,直到为0
{
start--;//依次向前置值
if(ht.LChild==c)//与左子相同,置0
cd=’0’;
else //否则置1
cd=’1’;
c=p;
p=ht.parent;
}
weight.num=n-start; //二进制码的长度(包含末尾0)
h=(char *)malloc((n-start)*sizeof(char));
strcpy(h);//将二进制字符串拷贝到指针数组h中
}
free(cd);//释放cd内存
system(pause);
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i《m;i++)
{
for(k=1;k《=n;k++) /*从weight相等的下标K*/
if(ch.c)
break;
hc.num)*sizeof(char));
strcpy(hc); //拷贝二进制编码
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf(***StringInformation***\n);
while(i《m)
{
p=2*n-1;//从父亲节点向下遍历直到叶子节点
for(j=0;hc!=’\0’;j++)
{
if(hc==’0’)
p=ht.LChild;
else
p=ht.RChild;
}
printf(%c,w.c); /*打印原信息*/
i++;
}
}
/*****释放huffman编码内存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i《=n;i++)//释放叶子结点的编码
free(h);
for(i=0;i《m;i++) //释放所有结点的编码
free(hc);
}
void main()
{
int i,n=0; /*n为叶子结点的个数*/
int m=0; /*m为字符串ch的长度*/
char ch存放输入的字符串*/
Huffman ht; /*Huffman二叉数*/
HuffmanCode h,hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf(\t***HuffmanCoding***\n);
printf(please input information :);
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息，m为字符串ch的长度*/
printf(***WeightInformation***\n Node );
for(i=1;i《=n;i++) /*输出叶子结点的字符与权值*/
printf(%c ,weight.c);
printf(\nWeight );
for(i=1;i《=n;i++)
printf(%d ,weight.weight);
CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/
printf(\n***HuffamnTreeInformation***\n);
printf(\ti\tweight\tparent\tLChild\tRChild\n);
for(i=1;i《=2*n-1;i++) /*打印Huffman树的信息*/
printf(\t%d\t%d\t%d\t%d\t%d\n,i,ht.RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/
printf( ***NodeCode***\n); /*打印叶子结点的编码*/
for(i=1;i《=n;i++)
{
printf(\t%c:,weight.c);
printf(%s\n,h);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/
printf(***StringCode***\n); /*打印字符串的编码*/
for(i=0;i《m;i++)
printf(%s,hc);
system(pause);
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
FreeHuffmanCode(h,hc,n,m);
system(pause);
} Matlab 中简易实现Huffman编译码：
n=input(’Please input the total number: ’);
hf=zeros(2*n-1,5);
hq=;
for ki=1:n
hf(ki,1)=ki;
hf(ki,2)=input(’Please input the frequency: ’);
hq=;
end
for ki=n+1:2*n-1
hf(ki,1)=ki;
mhq1=min(hq);
m=size(hq);
m=m(:,2);
k=1;
while k《=m%del min1
if hq(:,k)==mhq1
hq=;
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq1|hf(k,5)==1%find min1 location
k=k+1;
end
hf(k,5)=1;
k1=k;
mhq2=min(hq);
k=1;
while k《=m%del min2
if hq(:,k)==mhq2
hq=;
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq2|hf(k,5)==1%find min2 location
k=k+1;
end
hf(k,5)=1;
k2=k;
hf(ki,2)=mhq1+mhq2;
hf(ki,3)=k1;
hf(ki,4)=k2;
hq=;
end
clc
choose=input(’Please choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n’);
while choose==1|choose==2
if choose==1
a=input(’Please input the letter you want to Encoding: ’);
k=1;
while hf(k,2)~=a
k=k+1;
if k》=n
display(’Error! You did not input this number.’);
break
end
end
if k》=n
break
end
r=;
while hf(k,5)==1
kc=n+1;
while hf(kc,3)~=k&hf(kc,4)~=k
kc=kc+1;
end
if hf(kc,3)==k
r=;
else
r=;
end
k=kc;
end
r
else
a=input(’Please input the metrix you want to Decoding: ’);
sa=size(a);
sa=sa(:,2);
k=2*n-1;
while sa~=0
if a(:,1)==0
k=hf(k,3);
else
k=hf(k,4);
end
a=a(:,2:sa);
sa=sa-1;
if k==0
display(’Error! The metrix you entered is a wrong one.’);
break
end
end
if k==0
break
end
r=hf(k,2);
end
choose=input(’Choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n’);
clc;
end
if choose~=1&choose~=2
clc;
end

给定一组权值{6,5,10,9,22,45},构造相应的哈夫曼树,要求写出构造步骤并求出加权路径

这样就可以了

#include《iostream》

#include《stdlib.h》

using namespace std;

typedef int ElemType;

struct BTreeNode

{

ElemType data;

struct BTreeNode* left;

struct BTreeNode* right;

};

//根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针

struct BTreeNode* CreateHuffman(ElemType a, int n)

{

int i, j;

struct BTreeNode **b, *q;

b = (BTreeNode**)malloc(n * sizeof(struct BTreeNode));

for (i = 0; i 《 n; i++) //初始化b指针数组，使每个指针元素指向a数组中对应的元素结点

{

b = (BTreeNode*)malloc(sizeof(struct BTreeNode));

b;

b-》right = NULL;

}

for (i = 1; i 《 n; i++)//进行 n-1 次循环建立哈夫曼树

{

//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标

int k1 = -1, k2;

for (j = 0; j 《 n; j++)//让k1初始指向森林中第一棵树，k2指向第二棵

{

if (b != NULL && k1 == -1)

{

k1 = j;

continue;

}

if (b != NULL)

{

k2 = j;

break;

}

}

for (j = k2; j 《 n; j++)//从当前森林中求出最小权值树和次最小

{

if (b != NULL)

{

if (b-》data)

{

k2 = k1;

k1 = j;

}

else if (b-》data)

k2 = j;

}

}

//由最小权值树和次最小权值树建立一棵新树，q指向树根结点

q = (BTreeNode*)malloc(sizeof(struct BTreeNode));

q-》data = b-》data;

q-》left = b;

q-》right = b;

b = q;//将指向新树的指针赋给b指针数组中k1位置

b = NULL;//k2位置为空

}

free(b); //删除动态建立的数组b

return q; //返回整个哈夫曼树的树根指针

}

//3、求哈夫曼树的带权路径长度

ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0

{

if (FBT == NULL) //空树返回0

return 0;

else

{

if (FBT-》left == NULL && FBT-》right == NULL)//访问到叶子结点

return FBT-》data * len;

else //访问到非叶子结点，进行递归调用，返回左右子树的带权路径长度之和，len递增

return WeightPathLength(FBT-》left, len + 1) + WeightPathLength(FBT-》right, len + 1);

}

}

//主函数

int main(void)

{

int n, i;

ElemType* a;

struct BTreeNode* fbt;

cout 《《 "从键盘输入待构造的哈夫曼树中带权叶子结点数n：";

cin 》》 n;

a = (ElemType*)malloc(n * sizeof(ElemType));

cout 《《 "从键盘输入" 《《 n 《《 "个整数作为权值：";

for (i = 0; i 《 n; i++)

cin 》》 a;

fbt = CreateHuffman(a, n);

cout 《《 "哈夫曼树的带权路径长度：";

cout 《《 WeightPathLength(fbt, 0) 《《 endl;

}

如何用matlab实现哈夫曼树

#include
#include
#include
#include
#define MaxSize 10
#define IS_FULL(ptr)(!(ptr))
typedef struct btnode
{
char code;
int Element;
struct btnode* LChild,*RChild;
}BTNode;
typedef struct btree{
struct btnode* Root;
}BTree;
BTNode* NewNode()
{
BTNode* p=(BTNode*)malloc(sizeof(BTNode));
if(IS_FULL(p)){
fprintf(stderr,"The memeny is full\n");
exit(1);
}
return p;
}
void Fmin(BTree ht,int k)
/*我两元素放kk-1处注意BTree要改变rootElementroot起*/
{
int i,j;
BTree tmp;
for(j=0;j《2;j++)
for(i=0;i《k-j;i++)
if(ht.Root-》ElementElement)
{
tmp = ht;
ht;
ht = tmp;
}
}
//哈夫曼树要codeweight两部组...否则没编码象
BTree CreatHFMTree(char c,int n)
{
BTree ht;
BTree tmp;
int i,k;
for(i=0;i《n;i++)
/*CreateBTzero略余root都用释放所用用赋空再看*/
{
ht.Root = NewNode();
ht;
ht;
}
for(k=n-1;k》0;k--){
Fmin(ht,k);
tmp.Root = NewNode();
tmp.Root-》Element = ht.Root-》Element;
tmp.Root-》LChild = ht.Root;
tmp.Root-》RChild = ht.Root;
ht = tmp;
}
return ht;
}
int main()
{
BTree BT;
int n;
int tmp_i;
char tmp_c;
int w;
char c;
printf("请输入元素数:");
scanf("%i",&n);
for(int i=0;i《n;i++)
{
printf("字符:");
scanf(" %c",&tmp_c);
c = tmp_c;
printf("权重:");
scanf(" %i",&tmp_i);
w = tmp_i;
}
BT=CreatHFMTree(c,w,n);
return 0;
}