本文共 2690 字，大约阅读时间需要 8 分钟。

哈夫曼树(最优二叉树)

一.算法步骤与特点总结

①以权值作为根节点构建n棵二叉树，组成森林

二.代码实现

第一步:定义节点

//定义节点class Node{    int weight;//节点的权重    int r_link;//右子节点    int l_link;//左子节点    int p_link;//父节点    char c;    public Node()    {        this.l_link=0;        this.p_link=0;        this.r_link=0;    }    //初始化    public Node(int weight,char c)    {        this.l_link=0;        this.p_link=0;        this.r_link=0;        this.weight=weight;        this.c = c;    }}

第二步:构建哈夫曼树并实现功能

//构建哈夫曼树class Solution {    //采用静态三叉链表    Node node[];    char strs[];    int rates[];    int min_index,second_min;    Map
   
     map ;//用来存储字符对应的二进制串    //strs包含了所有出现字符,rates表示每一个字符出现的频率    public Solution(char[] strs,int rates[])    {        this.rates = rates;        this.strs = strs;        //这里我们使用索引为1-2*strs.length-1的节点        this.node=new Node[2*strs.length];        for(int i=1;i<2*strs.length;i++)        {            if(i<=strs.length)//前n个字符将字符与权重存进去                this.node[i] = new Node(rates[i-1],strs[i-1]);            else//后n个字符用下面的                this.node[i]=new Node();        }    }		//构建haffunman树    private  void BuildHaffuman()    {        for(int i = strs.length+1;i<=2*strs.length-1;i++)        {            //选择最小的与次小的            select(i-1);            node[min_index].p_link=i;            node[second_min].p_link=i;            node[i].r_link=min_index;            node[i].l_link=second_min;            node[i].weight=node[min_index].weight+node[second_min].weight;        }    }    //传入参数表示从1到N节点的权值最小的两个树     void select(int N)    {        int min_weight,second_min_weight;        int index=1;        //寻找索引最小的两个树        while(node[index].p_link!=0)            index++;        min_index=index;        min_weight=node[min_index].weight;        index++;        while(node[index].p_link!=0)            index++;        second_min=index;        second_min_weight=node[second_min].weight;        //将找到的最小的结果比较，如果犯了则交换        if(second_min_weight
    
     min_weight&&node[i].weight
     
       encodeStr()    {        Map
      
        map = new HashMap<>();        BuildHaffuman();        for(int i=0;i
      
     
    
   

第三步:测试

import org.junit.Test;import java.util.HashMap;import java.util.Map;public class Math {    @Test    public void Test() {        char strs[]=new char[]{
  'a','b','c','d'};        int rates[]=new int[]{
  1,3,5,2};        Solution s =  new Solution(strs,rates);        Map
   
     characterStringMap = s.encodeStr();        System.out.println(characterStringMap);        System.out.println(s.decodeStr("abccd"));    }}
   

转载地址：http://splzi.baihongyu.com/