1、基本概念

a、路径和路径长度

若在一棵树中存在着一个结点序列 k1，k2，……，kj， 使得 ki是ki+1 的双亲（1<=i<j），则称此结点序列是从 k1 到 kj 的路径。

从 k1 到 kj 所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1.

 

b、结点的权和带权路径长度

在许多应用中，常常将树中的结点赋予一个有着某种意义的实数，我们称此实数为该结点的权，(如下面一个树中的蓝色数字表示结点的权)

结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。

 

c、树的带权路径长度

树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，公式为：

 

其中，n表示叶子结点的数目，wi 和 li 分别表示叶子结点 ki 的权值和树根结点到 ki 之间的路径长度。

如下图中树的带权路径长度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4  =  122

 

 

d、哈夫曼树

哈夫曼树又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。

如下图为一哈夫曼树示意图。

 

2、构造哈夫曼树

 

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

 

 如：对 下图中的六个带权叶子结点来构造一棵哈夫曼树，步骤如下：

 

注意：为了使得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。

具体算法如下：

/**
 * 创建哈夫曼树
 */
PtrHuffman createHuffmanTree(ElemType arr[]){
    PtrHuffman ptrArr[LENGTH];
    PtrHuffman ptr,pRoot=NULL;  

    for (int i = 0; i < LENGTH; i++){  //初始化结构体指针数组,数组中每一个元素为一个结构体指针类型
        ptr = (PtrHuffman)malloc(sizeof(HuffmanTreeNode));  
        ptr->data = arr[i];  
        ptr->left = ptr->right = NULL; 
        ptrArr[i] = ptr;
    }
    
    for(i = 1; i < LENGTH; i++){  //进行 n-1 次循环建立哈夫曼树  
        //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标
        int k1 = -1, k2;
        for(int j = 0; j < LENGTH; j++){  
            if (ptrArr[j] != NULL && k1 == -1){  
                k1 = j;  
                continue;  
            }  
            if (ptrArr[j] != NULL){  
                k2 = j;  
                break;  
            }  
        }  
        //将指针数组中的指针指向的最小值赋值给索引号为k1的,次小值赋值给索引号为k2的
        for (j = k2; j < LENGTH; j++){
            if(ptrArr[j] != NULL){
                if(ptrArr[j]->data < ptrArr[k1]->data){
                    k2 = k1;
                    k1 = j;
                }else if(ptrArr[j]->data < ptrArr[k2]->data){
                    k2 = j;
                }
            }
        }
        //由最小权值树和次最小权值树建立一棵新树,pRoot指向树根结点
        pRoot = (PtrHuffman)malloc(sizeof(HuffmanTreeNode));
        pRoot->data = ptrArr[k1]->data + ptrArr[k2]->data;
        pRoot->left = ptrArr[k1];
        pRoot->right = ptrArr[k2];

        ptrArr[k1] = pRoot; //将指向新树的指针赋给ptrArr指针数组中k1位置
        ptrArr[k2] = NULL; //k2位置为空
    }

    return pRoot;
}

3、哈夫曼编码

在电报通信中，电文是以二进制的0、1序列传送的，每个字符对应一个二进制编码，为了缩短电文的总长度，采用不等长编码方式，构造哈夫曼树，

将每个字符的出现频率作为字符结点的权值赋予叶子结点，每个分支结点的左右分支分别用0和1编码，从树根结点到每个叶子结点的路径上

所经分支的0、1编码序列等于该叶子结点的二进制编码。如上文所示的哈夫曼编码如下：

a 的编码为：00

b 的编码为：01

c 的编码为：100

d 的编码为：1010

e 的编码为：1011

f 的编码为：11

 

4、哈夫曼树的操作运算

以上文的哈夫曼树作为具体实例，用详细的程序展示哈夫曼树的操作运算：

/** 哈夫曼树编码 **/
#include<stdio.h>
#include<stdlib.h> 
#define LENGTH 6

typedef int ElemType;  

typedef struct HuffmanTreeNode{  
    ElemType data;  //哈夫曼树中节点的权值
    struct HuffmanTreeNode* left;  
    struct HuffmanTreeNode* right;  
}HuffmanTreeNode,*PtrHuffman;  


/**
 * 创建哈夫曼树
 */
PtrHuffman createHuffmanTree(ElemType arr[]){
    PtrHuffman ptrArr[LENGTH];
    PtrHuffman ptr,pRoot=NULL;  

    for (int i = 0; i < LENGTH; i++){  //初始化结构体指针数组,数组中每一个元素为一个结构体指针类型
        ptr = (PtrHuffman)malloc(sizeof(HuffmanTreeNode));  
        ptr->data = arr[i];  
        ptr->left = ptr->right = NULL; 
        ptrArr[i] = ptr;
    }
    
    for(i = 1; i < LENGTH; i++){  //进行 n-1 次循环建立哈夫曼树  
        //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标
        int k1 = -1, k2;
        for(int j = 0; j < LENGTH; j++){  
            if (ptrArr[j] != NULL && k1 == -1){  
                k1 = j;  
                continue;  
            }  
            if (ptrArr[j] != NULL){  
                k