赫夫曼树

求解赫夫曼树的问题~

①首先把 n 个叶子结点看做 n 棵树（仅有一个结点的二叉树），把它们看做一个森林。
②在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和。这时森林中还有 n-1 棵树。
③重复第②步直到森林中只有一棵为止。

很高兴为您解答，祝你学习进步！如果您认可我的回答，请点击下面的【选为满意回答】按钮！有不明白的可以追问！

第一步：排序 2 4 5 9
第二步：挑出2个最小的 2 4 为叶子构造出
6
2 4
第三步：判断 6 不大于 5或9（剩余叶子中最小的2个）=》 同方向生长，得出：
11
6 5
2 4
第四步：继续生长
20
11 9
6 5
2 4
权值为 2*3+4*3+5*2+9*1=37
也可以20+11+6=37

例题：6、13、18、30、7、16
排序 6 7 13 16 18 30
13
6 7
26 26大于16或18 =》分支生长
13 13
6 7
26 34
13 13 16 18
6 7
此时最小的2个数为 26 30 得出
56 34
26 30 16 18
13 13
6 7
最后得出 90
56 34
26 30 16 18
13 13
6 7 权值 219
90+56+26+13+34 or 6*4+7*4+13*3+30*2+16*2+18*2

注：第一题 huffman 树以及 huffman编码
我将第二题与第三题与用邻接矩阵存储图相关的操作放在了一起完成
第三题则是利用邻接表

1.第一题
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define LEN 8
#define MAXLEAF 6 // 最大叶子结点数目
#define MAXNODE (MAXLEAF*2)-1

typedef float ElemType;
typedef struct /* this structure stores the information of code */
{
int start; /* 存放编码的起始位置右至左（高位至低位）*/
int bit[LEN]; /* 存放 huffman编码 */
}HCode;

typedef HCode HuffCode[MAXLEAF];
typedef struct /* huffman tree结点的结构 */
{
int parent;
int LChild;
int RChild;
ElemType weight;
}HNode;

typedef HNode Huffman[MAXLEAF*2-1];

void createHuffmanTree(Huffman h,int leaves,ElemType *weight)
{
int i,j;
for(i=0;i<leaves*2-1;i++) /* 初始化huffman tree */
{
(h+i)->parent=-1;
(h+i)->LChild=-1;
(h+i)->RChild=-1;
(h+i)->weight=0;
}
for(i=0;i<leaves;i++) /* 给叶子赋权重 */
{
(h+i)->weight=*(weight+i);
}
/* 上一个循环叶子已经带权,下面这个循环用来生成新根
* 新根数量为n-1
*/
for(i=0;i<leaves-1;i++)
{
ElemType m1, m2;
int m1_pos, m2_pos;
m1=m2=65536; /* m1存放最小的权值m2存放次小的权值 */
m1_pos=m2_pos=0; /* m1存放最小的权值对应下标m2存放次小的权值对应下标*/

for(j=0;j<leaves+i;j++)
{

if((h+j)->weight<m1&&(h+j)->parent==-1)
{
m2=m1;
m1=(h+j)->weight;
m2_pos=m1_pos;
m1_pos=j;
}

else if((h+j)->weight<m2&&(h+j)->parent==-1)
{
m2=(h+j)->weight;
m2_pos=j;
}
}

(h+leaves+i)->parent=-1; // 生成新根，无双亲-1
(h+leaves+i)->LChild=m1_pos; // 新根左孩子在数组中的下标
(h+leaves+i)->RChild=m2_pos; // 新根右孩子在数组中的下标
(h+m1_pos)->parent=leaves+i; // 原根的父亲位置
(h+m2_pos)->parent=leaves+i; // 原根的父亲位置

(h+leaves+i)->weight=m2+m1;
}
}

void huffmancode(Huffman h,HuffCode code,int leaves)
{
int i,j,p,c;
HCode hf;
/*从叶子结点开始向上回溯 从而计算出huffman code */
for(i=0;i<leaves;i++)
{
c=i;
p=h[i].parent;
hf.start=LEN-1;
while(p!=-1)
{
if(h[p].LChild==c)
{
hf.bit[hf.start]=0;
}
else
{
hf.bit[hf.start]=1;
}
--hf.start;
c=p;
p=h[c].parent;
}
for(j=hf.start+1;j<LEN;j++)
{
code[i].bit[j]=hf.bit[j];
}
code[i].start=hf.start+1;
}
}

void printhuffmantree(Huffman h,int leaves)
{
int i;
for(i=0;i<leaves*2-1;i++)
{
printf("weight=%-3.2f",h[i].weight);
printf("parent=%-3d",h[i].parent);
printf("LChild=%-3d",h[i].LChild);
printf("RChild=%-3d\n",h[i].RChild);
}
}

void printhuffcode(HuffCode hcode,char characters[])
{
int i,j;
for(i=0;i<strlen(characters);i++)
{
printf("%c的huffman编码:",characters[i]);

for(j=hcode[i].start;j<LEN;j++)
{
printf("%d",hcode[i].bit[j]);
}
printf("\n");
}
}

int main(void)
{
Huffman h;
HuffCode hcode;
char characters[]={"abcdef"}; /* 待编码的字符 */
ElemType weights[]={0.3,0.7,0.4,0.5,0.9,0.1}; /* 字符出现的频率 */
createHuffmanTree(h,strlen(characters),weights);
printhuffmantree(h,strlen(characters));
huffmancode(h,hcode,sizeof(characters));
printhuffcode(hcode,characters);
system("pause");
return 0;
}

2.第二题 代码如下，以及使用说明

例如有如下的图

a->b
/ \
|
c

首先输入顶点与弧的数目
3 2
提示输入顶点
abc
输入弧（弧头弧尾）
ab
ca
那些插入以及删除的操作已经放入主函数
顾回车后可以看到进行相关操作后图的变化

#include<stdio.h>
#include<stdlib.h>

#define MAXVERT 10 // 需要在图中进行插入操作所以设定一个最大值
#define INFINITE 32767
#define ERROR -1
#define FALSE 0
#define OK 1
typedef int ElemType;

enum maritype{DG,UDG,DN,UDN};

typedef struct
{
char vertex[MAXVERT];
ElemType arc[MAXVERT][MAXVERT];
int ArcNum;
int VertexNum;
}adjacentMatrix;

int locate(adjacentMatrix *G,char v)
{
int i, k=ERROR;
for(i=0;i<G->VertexNum;i++)
{
if(G->vertex[i]==v)
{
k=i;
break;
}
}
return(k);
}

void init(adjacentMatrix *G)
{
int i,j;
for(i=0;i<G->VertexNum;i++)
{
for(j=0;j<G->VertexNum;j++)
{
G->arc[i][j]=0;
}
}
}

void createDN(adjacentMatrix *G)
{
int i,j,k;
char v1,v2,blank;
printf("请输入顶点与弧的数目 \n");
scanf("%d%d",&G->VertexNum,&G->ArcNum);
init(G);
printf("请输入顶点（用字母表示）:\n");
getchar();
for(i=0;i<G->VertexNum;i++)
{
scanf("%c",&G->vertex[i]);
}
getchar();
for(i=0;i<G->ArcNum;i++)
{
printf("请输入弧%d的弧头与弧尾",i+1);
scanf("%c%c",&v1,&v2);
getchar();
j=locate(G,v1);
k=locate(G,v2);
G->arc[j][k]=1;
}
}

int InsertVex(adjacentMatrix *G,char v) /* insert vertex */
{
int i;
if(G->VertexNum>MAXVERT-1)
{
return(FALSE);
}

G->vertex[G->VertexNum++]=v;
for(i=0;i<G->VertexNum;i++)
{
G->arc[i][G->VertexNum-1]=G->arc[G->VertexNum-1][i]=0;
}
return(OK);
}

int InsertAar(adjacentMatrix *G,char v,char w) //插入边
{
int i,j;
i=locate(G,v);
j=locate(G,w);
if(i==-1||j==-1)
{
return(FALSE);
}
G->arc[i][j]=1;
return(OK);
}

int DeleteVex(adjacentMatrix *G,char v) //（删除顶点）
{
int i, k;
k=locate(G,v);
if(k==-1)
{
printf("The vertex has not found\n");
return(FALSE);
}
for(i=k;i<G->VertexNum;i++)
{
G->vertex[i]=G->vertex[i+1];
}
--G->VertexNum;
return(OK);
}

int DeleteArc(adjacentMatrix *G,char v,char w)
{
int i,j;
i=locate(G,v);
j=locate(G,w);
if(i==-1||j==-1)
{
return(ERROR);
}
G->arc[i][j]=0;
return(OK);
}

void degree(adjacentMatrix *G)
{
int i, j, odsum, idsum, zero=0;
for(i=0;i<G->VertexNum;i++)
{
odsum=0;
idsum=0;
for(j=0;j<G->VertexNum;j++)
{
odsum+=G->arc[i][j];
idsum+=G->arc[j][i];

}
if(!odsum)
{
++zero;
}
printf("顶点 %c 的出度与入度是",G->vertex[i]);
printf("%3d%3d\n",odsum,idsum);
}
printf("度为0的顶点 %d\n",zero);
}

void print(adjacentMatrix *G)
{
int i,j;
for(i=0;i<G->VertexNum;i++)
{
printf("%8c",G->vertex[i]);
}
printf("\n");
for(i=0;i<G->VertexNum;i++)
{
for(j=0;j<G->VertexNum;j++)
{
if(!j)
{
printf("%c",G->vertex[i]);
}
printf("%8d",G->arc[i][j]);
}
printf("\n");
}
}

int main(void)
{
int k;
char v, w;
adjacentMatrix G;
createDN(&G);
print(&G); // 邻接矩阵打印
degree(&G); // 求所有顶点出度入度 及度为0的点
InsertVex(&G,'f'); // 插入顶点f
InsertAar(&G,'f','c'); // 插入边 fc
degree(&G); // 观察插入边顶点后度的变化
print(&G); // 邻接矩阵打印
DeleteArc(&G,'f','c'); // 删除边 fc
print(&G); // 邻接矩阵打印 观察变化
DeleteVex(&G,'a'); // 删除顶点a
print(&G); // 邻接矩阵打印 观察删除顶点a后变化
system("pause");
return(0);
}

3.使用同上 示例图也如上所画 使用方式也基本一直
按你的要求只输出 顶点的出度入度以及度为0的顶点

#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 10
#define ERROR -1
#define FALSE 0
#define OK 1

typedef char VertexType;
typedef struct ArcNode // 边表的结构
{
int adjvex; // 与顶点相邻接的顶点在表头结点表（图中）的位置
struct ArcNode *nextarc;
}ArcNode;

typedef struct VertexNode // 表头结点表的结构
{
VertexType data;
ArcNode *firstarc;
}VertexNode;

typedef struct // 存放图信息的结构
{
int vexnum, arcnum; // 顶点与弧的数目
VertexNode vertex[MAX_VERTEX_NUM];
}Adjlist;

int locate(Adjlist *G,char v)
{
int i, k=ERROR;
for(i=0;i<G->vexnum;i++)
{
if(G->vertex[i].data==v)
{
k=i;
break;
}
}
return(k);
}

void createDG(Adjlist *G)
{
int i, j, k;
char v1, v2;
ArcNode *s;
printf("输入顶点与弧的数目 \n");
scanf("%d%d",&G->vexnum,&G->arcnum);
getchar();
printf("请输入顶点（用字母表示）:");
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
scanf("%c",&G->vertex[i].data);
G->vertex[i].firstarc=NULL;
}
getchar();
for(i=0;i<G->arcnum;i++)
{
printf("请输入第%d条边的信息 弧尾与弧头:",i+1);
scanf("%c%c",&v1,&v2);
getchar();
j=locate(G,v1);
k=locate(G,v2);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=k;
s->nextarc=G->vertex[j].firstarc;
G->vertex[j].firstarc=s;
}
}

void od(Adjlist *G)
{
int odsum, i;
ArcNode *p;
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
odsum=0;
p=G->vertex[i].firstarc;
while(p)
{
++odsum;
p=p->nextarc;
}
printf("\n%c的出度是:%d\n ",G->vertex[i].data,odsum);
}
}

void ind(Adjlist *G)
{
int insum, i, j, k;
ArcNode *p;
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
insum=0;

for(j=0;j<G->vexnum;j++)
{
if(i==j)
{
continue;
}
p=G->vertex[j].firstarc;
while(p)
{
if(p->adjvex==i)
{
++insum;
}
p=p->nextarc;
}
}
printf("\n%c的入度是:%d\n ",G->vertex[i].data,insum);
}
}

int main(void)
{
Adjlist G;
int i;
createDG(&G);
od(&G);
ind(&G);
system("pause");
return(0);
}

---

龙州县15512868212： 哈夫曼树 - 搜狗百科？
裴苑活心： 不唯一,因为没有限定左右子树,并且有权值重复时,可能树的高度都不唯一,唯一的只是带权路径长度之和最小. 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为...

龙州县15512868212： 到底什么是哈夫曼树啊,求例子 - ？
裴苑活心： 哈夫曼树是给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 例子: 1、将w...

龙州县15512868212： 关于 赫夫曼树?？
裴苑活心： 根据构造最优二叉树的算法,总是取最前面的两个较小节点构成子树. 所以赫夫曼树(如图)

龙州县15512868212： 什么是哈夫曼树呢? - ？
裴苑活心： 夫曼树是带权路径长度最小的二叉树,用途是平均查找信息的代价最小. 普通二叉树的用途也普通,比较通用,就是信息存储和查找. 普通二叉树可能有的只有一个子节点,而哈夫曼树一定有两个.

龙州县15512868212： 简述哈夫曼树的性质.？
裴苑活心： 哈 夫 曼 树 2.9 二叉树的应用2.9.1 哈夫曼树及应用 哈夫曼树又称最优树(二叉树),是一类带权路径最短的树.构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用.结点之间的路径长度:从一个结点到另一...

龙州县15512868212： 赫夫曼树的建立 - ？
裴苑活心： 给你一个全功能的代码,关于,hufman tree的,你要哪一段就自己节选:/* Note:Your choice is C IDE */#include ＂stdio.h＂#include ＂stdlib.h＂#define N 20/*叶子最大结点数*/ typedef struct { int weight;/*假设叶子权值为整型*/ int lchild,rchild,...

龙州县15512868212： 哈夫曼树问题 - ？
裴苑活心：[答案] 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree).

龙州县15512868212： 谁帮我讲讲哈夫曼树的特点.？
裴苑活心： 给你个我写的哈夫曼函数: void HuffmanTree(HuffmanTree &HT, int * w, int n) { //w 存放n 个字符的权值(均>0),构造赫夫曼树HT if (n<=1) return; m=2* n-1; HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode); //分配存储空间 //用给定的n个权...

龙州县15512868212： 哈夫曼树的定义是:带权路径长度最小的二叉树.我先请问:为何它是带全路径长度最小的二叉树?最小是哈夫曼树的定义是:带权路径长度最小的二叉树.我... - ？
裴苑活心：[答案] 只有带权路径长度最小的二叉树,才是哈夫曼树.当然是可以证明带权路径长度最小