哈夫曼树

#include<bits/stdc++.h>
#define maxsize 100
using namespace std;

//哈夫曼树结点结构
typedef struct {
    int weight;//结点权重
    int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
}htnode, *huffmantree;
//动态二维数组，存储哈夫曼编码
typedef char ** huffmancode;

//ht数组中存放的哈夫曼树，end表示ht数组中存放结点的最终位置，s1和s2传递的是ht数组中权重值最小的两个结点在数组中的位置
void select(huffmantree ht, int end, int *s1, int *s2)
{
    int min1, min2;
    //遍历数组初始下标为 1
    int i = 1;
    //找到还没构建树的结点
    while(ht[i].parent != 0 && i <= end){
        i++;
    }
    min1 = ht[i].weight;
    *s1 = i;
   
    i++;
    while(ht[i].parent != 0 && i <= end){
        i++;
    }
    //对找到的两个结点比较大小，min2为大的，min1为小的
    if(ht[i].weight < min1){
        min2 = min1;
        *s2 = *s1;
        min1 = ht[i].weight;
        *s1 = i;
    }else{
        min2 = ht[i].weight;
        *s2 = i;
    }
    //两个结点和后续的所有未构建成树的结点做比较
    for(int j=i+1; j <= end; j++)
    {
        //如果有父结点，直接跳过，进行下一个
        if(ht[j].parent != 0){
            continue;
        }
        //如果比最小的还小，将min2=min1，min1赋值新的结点的下标
        if(ht[j].weight < min1){
            min2 = min1;
            min1 = ht[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
        //如果介于两者之间，min2赋值为新的结点的位置下标
        else if(ht[j].weight >= min1 && ht[j].weight < min2){
            min2 = ht[j].weight;
            *s2 = j;
        }
    }
}

//ht为地址传递的存储哈夫曼树的数组，w为存储结点权重值的数组，n为结点个数
void createhuffmantree(huffmantree *ht, int *w, int n)
{
    if(n<=1) return; // 如果只有一个编码就相当于0
    int m = 2*n-1; // 哈夫曼树总节点数，n就是叶子结点
    *ht = (huffmantree) malloc((m+1) * sizeof(htnode)); // 0号位置不用
    huffmantree p = *ht;
    // 初始化哈夫曼树中的所有结点
    for(int i = 1; i <= n; i++)
    {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
    //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
    for(int i = n+1; i <= m; i++)
    {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
    //构建哈夫曼树
    for(int i = n+1; i <= m; i++)
    {
        int s1, s2;
        select(*ht, i-1, &s1, &s2);
        (*ht)[s1].parent = (*ht)[s2].parent = i;
        (*ht)[i].left = s1;
        (*ht)[i].right = s2;
        (*ht)[i].weight = (*ht)[s1].weight + (*ht)[s2].weight;
    }
}

/*使用程序求哈夫曼编码有两种方法：
1.从叶子结点一直找到根结点，逆向记录途中经过的标记。
例如，图 3 中字符 c 的哈夫曼编码从结点 c 开始一直找到根结点，
结果为：0 1 1 ，所以字符 c 的哈夫曼编码为：1 1 0（逆序输出）。
2.从根结点出发，一直到叶子结点，记录途中经过的标记。
例如，求图 3 中字符 c 的哈夫曼编码，就从根结点开始，依次为：1 1 0。
*/
//ht为哈夫曼树，hc为存储结点哈夫曼编码的二维动态数组，n为结点的个数
void huffmancoding(huffmantree ht, huffmancode *hc,int n){
    *hc = (huffmancode) malloc((n+1) * sizeof(char *));
    char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
    cd[n-1] = '';//字符串结束符
   
    for(int i=1; i<=n; i++){
        //从叶子结点出发，得到的哈夫曼编码是逆序的，需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = ht[i].parent;
        // 一直寻找到根结点
        while(j != 0){
            // 如果该结点是父结点的左孩子则对应路径编码为0，否则为右孩子编码为1
            if(ht[j].left == c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
            //以父结点为孩子结点，继续朝树根的方向遍历
            c = j;
            j = ht[j].parent;
        }
        //跳出循环后，cd数组中从下标 start 开始，存放的就是该结点的哈夫曼编码
        (*hc)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*hc)[i], &cd[start]);
    }
    //使用malloc申请的cd动态数组需要手动释放
    free(cd);
}

//ht为哈夫曼树，hc为存储结点哈夫曼编码的二维动态数组，n为结点的个数
void huffmancoding1(huffmantree ht, huffmancode *hc,int n){
    *hc = (huffmancode) malloc((n+1) * sizeof(char *));
    int m=2*n-1;
    int p=m;
    int cdlen=0;
    char *cd = (char *)malloc(n*sizeof(char));
    //将各个结点的权重用于记录访问结点的次数，首先初始化为0
    for (int i=1; i<=m; i++) {
        ht[i].weight=0;
    }
    //一开始 p 初始化为 m，也就是从树根开始。一直到p为0
    while (p) {
        //如果当前结点一次没有访问，进入这个if语句
        if (ht[p].weight==0) {
            ht[p].weight=1;//重置访问次数为1
            //如果有左孩子，则访问左孩子，并且存储走过的标记为0
            if (ht[p].left!=0) {
                p=ht[p].left;
                cd[cdlen++]='0';
            }
            //当前结点没有左孩子，也没有右孩子，说明为叶子结点，直接记录哈夫曼编码
            else if(ht[p].right==0){
                (*hc)[p]=(char*)malloc((cdlen+1)*sizeof(char));
                cd[cdlen]='';
                strcpy((*hc)[p], cd);
            }
        }
        //如果weight为1，说明访问过一次，即是从其左孩子返回的
        else if(ht[p].weight==1){
            ht[p].weight=2;//设置访问次数为2
            //如果有右孩子，遍历右孩子，记录标记值 1
            if (ht[p].right!=0) {
                p=ht[p].right;
                cd[cdlen++]='1';
            }
        }
        //如果访问次数为 2，说明左右孩子都遍历完了，返回父结点
        else{
            ht[p].weight=0;
            p=ht[p].parent;
            --cdlen;
        }
    }
}

//打印哈夫曼编码的函数
void printhuffmancode(huffmancode htable,int *w,int n)
{
    printf("huffman code : n");
    for(int i = 1; i <= n; i++)
        printf("%d code = %sn",w[i-1], htable[i]);
}
int main(void)
{
    int w[5] = {2, 8, 7, 6, 5};
    int n = 5;
    huffmantree htree;
    huffmancode htable;
    createhuffmantree(&htree, w, n);
    huffmancoding(htree, &htable, n);
    printhuffmancode(htable,w, n);
    return 0;
}