树---赫夫曼树

缺乏、安全感 2023-07-07 08:29 93阅读 0赞

## 赫夫曼树 ##

几个概念：

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

WPL最小的就是赫夫曼树

#### 赫夫曼树的创建 ####

将数列 \{13, 7, 8, 3, 29, 6, 1\}转成一颗赫夫曼树的过程：

1.  将数列元素从小到大排序
2.  取出最小的两个元素，生成一棵新的二叉树，取出的两个元素作为新二叉树的子节点（一般权重小的作为子节点），根节点的权重为子节点权重之和
3.  将处理过的两个元素从列表中删除，将新的根节点加入列表
4.  重复1~3步骤，直到列表中只有一个元素，该元素就是赫夫曼树的根节点

图解：  
数列排序后：\{1, 3, 6, 7, 8, 13, 29\}  
![在这里插入图片描述][20200222091145545.png]  
数列排序后：\{4, 6, 7, 8, 13, 29\}  
![在这里插入图片描述][20200222091159333.png]  
数列排序后：\{7, 8,10, 13, 29\}  
![在这里插入图片描述][20200222091433205.png]  
数列排序后：\{10, 13, 15, 29\}  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]  
数列排序后：\{15, 23, 29\}  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]  
数列排序后：\{29,38\}  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 2]  
代码实现：

public class HuffmanTreeDemo { 
        public static void main(String[] args) { 
            int[] arr = { 13, 7, 8, 3, 29, 6, 1};
            Node root = createHuffmanTree(arr);
            System.out.println(root);
        }
    
    	// 构建赫夫曼树
        public static Node createHuffmanTree(int[] arr) { 
            if(0 == arr.length) { 
                return null;
            }
            //将数组元素变成Node放入集合中
            List<Node> nodes = new ArrayList<>();
            for (int val : arr) { 
                nodes.add(new Node(val));
            }
    
            while(nodes.size() > 1) { 
                //将集合中的元素从小到大排序
                Collections.sort(nodes);
    
                //取出并删除最小的两个元素
                Node leftNode = nodes.remove(0);
                Node rightNode = nodes.remove(0);
    
                //构建一个新的二叉树
                Node parrent = new Node(leftNode.val + rightNode.val);
                parrent.left = leftNode;
                parrent.right = rightNode;
    
                //将新节点加入集合中
                nodes.add(parrent);
            }
    
            return nodes.get(0);
        }
    
    }
    
    
    class Node implements Comparable<Node>{ 
        int val;
        Node left;
        Node right;
    
        public Node(int val) { 
            this.val = val;
        }
    
        @Override
        public int compareTo(Node o) { 
            //从小到大排序
            return this.val - o.val;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "val=" + val +
                    '}';
        }
    }

[20200222091145545.png]: https://img-blog.csdnimg.cn/20200222091145545.png
[20200222091159333.png]: https://img-blog.csdnimg.cn/20200222091159333.png
[20200222091433205.png]: https://img-blog.csdnimg.cn/20200222091433205.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200222091729651.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200222091850443.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200222091936273.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70