哈夫曼树遍历求WPL和哈夫曼编码C语言--For初学者
楚昀
这篇文章使用纯c来写的，实现了生成哈夫曼树、求WPL和生成哈夫曼编码的应用，思路是，先定义一个结构体如下
typedef struct node
{
int weight;
struct node *lchild,*rchild;
struct node *next;
}HuffNode;
先生成单链表（用next链接），还存储输入的权值（weight），单链表无头结点（因为最后要转化成二叉树，所以不用头结点），而且每一次节点的插入都使单链表保持递增的状态（为生成哈夫曼树做准备）。
计算WPL用到简单的递归，如下
int CalcWPL(HuffNode *huff,int wpl)
{
HuffNode *p = huff;
if(!p)
return 0;
else
{
if(!p->rchild&&!p->rchild)
return p -> weight*wpl;
else
return CalcWPL(p->lchild,wpl+1) + CalcWPL(p->rchild,wpl+1);
}
}
在计算WPL的代码上，稍作改动，就可以生成哈夫曼编码，如下
void HuffCode(HuffNode *huff,int len)
{
HuffNode *p = huff;
static int a[MAX];
int i;
if(p)
{
if(!p->lchild && !p->rchild)
{
printf("%d:",p->weight);
for(i = 0;i< len;i++)
printf("%d",a[i]);
printf("\n");
}
else
{
a[len] = 0;
HuffCode(p->lchild,len+1);
a[len] = 1;
HuffCode(p->rchild,len+1);
}
}
}
左孩子（lchild）和右孩子（rchild）是为生成二叉树准备的。
无头有序单链表的生成（就是链接权值），代码如下
void CreatUpLink(HuffNode **huff,int n)
{
HuffNode *pre,*p ,*s,*head = (*huff);
int x;
scanf("%d",&x);
s = malloc(sizeof(HuffNode));
s -> lchild = NULL;
s -> rchild = NULL;
s -> weight = x;
s -> next = NULL;
head = s;
n--;
while(n--)
{
pre = p = head;
scanf("%d",&x);
s = malloc(sizeof(HuffNode));
s -> lchild = NULL;
s -> rchild = NULL;
s -> weight = x;
if(p->weight > x)
{
s -> next = p;
head = s;
}
else
{
while(p&&p->weight < x)
{
pre = p;
p = p->next;
}
s -> next = pre->next;
pre -> next = s;
}
}
(*huff) = head;
}
生成单链表是生成二叉树的基础，代码如下
void HuffTree(HuffNode **huff)
{
HuffNode *pn1 ,*pn2 ,*p = *huff,*s = NULL,*q = NULL,*pre = NULL,*pr = NULL;
if(!p->next)
return ;
while(p)
{
pn1 = p ;
pn2 = pn1 -> next;
pre = q = pn2 -> next ;
s = malloc(sizeof(HuffNode));
s -> lchild = pn1;
s -> rchild = pn2;
s -> weight = pn1 -> weight + pn2 -> weight;
s ->next = NULL;
if(!pn2 -> next)
{
s -> next = NULL;
pn2 -> next = s;
(*huff) = s;
return;
}
if(pn2 -> next -> weight > s->weight)
{
s -> next = pn2 -> next;
pn2 ->next = s;
}
else
{
while(q && q->weight < s -> weight)
{
pre = q;
q = q->next;
}
s -> next = pre->next;
pre -> next = s;
}
pr = pn2;
p = pn2 -> next;
}
(*huff) = pr;
}
以上是重要的模块，主函数没有写，读者可以自行编写，我提供的代码仅供参考。
下面是全部的代码，编辑环境是Code::Blocks。
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
//201612-4
/* * * * * * * * * * * * * * * *
//测试数据
4
1 3 5 7
29
8
7 19 2 6 32 3 21 10
261
* * * * * * * * * * * * * * * */
typedef struct node
{
int weight;
struct node *lchild,*rchild;
struct node *next;
}HuffNode;
void HuffTree(HuffNode **);
void CreatUpLink(HuffNode **,int);
void InitLink(HuffNode**);
void PrintNode(HuffNode**);
void PrePrint(HuffNode *);
int CalcWPL(HuffNode *,int);
void HuffCode(HuffNode *,int);
int main()
{
int wpl = 0;
HuffNode *huff;
int n;
scanf("%d",&n);
CreatUpLink(&huff,n);
PrintNode(&huff);
HuffTree(&huff);
printf("\nPreorder :\n");
PrePrint(huff);
wpl = CalcWPL(huff,0);
printf("\n\nWPL = %d\n",wpl);
printf("\nHuffCode:\n");
HuffCode(huff,0);
return 0;
}
int CalcWPL(HuffNode *huff,int wpl)
{
HuffNode *p = huff;
if(!p)
return 0;
else
{
if(!p->rchild&&!p->rchild)
return p -> weight*wpl;
else
return CalcWPL(p->lchild,wpl+1) + CalcWPL(p->rchild,wpl+1);
}
}
void HuffCode(HuffNode *huff,int len)
{
HuffNode *p = huff;
static int a[MAX];
int i;
if(p)
{
if(!p->lchild && !p->rchild)
{
printf("%d:",p->weight);
for(i = 0;i< len;i++)
printf("%d",a[i]);
printf("\n");
}
else
{
a[len] = 0;
HuffCode(p->lchild,len+1);
a[len] = 1;
HuffCode(p->rchild,len+1);
}
}
}
void PrePrint(HuffNode *huff)
{
HuffNode *p = huff;
if(p)
{
printf("%d\t",p->weight);
PrePrint(p->lchild);
PrePrint(p->rchild);
}
}
void PrintNode(HuffNode **huff)
{
HuffNode *p = (*huff);
while(p)
{
printf("%d\t",p->weight);
p = p->next;
}
putchar('\n');
}
void InitLink(HuffNode **huff)
{
(*huff) = NULL;
}
void CreatUpLink(HuffNode **huff,int n)
{
HuffNode *pre,*p ,*s,*head = (*huff);
int x;
scanf("%d",&x);
s = malloc(sizeof(HuffNode));
s -> lchild = NULL;
s -> rchild = NULL;
s -> weight = x;
s -> next = NULL;
head = s;
n--;
while(n--)
{
pre = p = head;
scanf("%d",&x);
s = malloc(sizeof(HuffNode));
s -> lchild = NULL;
s -> rchild = NULL;
s -> weight = x;
if(p->weight > x)
{
s -> next = p;
head = s;
}
else
{
while(p&&p->weight < x)
{
pre = p;
p = p->next;
}
s -> next = pre->next;
pre -> next = s;
}
}
(*huff) = head;
}
void HuffTree(HuffNode **huff)
{
HuffNode *pn1 ,*pn2 ,*p = *huff,*s = NULL,*q = NULL,*pre = NULL,*pr = NULL;
if(!p->next)
return ;
while(p)
{
pn1 = p ;
pn2 = pn1 -> next;
pre = q = pn2 -> next ;
s = malloc(sizeof(HuffNode));
s -> lchild = pn1;
s -> rchild = pn2;
s -> weight = pn1 -> weight + pn2 -> weight;
s ->next = NULL;
if(!pn2 -> next)
{
s -> next = NULL;
pn2 -> next = s;
(*huff) = s;
return;
}
if(pn2 -> next -> weight > s->weight)
{
s -> next = pn2 -> next;
pn2 ->next = s;
}
else
{
while(q && q->weight < s -> weight)
{
pre = q;
q = q->next;
}
s -> next = pre->next;
pre -> next = s;
}
pr = pn2;
p = pn2 -> next;
}
(*huff) = pr;
}
运行结果图不附上了，读者可自行运算，本文只是用C语言来提供一种方法。
作者能力有限，难免有bug，欢迎大神评论指教。
类似资料：