哈夫曼树（Java）

柔光的暖阳◎ 2024-04-07 12:45 11阅读 0赞

#### 这里写目录标题 ####

*   *   *  9.7 哈夫曼树
         *  本次哈夫曼树创建教程出自韩顺平的数据结构与算法

#### 9.7 哈夫曼树 ####

**基本介绍**

1）给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度（wpl）达到最小，称这样的二叉树称为最优二叉树，也称为哈夫曼树（Huffmantree）

2）哈夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近。

**哈夫曼树的几个重要概念**

1）路径和路径长度：在一棵树中，从一个节点往下可以达到的孩子或者孙子节点之间的通路，称为路径，通路中分支的数目称为路径长度，若规定根节点的层数为1，则从根节点到L层节点的路径长度为L - 1

2）节点的权及带权路径长度：若将树中中节点赋给一个有着某种含义的数值，则这个数值成为该节点的权，节点的 带权路径长度为：从根节点到该节点之间的路径长度与该节点的 权的乘积

3）树的带权路径长度：树的带权路径长度规定为所有叶子节点的带权路径长度之和，记为WPL（weighted path length），权值越大的节点离根节点越近的二叉树才是最优二叉树

4）WPL最小的就是哈夫曼树

**思路分析：**

1）从小到大进行排序，将每一个数据，每个数据都是一个节点，每个节点可以看出是一颗最简单的二叉树。

2）取出根节点权值最小的两颗二叉树

3）组成一颗新的二叉树，该二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4）再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复1234的步骤，直到数列中，所有的数据都被处理，就得到一颗哈夫曼树。

package com.ldm.HuffmanTree;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    /**
     * @author 梁东明
     * 2022/9/3
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class HuffmanTree {
        
        
        public static void main(String[] args) {
        
            int[] arr = {
        13,7,8,3,29,6,1};
            Node root = createHuffmanTree(arr);
            preOrder(root);
        }
        
        
        //前序对根节点进行遍历
        public static void preOrder(Node root){
        
            if (root != null){
        
                root.preOrder();
            }else {
        
                System.out.println("这是一个空数组。。。");
            }
        }
    
        /**
         * 创建哈夫曼树
         *
         * @param arr 传入的数组
         * @return 返回根节点
         */
        public static Node createHuffmanTree(int[] arr){
        
    
            //先创建list集合，命名为nodes
            List<Node> nodes = new ArrayList<>();
           
            /*看不懂可以用这个普通for循环将arr数组的元素插入list集合中
            for (int i = 0; i < arr.length; i++) {
                nodes.add(new Node(i));
            }*/
            //通过增强for循环将arr数组的元素以节点的形式插入list集合中
            for (int  value : arr) {
        
                nodes.add(new Node(value));
            }
            //循环list集合，直到list集合只剩一个节点退出循环
            while (nodes.size() > 1){
        
                //对list集合排序
                Collections.sort(nodes);
    
                //输出节点
                System.out.println(nodes);
    
                //取出list集合中的最小两颗权值的二叉树取出来
                Node leftNode = nodes.get(0);
                Node rightNode = nodes.get(1);
                //把他们组合成新的二叉树
                Node parent = new Node(leftNode.value + rightNode.value);
                parent.left = leftNode;
                parent.right = rightNode;
                //把处理过的两个二叉树（节点）从list集合删除
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                //把新的二叉树（节点）插入到list集合中
                nodes.add(parent);
            }
            //退出循环之后，list集合就只剩下一个节点，将它返回
            return nodes.get(0);
    
        }
    }
    //创建节点类，实现comparable接口，重写compareTo方法
    class Node implements Comparable<Node>{
        
        public int value;  //权值
        public Node left;  //左节点
        public Node right;  //右节点
    
        //构造器alt+invest（ins）快捷键快速创建，必须是idea
        public Node(int value) {
        
            this.value = value;
        }
        //前序遍历的方法
        public void preOrder(){
        
            System.out.println(this);
            if (this.left != null){
        
                this.left.preOrder();
            }
            if (this.right != null){
        
                this.right.preOrder();
            }
        }
    
        @Override
        public String toString() {
        
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        @Override
        public int compareTo(Node o) {
        
            return this.value - o.value;
        }
    }
    /*
    实现步骤：
    看不懂没关系，这是我自己做的代码步骤，然后自己思考，最后手敲出来运行成功会有一种莫名的自豪感
    你自己也可以总结实现步骤，自己动手写一遍。
    1、在主方法创建数组
    2、创建节点类、实现comparable接口
    3、创建哈夫曼树方法
    4、调用list集合，把数组的值插入list中
    5、对list集合里面的节点进行排序，用 Collection的sort方法排序;
    6、取出集合中权值最小的两颗二叉树
    7、构建新的二叉树
    8、从集合中删除前面取出来的两颗二叉树
    9、将新的二叉树插入回list集合
    10、循环执行步骤6、7、8、9直到list集合只剩一个棵树
    11、返回哈夫曼树的root节点
    12、前序遍历测试
    13、代码执行成功，prefect!!!
     */

#### 本次哈夫曼树创建教程出自韩顺平的数据结构与算法 ####

[数据结构和算法教程][Link 1]，哔哩哔哩详细教程  
在 112-114p.

最后，认识一下，我是小白。努力成为一名合格的程序员。期待与你的下次相遇。

[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=110&spm_id_from=pageDriver&vd_source=027fde985896626031abccc06ce8b031