哈夫曼树（创建 | 编码） - 图1

    1. #include<stdio.h>
    2. #include<stdlib.h>
    4. #define MAX 100
    6. typedef struct node{
    7.     int w;
    8.     struct node *lchild,*rchild;
    9. }BiTNode, *BiTree;
    11. BiTree CreateHufferman(int num[], int n);
    12. int GetWPL(BiTree T, int pathLen);
    13. void GetCode(BiTree T, int pathLen);
    15. int main() {
    16. /*
    17. 5
    18. 2 5 7 9 13
    19. */
    20.     int n,num[MAX];
    21.     BiTree HfmTree;
    22.     int i;
    23.     int tmp;
    25.     // 输入个数
    26.     do{
    27.         printf("权重个数，最多能输入%d个\n>>> ", MAX);
    28.         scanf("%d", &n);
    29.     } while (n>MAX); //检查输入是否合法
    30.     // 输入数组
    31.     printf("输入权重数组（%d个）\n>>> ", n);
    32.     for (i=0; i<n; i++) {
    33.         scanf("%d", &num[i]);
    34.     }
    35.     // 创造
    36.     HfmTree = CreateHufferman(num, n);
    37.     // 计算WPL
    38.     tmp = GetWPL(HfmTree, 0); //根结点的路径长度为0
    39.     printf("\nWPL：%d\n", tmp);
    41.     // 哈夫曼编码
    42.     printf("权重\t哈夫曼编码");
    43.     GetCode(HfmTree, 0); //根结点的路径长度为0
    44.     printf("\n");
    46.     return 0;
    47. }
    49. BiTree CreateHufferman(int num[], int n) {
    50.     BiTree *tmp; //BiTree[]用于存放n个子树
    51.     BiTNode p;   //结点
    52.     int k1,k2;     //k1为最小的下标，k2为次小的下标
    53.     int i,j;
    54.     //创建一个BiTree[]来存n个子树
    55.     tmp = (BiTree *)malloc(sizeof(BiTree) * n);
    56.     //创建n个结点，每个结点即是树的根，放到tmp[]中统一管理
    57.     for (i=0; i<n; i++) {
    58.         tmp[i] = (BiTNode *)malloc(sizeof(BiTNode)); if (!tmp[i]) exit(0);
    59.         tmp[i]->w = num[i];
    60.         tmp[i]->lchild = tmp[i]->rchild = NULL;
    61.     }
    62.     //构造哈夫曼树，循环n-1次
    63.     for (i=1; i<n; i++) {
    64.         //找出tmp[0]至tmp[n]中的前两个
    65.         k1 = -1; //k1未选
    66.         for (j=0; j<n; j++) {
    67.             if (tmp[j]!=NULL && k1==-1) { //找到了第一个
    68.                 k1 = j;
    69.                 continue; //找k2
    70.             }
    71.             if (tmp[j]!=NULL) { //找到了第二个
    72.                 k2 = j;
    73.                 break; //退出
    74.             }
    75.         }
    76.         //找出最小的、次小的结点
    77.         for (j=k2; j<n; j++) { //从k2开始
    78.             if (tmp[j]==NULL) continue; //空树，进入下一轮循环
    79.             // 和当前k1、k2比较
    80.             if (tmp[j]->w < tmp[k1]->w) { //先和最小的k1比较
    81.                 // 即 [j] < [k1]，j是当前的最小
    82.                 k2 = k1; //△原来最小的变成了次小
    83.                 k1 = j;  //最小的变成了j
    84.             } else if (tmp[j]->w < tmp[k2]->w) { //和次小的比较
    85.                 // 即[k1] < [j] < [k2]
    86.                 k2 = j; //次小的为j
    87.             }
    88.         }
    89.         //合并k1,k2
    90.         p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(0);
    91.         p->w = tmp[k1]->w + tmp[k2]->w;
    92.         p->lchild = tmp[k1];
    93.         p->rchild = tmp[k2];
    94.         tmp[k1] = p;    // 新结点的放到k1的位置
    95.         tmp[k2] = NULL; // k2位置为空
    96.     }
    98.     free(tmp); //删除动态建立的数组tmp[]
    99.         //它只是一个BiTNode *的指针数组，而所指结点（即新建的哈夫曼结点）是不会被删除的！
    100.     return p; //返回哈夫曼树的根结点
    101. }
    103. int GetWPL(BiTree T, int pathLen) {
    104.     // 叶子结点
    105.     if (T->lchild==NULL && T->rchild==NULL) {
    106.         return T->w * pathLen;
    107.     }
    109.     return GetWPL(T->lchild, pathLen+1) + GetWPL(T->rchild, pathLen+1);
    110. }
    112. void GetCode(BiTree T, int pathLen) {
    113.     static char tmp[2*MAX-1]; //存储编码的结果
    114.     int i;
    116.     // 叶子结点
    117.     if (T->lchild==NULL && T->rchild==NULL) {
    118.         printf("\n%d\t", T->w); //结点值
    119.         for (i=0; i<pathLen; i++) { //编码值
    120.             printf("%c", tmp[i]);
    121.         }
    122.         return ;
    123.     }
    125.     //往左走
    126.     tmp[pathLen] = '0';
    127.     GetCode(T->lchild, pathLen+1);
    128.     //往右走
    129.     tmp[pathLen] = '1';
    130.     GetCode(T->rchild, pathLen+1);
    131. }