贪心算法-构造哈夫曼数及生成哈夫曼编码,编程实现

哈夫曼树

1.概念：

• 给定n个权值最为n个叶子的节点，构建成一颗二叉树。如果次树的带权路径长度最小，则称此二叉树为最优二叉树，也叫哈夫曼树。
  
• WLP：带权路径长度
  
  
  
  • 公式：
    [img=45%,45%/]https://img2022.cnblogs.com/blog/2291187/202211/2291187-20221120131450130-1355213385.png[/img]
    
  • Wk:第k个叶子的节点权值
    
  • Lk:根节点到第k个叶子的节点长度
    
  
  

例如下列二叉树：

• 给定4个叶子节点，权值分别为{2，3，5，8}，可以构造出4中形状不同的二叉树，但它们的带权路径长度可能不同。
  

[img=45%,45%/]https://img2022.cnblogs.com/blog/2291187/202211/2291187-20221120131621096-707303050.png[/img]如上图可看出：1、最后两个树的带权路径长度相同且也是最小的，所以可看作哈夫曼树
​                                                  2、权值最小的节点越靠下，越大越靠近根节点
2.构建哈夫曼树

（1）、在{2，3，5，8}这几个节点看作叶子节点（即后面没有子节点）
​                        [img=45%,45%/]https://img2022.cnblogs.com/blog/2291187/202211/2291187-20221120131810637-1862349395.png[/img]
（2）、在这几个节点中选出权值最小和次小的两个节点。构成一个新二叉树（最小为左字节的、次小为右子节点），新二叉树的权值为这两个权值之和.
[img=35%,35%/]https://img2022.cnblogs.com/blog/2291187/202211/2291187-20221120131911264-1161635956.png[/img]（3）、删除已经使用过的节点。将新创建的节点加入到还没被使用过的节点集合中，找出最小和次小的节点权值。又构成一颗新的二叉树。
[img=45%,45%/]https://img2022.cnblogs.com/blog/2291187/202211/2291187-20221120132008656-121294881.png[/img]（4）、重复(2)的操作
​                [img=45%,45%/]https://img2022.cnblogs.com/blog/2291187/202211/2291187-20221120132100035-1281422288.png[/img]
（5）、重复上面操作：删除已使用的节点，将新的节点加入未使用节点的集合中，发现只有一个节点，其权值为18.则此哈夫曼树创建完成，根节点权值为18.
代码如下：

1. import java.util.ArrayList;
2. import java.util.Collections;
3. import java.util.List;
5. /**
6. * 构造哈夫曼树
7. */
8. public class test1 {
9.     public static void main(String[] args) {
10.         int[] arr={2,3,5,8};
11.         //调用自定义的哈夫曼树方法，生成哈夫曼树
12.         hafmantree(arr);
13.     }
15.     /**
16.      * ,构造哈夫曼数方法
17.      *
18.      * @param arry
19.      */
20.     public static void hafmantree(int[] arry) {
21.         //创建集合用于存放节点值
22.         List<Node> nlis = new ArrayList<Node>();
23.         //遍历集合
24.         for (int value : arry) {
25.             //将每个数组元素看作Node节点对象，并存入list集合内
26.             nlis.add(new Node(value));
27.         }
28.        /*
29.        由于集合中存入的是一个个的Node对象，而Node对象已经被我们声明成了按照从小到大的可排序对象。
30.        所以这里我们为可以通过Collections工具类中的sort方法进行排序
31.         */
32.         //循环条件：只有一个节点，即最终根节点
33.         while (nlis.size() > 1) {
34.             Collections.sort(nlis);
35.             //查看集合中还未被使用的节点
36.             System.out.println(nlis);
37.             //到了这里说明集合中的所有节点（权值）都是按照从小到大的顺序
38.             //获取最小的节点值（二叉树左节点）:子节点
39.             Node lileft = nlis.get(0);
40.             //获取第2小的节点值（二叉树右节点）：子节点
41.             Node lireght = nlis.get(1);
42.        /*创建新的Node节点对象（二叉树）:
43.             此节点对象是最小的两个节点之和所生成的最新的节点。三个节点可以看成一个二叉树，即：
44.              根节点(insternode对象)、左子节点(lileft.value)、右子节点(lireght.value)
45.         */
46.             Node insternode = new Node(lileft.value + lireght.value);
47.             //此二叉树的左节点
48.             insternode.left = lileft;
49.             //此二叉树的右节点
50.             insternode.right = lireght;
51.             //删除已经被处理过的节点
52.             nlis.remove(lileft);
53.             nlis.remove(lireght);
54.             //将最新的节点加入到list集合中
55.             nlis.add(insternode);
56.             //重新对最新的list数组进行排序
57.             Collections.sort(nlis);
58.         }
59.         //查看最终根节点
60.         System.out.println(nlis);
61.     }
64. }
67. /**
68. * ,构造哈夫曼数节点类,
69. * 此类也可以看成一个二叉树：根节点(Node对象)、左节子点(left)、右字节点(right)
70. * 实现Comparable接口：说明此类是可通过Collections工具类排序的，
71. */
72. class Node implements Comparable<Node> {
73.     int value;  //每个节点的值（权值）
74.     Node left;   //每个二叉树的左指向节点
75.     Node right;   //每个二叉树的右指向节点
77.     //构造方法，这里只需要初始化value实例变量，用于对象的赋值，而 left 与 right 本身就是此对象，可直接用于value赋值
78.     public Node(int value) {
79.         this.value = value;
80.     }
82.     @Override
83.     public String toString() {
84.         return "Node{" +
85.                 "value=" + value +
86.                 '}';
87.     }
89.     //支持从小到大排序
90.     @Override
91.     public int compareTo(Node o) {
92.         return this.value - o.value;
93.     }
94. }

复制代码

结果：
[img=45%,45%/]https://img2022.cnblogs.com/blog/2291187/202211/2291187-20221120132248314-1579160233.png[/img]3.构建哈夫曼编码

• 这里是对一段字符串进行哈夫曼编码，所以需要先处理字符串
  
• 在哈夫曼树的基础上，规定了路径编码。
  
• 遍历已经创建好了的哈夫曼树，从它的根节点遍历次树到叶子节点，左子路径编码：0  、右子路径编码：1
  

1. import java.util.*;
3. /**
4. * 构造哈夫曼数+生成哈夫曼编码,编程实现。
5. */
6. public class test1 {
7.     public static void main(String[] args) {
8.         //需要转换为哈夫曼编码的字符串
9.         String valus="asdsgddbhj ,sjsh";
10.         //将字符串存以node对象存入list集合中
11.         List<Node> list = ListAndNode(valus);
12.         //生成哈夫曼树
13.         Node node = HFMTree(list);
14.         //得到哈夫曼编码
15.         HFMTable(node,"",andindex);
16.         System.out.println(yezijied);   //{32=1010, 97=1011, 98=1100, 115=01, 100=111, 103=1101, 104=001, 106=100, 44=000}
18.     }
20. /*
21. 第四步：
22. 创建哈夫曼编码表：将叶子节点以0、1表示。0===》向左子节点走。1===》向右子节点走
23.     yezijied:存放叶子节点对应的哈夫曼编码。此集合作业与全局
24.     andindex：拼接编码。(拼接对应的0或1，形参最终的哈夫曼编码)
25. */
27.     static Map<Byte,String> yezijied=new HashMap<>();
28.     static  StringBuilder andindex=new StringBuilder();
30.     /**
31.      *
32.       * @param node：节点
33.      * @param index：路径表示：左路径为0.右路劲为1
34.      * @param sub：拼接路径，使其成为对应叶子节点的哈夫曼码
35.      */
36. public static void HFMTable(Node node,String index,StringBuilder sub){
37.     //
38.     StringBuilder gitindex=new StringBuilder(sub);
39.     //拼接路径
40.     gitindex.append(index);
41.     //如果节点为空就不需要处理
42.     if (node!=null) {
43.         //如果当前节点不是叶子节点
44.         if (node.value == null) {
45.             //如果节点不为空就递归其左边节点。并设置向左为0
46.             HFMTable(node.left, "0", gitindex);
47.             //如果节点不为空就递归其右边节点。并设置向右为1
48.             HFMTable(node.right, "1", gitindex);
49.         } else {
50.             //为叶子节点就将其存入map集合中
51.             yezijied.put(node.value, gitindex.toString());
52.         }
54.     }
55. }
57.     /*
58.     第三步：
59.     @param nodes:已经存入list集合中的Node节点
60.     创建字符串的哈夫曼树结构
61.      */
62.     public static Node HFMTree(List<Node> nodes){
63.         //循环条件：节点数必须大于1.如果等于1就是一个节点(根节点),没有分支
64.         while (nodes.size()>1){
65.             //排序list集合，根据权值(节点个数)从小到大排序
66.             Collections.sort(nodes);
68.             /*
69.             创建一个二叉树：
70.             feiyezijied:根节点
71.             nodeleft：左子节点
72.             noderight：右子节点
73.              */
74.             //得到权值最小的两个节点.这两个节点分别可看作左右两个子节点
75.             Node nodeleft = nodes.get(0);
76.             Node noderight = nodes.get(1);
77.             //创建新的Node对象：这可以想象为两个叶子节点生成的根节点，
78.             // 由于哈夫曼数的原理，需要编码的值是叶子节点，而叶子节点上的父节点只是通过叶子节点虚拟创建的节点，
79.             // 是为了形成一整颗完整的树。所以它是没有字符串原始值，，其可用两个字节的权值之和标记
80.             Node feiyezijied=new Node(null,nodeleft.quanzhi+noderight.quanzhi);
81.             //Node对象的左字节点
82.             feiyezijied.left=nodeleft;
83.             //Node对象的右字节点
84.             feiyezijied.right=noderight;
86.             //删除原集合中的以使用的节点对象.即上面已经每次获得的集合中两个最小的节点
87.             nodes.remove(nodeleft);
88.             nodes.remove(noderight);
90.             //将新创建的Node节点加入list集合中
91.             nodes.add(feiyezijied);
92.             //重新对list集合排序
93.             Collections.sort(nodes);
94.         }
95.         //返回最终根节点
96.         return nodes.get(0);
97.     }
101.     /*
102.     第二步：
103.     @param valus:传入需要编码的字符串，将其变成节点
104.     将需要编码的字符串，每个原始值(ASCIIM码)以节点(Node)对象形式传入list集合中。
105.     而节点对象Node初始化了value与quanzhi，所以节点对象是包括这两个值，所以将每个节点对象当作一个map.
106.     设k=value、v=quanzhi
107.      */
108.     public static List<Node> ListAndNode(String valus){
109.         //将字符对象存入byte数组。
110.         byte[] bytes = valus.getBytes();
111.         //创建List集合
112.         List<Node> nodes=new ArrayList<>();
113.         //创建Map集合
114.         Map<Byte,Integer> node=new HashMap<>();
115.         //遍历bytes数组，得到每个字符串的原始值
116.         for (byte by:bytes){
117.             //先试着通过传入的第一个k获取v
118.             Integer index = node.get(by);
119.             //如果map集合中此原始值对应的个数还没有
120.             if (index==null){
121.                 node.put(by,1);
122.             }else {
123.                 node.put(by,index+1);
124.             }
125.         }
126.         //遍历map集合，并将每次遍历的元素，以Node对象的形式存入list集合
127.         for (Map.Entry<Byte,Integer> n:node.entrySet()){
128.             nodes.add(new Node(n.getKey(),n.getValue()));
129.         }
130.         //最后返回此list集合
131.         return nodes;
132.     }
134. }
136.   /*
137.   第一步：
138.     节点类:其本身可可看作一个概念性的二叉树
139.     Node对象本身可看作是一个二叉树的根节点
140.     实现Comparable接口：泛型规定此接口作用与此Node节点，说明此类是可排序的，通过' Collections.sort()'
141.      */
143. class Node implements Comparable<Node>{
144.     Byte value;     //原始值：字符本身的ASCIIM码。因为一段字符串中有许多相同的字符，但相同字符却对应这一个ASCIIM码
145.     int quanzhi;    //此字符value在一段字符串中出现的次数
146.     Node left;      //Node对象看作是二叉树的根节点，那么这就是此二叉树的左子节点
147.     Node right;     //Node对象看作是二叉树的根节点，那么这就是此二叉树的右边子节点
149.     //构造器初始化 value 、quanzhi。
150.     public Node(Byte value, int quanzhi) {
151.         this.value = value;
152.         this.quanzhi = quanzhi;
153.     }
155.     //重写toString：因为我们需要拿到这两个值
156.     @Override
157.     public String toString() {
158.         return "Node{" +
159.                 "value=" + value +
160.                 ", quanzhi=" + quanzhi +
161.                 '}';
162.     }
164.     //实现Comparable接口中的方法：手动设置排序规则
165.     @Override
166.     public int compareTo(Node o) {
167.         //设置为通过权值从小到大排序
168.         return    this.quanzhi-o.quanzhi;
169.     }
171.     //前序遍历
172.     public void qxbl(){
173.         //先输出当前节点，也就是根节点
174.         System.out.println(this);
175.         //如果左子节点不是null节点，就递归遍历输出左子节点.null表示不是叶子节点
176.         if (this.left!=null){
177.             this.left.qxbl();
178.         }
179.         //同样递归右子节点
180.         if (this.right!=null){
181.             this.right.qxbl();
182.         }
183.     }
184. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！