哈夫曼树遍历求WPL和哈夫曼编码C语言

遍历求WPL和哈夫曼编码C语言"/>

哈夫曼树遍历求WPL和哈夫曼编码C语言

这篇文章使用纯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;elsereturn 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
298
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;elsereturn 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，欢迎大神评论指教。