二叉树创建c语言实现 如何用C语言画赫夫曼树

如何用C语言画赫夫曼树  

如何用C语言画赫夫曼树, 用C语言 根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。, 赫夫曼树及其编码怎么写？

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;
void Select(HuffmanTree HT,int n)
{
int i,j;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(HT[j].parent==0)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
if(HT[s1].weight>HT[i].weight)
if(s2!=i)
s1=i;
}
for(j=1;j<=n;j++)
{
if(HT[j].parent==0)
if(HT[s2].weight>HT[j].weight)
if(s1!=j)
s2=j;
}
if(s1>s2)
{
int temp=s1;
s1=s2;
s2=temp;
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int i,j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
for (i=1; i<=n; i++)
{
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}

新增检视，便于除错
printf("构造过程显示：n");
for(i=1;i<=m;i++)
printf("%4d%4d%4d%4d%4dn",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");
for(i=n+1;i<=m;i++)
{
Select(HT,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;
新增检视，便于除错

}
cd = (char *)malloc(n*sizeof(char));
p=m;
cdlen=0;
for(i=1;i<=m;i++)
HT[i].weight=0;
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
}
else if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='';
strcpy(HC[p],cd);
}
}
else if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
}
}
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("请输入节点数：n");
scanf("%d",&n);
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("请输入节点的权值：n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
printf("输出编码：n");
for(i=1;i<=n;i++)
printf("%2d(%4d):%sn",i,w[i-1],HC[i]);
return 0;
system("pause");
}

赫夫曼树的建立

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

#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;
}
}
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;
}
}
}


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;

}
for(i = n + 1; i <= m; i++)
{
huftree[i].weight = -1;
huftree[i].lchild = huftree[i].rchild = huftree[i].parent = -1;
}
for(i = 1; i <= n - 1; i++)
{
Selectsort(huftree, 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;
}

}


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)
temp[c++] = '0';
else
temp[c++] = '1';
cd[i].code = (char *)malloc(c+1);
cd[i].code[c--] = '';
k = 0;
while(c >= 0)
cd[i].code[k++] = temp[c--];

cd[i].length = k;
}
}
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");
for(i = 1; i <= n; i++)
{
printf("%d * %d + ",huftree[i].weight,cd[i].length);
sum += huftree[i].weight * cd[i].length;
}
printf("0 = %dn",sum);
printf("The Program is over!");
}
else
{
printf("Sorry!You enter error!Please input again!n");
goto A;
}
}

赫夫曼树是否唯一

不唯一，第一：存在左右问题。比如（1,2,4,8）选则最小的两个权值1和2之后，建立了以1+2=3的新节点，下一个结点肯定是选择4和3，那么4和3就存在谁是7的左子树，谁是右子数问题。
第二：比如（1,2，3@,3￥），（注意：我这里面写得‘@’，‘￥’，是为了区别不同的3，并不参与运算）第一步：选择1和2，然后组成3*。第二步，应该在（3*，3@，3￥）中选择两个3，那么选择3*和3@，和选择3@和3￥是不一样的。自己画画

赫夫曼编码

赫夫曼编码就是一组由0和1构成的位元流。为了表示这个位元流，我们用位元组来描述。

资料结构作业，用c语言编:根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。求大神解答，求程式码！

#include "stdafx.h"#include "stdlib.h"#include "string.h"static int s1,s2;typedef struct{unsigned int weight; 结点的权值unsigned int parent;结点的双亲 unsigned int lchild;左孩子 unsigned int rchild;右孩子 unsigned char date;}HTnode,*Huffmantree;typedef char **Huffmancode;void select(Huffmantree HT,int n) 寻找权值最小的S1,s2节点{ int i,j; for(i=1;i<=n;i++) { if(HT[i].parent==0) { s1=i;break; } } for(j=i+1;j<=n;j++) { if(HT[j].parent==0) { s2=j;break; } } for(i=1;i<=n;i++) { if(HT[i].parent==0) { if(HT[s1].weight>HT[i].weight ) { if(s2!=i) { s1=i; } } } } for(j=1;j<=n;j++) { if(HT[j].parent==0) { if(HT[s2].weight>HT[j].weight ) { if(s1!=j) { s2=j; } } } } if(s1>s2) { int temp=s1; s1=s2; s2=temp; }}void Huffmancoding(Huffmantree HT,Huffmancode HC,int *w,int n,char *d){ int i,j,c,f,start; char cd[100]; int m=2*n-1;共有m个节点，n个叶子节点 char string[100];输入字串进行编码 char * out;存放字串编码 HT=(Huffmantree)malloc((m+1)*sizeof(HTnode)); for(i=1;i<=n;i++) { HT[i].weight =w[i-1]; HT[i].date=d[i-1]; HT[i].parent =0; HT[i].lchild =0; HT[i].rchild =0; } for(i=n+1;i<=m;i++) { HT[i].weight =0; HT[i].parent =0; HT[i].lchild =0; HT[i].rchild =0; } for(i=n+1;i<=m;i++) { select(HT,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 ; } printf("输出哈夫曼树的储存结构n"); for(i=1;i<=m;i++) { printf("%4d%4d%4d%4d%cn",HT[i].weight ,HT[i].parent ,HT[i].lchild ,HT[i].rchild,HT[i].date ); } HC=(Huffmancode)malloc((n+1)*sizeof(char*)); cd[n-1]='';编码结束符 for(i=1;i<=n;i++)逐个字元求霍夫曼编码 { start=n-1;编码结束符位置 for(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));为第i个字元编码分配空间 strcpy(HC[i],&cd[start]);从cd复制编码到HC } printf("输出结点的编码n"); for(i=1;i<=n;i++) { printf("%c的编码:",HT[i].date); puts(HC[i]); 用puts函式输出字串 }printf("请输入字串n"); for(i=0;i<=3;i++) 输入字串进行编码 { if(string[i-1]==10) 目的是去除空格字元 { i--; } scanf("%c",&string[i]); } printf("字串的编码是:n"); out=(char*)malloc(n*sizeof(char)); for(i=0;string[i]!='';i++) { for(j=1;j<=n;j++) { if(HT[j].date==string[i]) { strcpy(out,HC[j]); printf("%s",out); break; } } }}int main() { Huffmantree HT; Huffmancode HC; int *w,n,i; char *d; printf("请输入节点数n"); scanf("%d",&n); w=(int *)malloc(n*sizeof(int)); d=(char* )malloc(n*sizeof(char)); printf("请输入节点的权值n"); for(i=0;i<n;i++) { scanf("%d%c",&w[i],&d[i]); } Huffmancoding(HT,HC,w,n,d); return 0;}

急求一个简短的赫夫曼编码C语言程式

给你的程式码是从根出发，遍历整棵哈夫曼树，求得各个叶子结点所表示的字元的哈夫曼编码：
--------------无桟非递回遍历哈夫曼树，求哈夫曼编码
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
p = m; cdlen = 0;
for(i=1;i<=m;++i) HT[i].weight = 0;遍历哈夫曼树时用作结点状态标志
while(p){
if(HT[p].weight == 0){ 向左
HT[p].weight =1;
if(HT[p].lchild!=0){
p=HT[p]lchild; cd[cdlen++]="0";
}
else if(HT[p].rchild == 0){ 登记叶子结点的字元的编码
HC[p] = (char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen] = ""; strcpy(HC[p].cd); 复制编码(串)
}
}
else if (HT[p].weight == 1){ 向右
HT[p].weight =2;
if(HT[p].rchild !=0){
p = HT[p].rchild; cd[cdlen++] = "1";
}
}else{ HT[p].weight == 2,退回
HT[p].weight = 0; p= HT[p].parent; --cdlen; 退到父结点，编码长 度减1
}else
}While

已知权值W＝｛3，5，7，9，11｝，画出赫夫曼树和结点的赫夫曼编码，急求！谢谢

35
/
15 20
/ /
8 7 9 11
/
3 5
编码：3：000 5: 001 7： 01 9： 10 11： 11

求赫夫曼编码，急！

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; 动态分配阵列储存哈夫曼树
typedef char *HuffmanCode; 动态分配阵列储存哈夫曼编码表
void Select(HuffmanTree HT,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(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
演算法6.13
w存放n个字元的权值(均>0)，构造哈夫曼树HT，
并求出n个字元的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;
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;
}
for (i=n+1; i<=m; i++) { 初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("n哈夫曼树的构造过程如下所示：");
printf("HT初态:n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { 建哈夫曼树
在HT[1..i-1]中选择parent为0且weight最小的两个结点，
其序号分别为s1和s2。
Select(HT, 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;
printf("nselect: s1=%d s2=%dn", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}
------无栈非递回遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { 登记叶子结点的字元的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] =''; strcpy(HC[p], cd); 复制编码(串)
}
} else if (HT[p].weight==1) { 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("n各结点的哈夫曼编码:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%sn",i,w[i-1],HC[i]);
getchar();
}