赫夫曼树

冷不防 2022-11-07 14:44 157阅读 0赞

# 一：赫夫曼树的特点 #

1.  给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，**若该树的带权路径长度(wpl)达到最小**，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。 
2.  赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近

## 1：赫夫曼树的几个概念 ##

1.  **路径和路径长度**：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。
2.  **中分支的数目称为路径长度**。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1。
3.  **结点的权及带权路径长度**：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。**结****点的带权路径长度为**：从根结点到该结点之间的路径长度与该结点的权的乘积 
4.  树的带权路径长度：树的带权路径长度规定为**所有叶子结点的带权路径长度之和**，记为 WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。 
5.  WPL 最小的就是赫夫曼树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

## 2：赫夫曼树创建思路图解  ##

1.  从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树。
2.  取出根节点权值最小的两颗二叉树。
3.  组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和。
4.  再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][]

## 3：代码实现 ##

Node实体类

package com.tree.huffman;
    
    /**
     * @author lizhangyu
     * @date 2021/3/13 15:47
     */
    public class Node implements Comparable<Node>{
    
        /**
         * 节点的权值
         */
        public int value;
        /**
         * 左子节点
         */
        public Node left;
        /**
         * 右子节点
         */
        public Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        /**
         * 前序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }
    }

HuffManTree实体类

package com.tree.huffman;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    /**
     * @author lizhangyu
     * @date 2021/3/13 16:00
     */
    public class HuffManTree {
    
        public static void main(String[] args) {
    
            int[] arr = {7,8,4,6,5,9};
            Node root = createHuffManTree(arr);
    
            preOrder(root);
        }
    
        /**
         * 前序遍历
         * @param root
         */
        private static void preOrder(Node root) {
            if (root != null) {
                root.preOrder();
            }else {
                System.out.println("是空树，不能遍历");
            }
        }
    
        /**
         * 创建赫夫曼树
         * @param arr
         * @return
         */
        public static Node createHuffManTree(int[] arr) {
            //为了便于操作，将int[]转为List类型
            List<Node> nodes = new ArrayList<>();
            for (int val : arr) {
                nodes.add(new Node(val));
            }
    
            while (nodes.size() > 1) {
                //从小到大进行排序
                Collections.sort(nodes);
    
                //取出权值最小的节点（二叉树）
                Node leftNode = nodes.get(0);
                //取出权值第二小的节点
                Node rightNode = nodes.get(1);
    
                //构建一个新的二叉树（二叉树）
                Node parent = new Node(leftNode.value + rightNode.value);
                parent.left = leftNode;
                parent.right = rightNode;
    
                //将处理过的二叉树剔除掉
                nodes.remove(leftNode);
                nodes.remove(rightNode);
    
                //将parent加入到nodes
                nodes.add(parent);
            }
    
            return nodes.get(0);
        }
    }

运行结果：

Node{value=39}
    Node{value=17}
    Node{value=8}
    Node{value=9}
    Node{value=22}
    Node{value=9}
    Node{value=4}
    Node{value=5}
    Node{value=13}
    Node{value=6}
    Node{value=7}

## 4：赫夫曼的应用 ##

赫夫曼编码可以在数据压缩方面进行应用，而且赫夫曼编码是无损方案处理。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/4e1e0b140099417fbd8029d6e9d841fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: /images/20221023/af1cc45e11d1439680b6d56eed34d265.png