赫夫曼树的建立

哈夫曼树的创建~

哈夫曼树不一定是唯一的，选出最小和次小之后哪个放左边都行的，哈弗曼编码唯一只是说得到的码是唯一，但是可以有许多种码，只是它能够唯一地编码和解码。所以，上面两个图应该都是正确的。如果你习惯按照左小右大的规则来构造的话，那只能选择第二幅图了。

给你个大概的代码，把显示跟调用那里改改#include
#include
#include
#include typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild,ch;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 int m,s1,s2;
HuffmanTree HT;void Select(int n){ //选择两个权值最小的结点
int i,j;
for(i=1;i<=n;i++){
if(!HT[i].parent){
s1 = i;break;
}
}
for(j=i+1;j<=n;j++){
if(!HT[j].parent){
s2 = j;break;
}
}
for(i=1;i<=n;i++){
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i)){
s1=i;
}
}
for(j=1;j<=n;j++){
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j)){
s2=j;
}
}
} void HuffmanCoding(HuffmanCode HC[], int *w, int n) {
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;
int start;if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) {//初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].ch=0;
}
for (i=n+1; i<=m; i++) {//初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].ch=0;
}
for (j=1,i=n+1; i<=m; i++,j++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2
Select(i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
HT[i].ch=j;
}//-----从叶子到根逆向求每个字符的哈夫曼编码
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i){
start=n-1;
HT[i].ch=i;
for(unsigned int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
void PTree(int n){//打印树的结构
int r=2*n-1;
printf("树的结构为（0表示无孩子）：
");
for(;r>0;r--){
cout"<<HT[r].rchild<<endl;
}
}void trans(){//译码
int i=m;
char a;
printf("输入0/1进行译码，输入'!'进行编码");
cin>>a;
while(a=='0'||a=='1'){
if(a=='0')i=HT[i].lchild;
else if(a=='1') i=HT[i].rchild;
if(HT[i].lchild==0){
cout<<(char)(HT[i].ch+64);
i=m;
}
else if(a=='!') return;//当接收到的输入为"!"时返回主函数进行编码
cin>>a;
}
}void main() {
HuffmanTree HT;
HuffmanCode *HC;
int *w,n,i,j;
char b,c;
puts("输入结点数：");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值
",n);
for(i=0;i<n;i++){
scanf("%d",&w[i]);
}
HuffmanCoding(HC,w,n);
puts("
各结点的哈夫曼编码为：");
for(i=1;i<=n;i++){
c=(char)i+64;
cout<<c<<'('<<w[i-1]<<')'<<HC[i]<<endl;
}
PTree(n);
printf("
各结点的哈夫曼译码为：
");
trans();
cout<<"请输入源码：";//从trans函数返回进行编码
cin>>b;
j=(int)(b-64);
while(j){
cout<<HC[j];
cin>>b;
j=(int)(b-64);
}
cout<<endl;
system("pause");
}

给你一个全功能的代码，关于，hufman tree的，你要哪一段就自己节选：

/* Note:Your choice is C IDE */
#include "stdio.h"
#include "stdlib.h"
#define N 20/*叶子最大结点数*/
typedef struct
{
int weight;/*假设叶子权值为整型*/
int lchild,rchild,parent;/*左孩子,右孩子,父结点*/
}Htnode;/*哈夫曼树结点类型*/
typedef struct
{
char *code;/*编码*/
int length;/*编码的长度*/
}CodeType;/*叶编码类型 */
/*功能:求节点中两个最小的数*/
/*传入参数:树huftree[],节点个数n,数*s1,*s2*/
void Selectsort(Htnode huftree[], int n, int *s1, int *s2)
{
int i,min1,min2;/*两个最小数*/
min1 = huftree[0].weight;
*s1 = 0;
for(i = 1; i <= n; i++)
{
if(huftree[i].parent == -1 && huftree[i].weight < min1)
/*如果节点未被构建树,并且小于最小值,则更新最小值*/
{
min1 = huftree[i].weight;
*s1 = i;
}
else/*为下边求另一个最小值赋初值*/
{
min2 = huftree[i].weight;
*s2 = i;
}
}/*end for*/
for(i = 1; i <= n; i++)
{
if(huftree[i].parent == -1 && huftree[i].weight < min2 && huftree[i].weight >= min1 && *s1 != i)
/*如果节点未被构建树,并且小于最小值,并且大于第一个最小值,*/
/*并且在数组中的下标不等于第一个最小值,则更新最小值*/
{
min2 = huftree[i].weight;
*s2 = i;
}
}/*end for*/
}
/*功能:构造一棵哈夫曼树*/
/*传入参数:树huftree[],节点个数n,节点数组w[]*/
void Hufcoding(Htnode huftree[], int w[], int n)
{
int i,s1,s2,m,sum;
m = 2 * n - 1;/*计算哈夫曼树的结点总数*/
for(i = 1; i <= n; i++)/*初始化每个结点自成一棵树*/
{
huftree[i].weight = w[i-1];
huftree[i].lchild = huftree[i].rchild = huftree[i].parent = -1;
/*huftree[i].ch = getchar();*/
}/*end for*/
for(i = n + 1; i <= m; i++)/*给剩下的节点左孩子,右孩子,父结点初始化-1*/
{
huftree[i].weight = -1;
huftree[i].lchild = huftree[i].rchild = huftree[i].parent = -1;
}/*end for*/
for(i = 1; i <= n - 1; i++)/*生成n-1个非叶子结点的循环*/
{
Selectsort(huftree, n + i - 1, &s1, &s2);
/* 对数组 huftree[1..n+i-1]中无双亲的结点权值进行排序,*/
/*s1,s2将是无双亲且权重最小的两个结点下标 */
sum = huftree[s1].weight + huftree[s2].weight;/*求和,构造父节点*/
huftree[n + i].weight = sum;
huftree[s1].parent = huftree[s2].parent = n + i;/*最小的两个节点的父节点的数组的下标*/
huftree[n + i].lchild = s1;/*父节点的左孩子下标*/
huftree[n + i].rchild = s2;/*父节点的右孩子下标*/
}/*end for*/

}
/*功能:求哈夫曼树中各个节点的编码*/
/*传入参数:树huftree[],节点个数n,编码数组cd[]*/
void HuftreeCode(Htnode huftree[], CodeType cd[], int n)
{
int i,c,f,k;
char temp[N];/*暂存叶子编码字符串,最后需要转置*/
for(i = 1; i <= n; i++)/*开始求每个叶子结点的编码*/
{
c = 0;
for(k = i, f = huftree[i].parent; f != -1; k = f,f = huftree[f].parent)
if(huftree[f].lchild == k)/*左分支是0*/
temp[c++] = '0';
else
temp[c++] = '1';/*右分支是1*/
cd[i].code = (char *)malloc(c+1); /*产生存储编码的空间*/
cd[i].code[c--] = '\0';
k = 0;
while(c >= 0)
cd[i].code[k++] = temp[c--];/*将temp转置到cd中*/
/*cd[i].leaf = huftree[i].ch;*/
cd[i].length = k;
}/*end for*/
}
void main()
{
Htnode huftree[2 * N];/*夫曼树的数组*/
CodeType cd[N];/*节点的编码数组*/
int w[N],n,i,temp,sum = 0;/*节点的临时存放及节点的个数*/
printf("The Program is start!\n");/*程序开始*/
printf("Please input The number of Huftree's nodes:");/*输入带权节点的个数*/
scanf("%d",&n);
if(n < N)
{
A:printf("Please input Huftree's weight separated by a space:");/*输入带权值的数*/
for(i = 1; i <= n; i++)
{
scanf("%d",&temp);
w[i-1] = temp;
}
Hufcoding(huftree, w, n);/*创建哈夫曼树*/
printf("The HuftreeCode is:\n");/*打印每个节点的编码*/
HuftreeCode(huftree, cd, n);
for(i = 1; i <= n; i++)
{
printf("%d 's HuftreeCode is:",huftree[i].weight);
puts(cd[i].code);
}
printf("The Huftree's WPL is:\n");/*打印WPL*/
for(i = 1; i <= n; i++)
{
printf("%d * %d + ",huftree[i].weight,cd[i].length);
sum += huftree[i].weight * cd[i].length;
}
printf("0 = %d\n",sum);
printf("The Program is over!");/*程序结束*/
}
else
{
printf("Sorry!You enter error!Please input again!\n");
goto A;
}
}

给你一个全功能的代码，关于，hufman
tree的，你要哪一段就自己节选:
/*
Note:Your
choice
is
C
IDE
*/
#include
"stdio.h"
#include
"stdlib.h"
#define
N
20/*叶子最大结点数*/
typedef
struct
{
int
weight;/*假设叶子权值为整型*/
int
lchild,rchild,parent;/*左孩子,右孩子,父结点*/
}Htnode;/*哈夫曼树结点类型*/
typedef
struct
{
char
*code;/*编码*/
int
length;/*编码的长度*/
}CodeType;/*叶编码类型
*/
/*功能:求节点中两个最小的数*/
/*传入参数:树huftree[],节点个数n,数*s1,*s2*/
void
Selectsort(Htnode
huftree[],
int
n,
int
*s1,
int
*s2)
{
int
i,min1,min2;/*两个最小数*/
min1
=
huftree[0].weight;
*s1
=
0;
for(i
=
1;
i
<=
n;
i++)
{
if(huftree[i].parent
==
-1
&&
huftree[i].weight
<
min1)
/*如果节点未被构建树,并且小于最小值,则更新最小值*/
{
min1
=
huftree[i].weight;
*s1
=
i;
}
else/*为下边求另一个最小值赋初值*/
{
min2
=
huftree[i].weight;
*s2
=
i;
}
}/*end
for*/
for(i
=
1;
i
<=
n;
i++)
{
if(huftree[i].parent
==
-1
&&
huftree[i].weight
<
min2
&&
huftree[i].weight
>=
min1
&&
*s1
!=
i)
/*如果节点未被构建树,并且小于最小值,并且大于第一个最小值,*/
/*并且在数组中的下标不等于第一个最小值,则更新最小值*/
{
min2
=
huftree[i].weight;
*s2
=
i;
}
}/*end
for*/
}
/*功能:构造一棵哈夫曼树*/
/*传入参数:树huftree[],节点个数n,节点数组w[]*/
void
Hufcoding(Htnode
huftree[],
int
w[],
int
n)
{
int
i,s1,s2,m,sum;
m
=
2
*
n
-
1;/*计算哈夫曼树的结点总数*/
for(i
=
1;
i
<=
n;
i++)/*初始化每个结点自成一棵树*/
{
huftree[i].weight
=
w[i-1];
huftree[i].lchild
=
huftree[i].rchild
=
huftree[i].parent
=
-1;
/*huftree[i].ch
=
getchar();*/
}/*end
for*/
for(i
=
n
+
1;
i
<=
m;
i++)/*给剩下的节点左孩子,右孩子,父结点初始化-1*/
{
huftree[i].weight
=
-1;
huftree[i].lchild
=
huftree[i].rchild
=
huftree[i].parent
=
-1;
}/*end
for*/
for(i
=
1;
i
<=
n
-
1;
i++)/*生成n-1个非叶子结点的循环*/
{
Selectsort(huftree,
n
+
i
-
1,
&s1,
&s2);
/*
对数组
huftree[1..n+i-1]中无双亲的结点权值进行排序,*/
/*s1,s2将是无双亲且权重最小的两个结点下标
*/
sum
=
huftree[s1].weight
+
huftree[s2].weight;/*求和,构造父节点*/
huftree[n
+
i].weight
=
sum;
huftree[s1].parent
=
huftree[s2].parent
=
n
+
i;/*最小的两个节点的父节点的数组的下标*/
huftree[n
+
i].lchild
=
s1;/*父节点的左孩子下标*/
huftree[n
+
i].rchild
=
s2;/*父节点的右孩子下标*/
}/*end
for*/
}
/*功能:求哈夫曼树中各个节点的编码*/
/*传入参数:树huftree[],节点个数n,编码数组cd[]*/
void
HuftreeCode(Htnode
huftree[],
CodeType
cd[],
int
n)
{
int
i,c,f,k;
char
temp[N];/*暂存叶子编码字符串,最后需要转置*/
for(i
=
1;
i
<=
n;
i++)/*开始求每个叶子结点的编码*/
{
c
=
0;
for(k
=
i,
f
=
huftree[i].parent;
f
!=
-1;
k
=
f,f
=
huftree[f].parent)
if(huftree[f].lchild
==
k)/*左分支是0*/
temp[c++]
=
'0';
else
temp[c++]
=
'1';/*右分支是1*/
cd[i].code
=
(char
*)malloc(c+1);
/*产生存储编码的空间*/
cd[i].code[c--]
=
'\0';
k
=
0;
while(c
>=
0)
cd[i].code[k++]
=
temp[c--];/*将temp转置到cd中*/
/*cd[i].leaf
=
huftree[i].ch;*/
cd[i].length
=
k;
}/*end
for*/
}
void
main()
{
Htnode
huftree[2
*
N];/*夫曼树的数组*/
CodeType
cd[N];/*节点的编码数组*/
int
w[N],n,i,temp,sum
=
0;/*节点的临时存放及节点的个数*/
printf("The
Program
is
start!\n");/*程序开始*/
printf("Please
input
The
number
of
Huftree's
nodes:");/*输入带权节点的个数*/
scanf("%d",&n);
if(n
<
N)
{
A:printf("Please
input
Huftree's
weight
separated
by
a
space:");/*输入带权值的数*/
for(i
=
1;
i
<=
n;
i++)
{
scanf("%d",&temp);
w[i-1]
=
temp;
}
Hufcoding(huftree,
w,
n);/*创建哈夫曼树*/
printf("The
HuftreeCode
is:\n");/*打印每个节点的编码*/
HuftreeCode(huftree,
cd,
n);
for(i
=
1;
i
<=
n;
i++)
{
printf("%d
's
HuftreeCode
is:",huftree[i].weight);
puts(cd[i].code);
}
printf("The
Huftree's
WPL
is:\n");/*打印WPL*/
for(i
=
1;
i
<=
n;
i++)
{
printf("%d
*
%d
+
",huftree[i].weight,cd[i].length);
sum
+=
huftree[i].weight
*
cd[i].length;
}
printf("0
=
%d\n",sum);
printf("The
Program
is
over!");/*程序结束*/
}
else
{
printf("Sorry!You
enter
error!Please
input
again!\n");
goto
A;
}
}

---

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

开封县18772415337： 赫夫曼树的建立原则是什么 - ？
蓍勉索拉： 其实没什么区别,哈夫曼树一是用来加密的二是用来求最短路径的.所以怎么构建一个树,没多大区别,只要是最小的就行了

开封县18772415337： 哈夫曼树的建立及应用 - ？
蓍勉索拉： 给你个我写的哈夫曼函数:void HuffmanTree(HuffmanTree &HT, int * w, int n) {//w 存放n 个字符的权值(均>0),构造赫夫曼树HT if (nm=2* n-1; HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode); //分配存储空间//用给定的n个权值,构造n棵只有...

开封县18772415337： 怎样构造合适的哈夫曼树? - ？
蓍勉索拉： 来自百度百科:哈夫曼树构造方法: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2) 在森...

开封县18772415337： 权值序列为:10,16,20,6,30,24,如何构造出一棵哈夫曼树? - ？
蓍勉索拉：[答案] 哈夫曼树构造规则是先从序列中选取两个最小的权值的点来构造树,新的树根的权值是两个左右子节点的权值和,该新的权值然后放回到权值序列中.迭代这个过程直到只有一棵树为止. 所以该哈夫曼树是: 106 / \ 44 62 / \ / \ 20 24 30 32 / \ 16 16 / \ 6 10

开封县18772415337： 哈夫曼树(计算机术语) - 搜狗百科？
蓍勉索拉： Typedef struct{ unsigned int weight; unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree; //动态分配数组存储赫夫曼编码表 Typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表 Void HuffmanCoding ( HuffmanTree &HT, ...

开封县18772415337： 哈夫曼树的建立 - ？
蓍勉索拉： 给你个大概的代码,把显示跟调用那里改改#include #include #include#include typedef struct { unsigned int weight; unsigned int parent,lchild,rchild,ch; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode; //动态分配...

开封县18772415337： 构造赫夫曼树 - ？
蓍勉索拉： #include＂stdio.h＂ #include＂stdlib.h＂ #include＂string.h＂typedef char ElemType; typedef struct { ElemType elem; unsigned int m_weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;typedef char** HuffmanCode; typedef int Status...

开封县18772415337： 哈夫曼数编码实现 - ？
蓍勉索拉： 一样的实验题呵呵.自己写的,能够运行(在vs2005下通过)你看看吧文件Main.cpp#include ＂main.h＂//在HT[1...i-1]选择parent为且weigth最小的两个节点,其序号分别为s1和s2.void...