深入学习二叉树（06）霍夫曼树/哈夫曼编码/最优二叉树

简介

　  哈夫曼树

　　构建原理

       树的节点

       初始化树

       对哈夫曼树编码

       完整的代码(C)

几个名称

路径： 在一棵树中，一个节点到另一个节点之间的通路，称为路径

路径的长度：在一条路径中，每经过一个节点，路径的长度加 1 ，如下图中， C 节点的路径长度为 3

节点的权： 节点出现的频率，每出现一次就+1

节点的带权路径长度：指从根节点到该节点之间的路径与该节点权的乘积

树的带权路径长度： 树中所有叶子节点的带权路径之和

 

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

哈夫曼树

当用 n 个节点(都做叶子节点且都有各自的权值)，试图构建一棵树时，如果这颗树的带权路径长度最小，称为这课树为 “最优二叉树”，有时也叫 “赫夫曼树” 、 “哈夫曼树”

在构建树时，要使的带权路径长度最小，只要遵循一个原则：权重越大的节点离根越近

构建哈夫曼树的过程

1.在 n 个权值中选出两个最小的权值，对应的两个节点组成新的二叉树，且新的二叉树的根节点的权值作为左右孩子权值的和

2.在原有的 n 个权值中删除那 2 个最小的权值，同时将新的权值加入到 n-2 个权值的行列中，依次类推

3.重复上述，直到创建一棵二叉树为止

哈夫曼树节点

key ：代表关键字

weight： key 出现的频率/权重

left/right ：左/右节点

parent :父节点下标

*code ： 代表该节点的哈夫曼编码 

typedef struct node{
    int key;
    int weight;
    int left,parent,right;
    int *code;
}TreeNode;

哈夫曼树初始化

    int data[2][8] = {{1,2,5,8,4},{1,2,5,8,4}};

TreeNode* initialTree(int data[2][5],int n){
    TreeNode *root = (TreeNode *)malloc((2*n-1)*sizeof(TreeNode));
    int i; 
    for(i=0;i<n;i++){
        root[i].left = -1;
        root[i].right = -1;
        root[i].parent = -1;
        root[i].code = NULL;
        root[i].key = data[0][i];
        root[i].weight = data[1][i];
    }
    return root;
} 

二维数组，第一行保存数据key ,第二行保存权重

创建哈夫曼树

//创建树 
TreeNode* createTree(TreeNode *root,int n){
    int i,j,k1,k2;
    for(i=0;i<n-1;i++){
        for(k1=0;k1<n+i&&root[k1].parent!=-1;k1++);
        for(k2=k1+1;k2<n+i&&root[k2].parent!=-1;k2++);
        for(j=k2;j<n+i;j++){
            if(root[j].parent==-1){
                if(root[j].weight<=root[k1].weight){
                    k2 = k1;
                    k1 = j;
                }else if(root[j].weight<=root[k2].weight){
                    k2 = j;
                }
            }
        }
        root[n+i].left = k1;
        root[n+i].right = k2;
        root[n+i].parent = -1;
        root[n+i].code = NULL;
        root[n+i].key = root[k1].key+root[k2].key;
        root[n+i].weight = root[k1].weight + root[k2].weight;
        root[k1].parent = n+i;
        root[k2].parent = n+i;
    }     
    return root;
}

依次从森林中找到最小的2个可用节点，组成新的节点，同时修改这2个节点的parent = -1

对哈夫曼树编码

//对哈弗曼树进行编码 
TreeNode* CreatCode(TreeNode * root,int n){
    printf("哈弗曼树编码:............
");
    int i,parent,temp;
    int *p;
    for(i=0;i<n;i++){
        root[i].code=p=(int *)malloc(n*sizeof(int));
        p[0]=0;
        temp=i;
        while(root[temp].parent!=-1){
            parent=root[temp].parent;
            if(root[parent].left==temp){
                p[++p[0]]=0;
            }else{
                p[++p[0]]=1;
            }
            temp=parent;
        }
     }
 return root;
}

哈夫曼树的 int *code ，指向一个int 数组。数组中每个单元保存 0/1 .如果当前节点在父节点的左边，则保存 0 ，右边则保存 1

由于0/1 的个数是节点的路径，最大不超过叶子个数 N ，因此数组的长度为 N ，同时第一个节点标记 0/1 的个数

 

 输出

 完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
    int key;
    int weight;
    int left,parent,right;
    int *code;
}TreeNode;

//初始化树 
TreeNode* initialTree(int data[2][5],int n){
    TreeNode *root = (TreeNode *)malloc((2*n-1)*sizeof(TreeNode));
    int i; 
    for(i=0;i<n;i++){
        root[i].left = -1;
        root[i].right = -1;
        root[i].parent = -1;
        root[i].code = NULL;
        root[i].key = data[0][i];
        root[i].weight = data[1][i];
    }
    return root;
} 

//对哈弗曼树进行编码 
TreeNode* CreatCode(TreeNode * root,int n){
    printf("哈弗曼树编码:............
");
    int i,parent,temp;
    int *p;
    for(i=0;i<n;i++){
        root[i].code=p=(int *)malloc(n*sizeof(int));
        p[0]=0;
        temp=i;
        while(root[temp].parent!=-1){
            parent=root[temp].parent;
            if(root[parent].left==temp){
                p[++p[0]]=0;
            }else{
                p[++p[0]]=1;
            }
            temp=parent;
        }
     }
 return root;
}
 

//创建树 
TreeNode* createTree(TreeNode *root,int n){
    int i,j,k1,k2;
    for(i=0;i<n-1;i++){
        for(k1=0;k1<n+i&&root[k1].parent!=-1;k1++);
        for(k2=k1+1;k2<n+i&&root[k2].parent!=-1;k2++);
        for(j=k2;j<n+i;j++){
            if(root[j].parent==-1){
                if(root[j].weight<=root[k1].weight){
                    k2 = k1;
                    k1 = j;
                }else if(root[j].weight<=root[k2].weight){
                    k2 = j;
                }
            }
        }
        root[n+i].left = k1;
        root[n+i].right = k2;
        root[n+i].parent = -1;
        root[n+i].code = NULL;
        root[n+i].key = root[k1].key+root[k2].key;
        root[n+i].weight = root[k1].weight + root[k2].weight;
        root[k1].parent = n+i;
        root[k2].parent = n+i;
    }     
    return root;
}

//输出 
void print(TreeNode *root,int n){
    int i,j;
    for(i=0;i<n;i++){
        printf("[%d] key:%3d  , left[%d] , parent[%d] , right[%d] ",i,root[i].key,root[i].left,root[i].parent,root[i].right); 
        for(j=root[i].code[0];j>0;j--){
            printf("%d",root[i].code[j]);
        }
        printf("
");
    }
}

int main(void){
    int data[2][5] = {{1,2,5,8,4},{1,2,5,8,4}};
    TreeNode *root = initialTree(data,5);
    root = createTree(root,5);
    root = CreatCode(root,5);
    print(root,5); 
    return 0;
}