哈夫曼树与哈夫曼编码

1. 路径：树中一个结点到另一个结点之间分支构成的这俩个结点之间的路径
2. 结点的路径长度：俩结点间路径上的分支数
3. 树的路径长度：从树根到每一个结点的路径长度之和
4. 权：将树中的结点赋值一个有着某种含义的值
5. 结点的带权路径长度：根结点到该结点的路径长度乘该结点结点的权（路径长度*权）
6. 树的带权路径长度：树中所有叶子结点的带权路径长度之和

哈夫曼树：带权路径长度最短的二叉树（最优二叉树）

1. 根据给定的权值构成n棵二叉树的森林 F = {T1 , T2 , T3…, Tn}（构造的森林全是根）
2. 在F中选取俩个根结点权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点为原来俩个结点权值之和
3. 在F中删除这俩棵树，同时将新得到的新的二叉树加入森林中
4. 重复2 ，3 过程，直到森林中只有一棵树为止，这棵树即为哈夫曼树

1. 包含n棵树的森林经过n-1次合并形成哈夫曼树，产生n-1个新结点
2. n个叶子结点的哈夫曼树共含有2n-1个结点
3. 哈夫曼树的度为0或者2， 没有度为1的结点

#include
#include
using namespace std;
typedef struct {
    int weight;
    int parent , lch , rch;//双亲，左右孩子
}HNode , *HuffTree;
void Select(HuffTree HT,int m,int *s1,int *s2){//从这m个数里边选择最小的2个//把第一个进行标记就ok 
    int i;//从下标为1的位置开始计数 
    //int min=HT[1].weight;这里直接赋值不合理，假如第一次那个1就是最小被选选中，那么第2次还是被选中 
    int min1=1000; 
    int min2=1000;//规定一个特别大的数 

    for(i=1;i<=m;i++){
        if(HT[i].parent==0&&min1>HT[i].weight){
            min1=HT[i].weight;
            *s1=i;
        }
    }
    for(i=1;i<=m;i++){//注意这个I!=*s1标记min 
        if(i!=(*s1)&&HT[i].parent==0)
            if(HT[i].weight 
哈夫曼编码 
统计字符集中每个字符在电文中出现的平均概率
利用哈夫曼编码的特点：将每个字符的概率作为权值，构造哈夫曼树，概率越大的结点，路径越短
在哈夫曼树的每个分支标记0,1。结点左分支标0，右分支标1。把从根到每个叶子的路径的标号连接起来，作为该叶子结点的字符编号
 
哈夫曼编码的性质
 
哈夫曼编码是前缀码
哈夫曼编码是最优前缀码
 
哈夫曼编码的算法实现
 
void CreatHuffmanCode(HuffTree T ,char **HuffmanCode, int n){
    int i , start ,c ,f;
    HuffmanCode = new char*[n+1];
    char *cd = (char*)malloc(sizeof(char)*n);
    cd[n-1] = '';
    for (i = 1 ; i <= n ; i ++){
        start = n-1;
        c = i,f = T[i].parent;
        while (f != 0){
            start --;
            if (T[f].lch == c) cd[start] = '0';
            else cd[start] = '1';
            c = f, f = T[f].parent;
        }
        //HuffmanCode[i]
        strcpy(HuffmanCode[i],&cd[start]);
    }
    free(cd);
}