哈夫曼树

基本介绍

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

相关概念

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

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

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

4.WPL最小的就是赫夫曼树

哈夫曼树创建思路分析

给定一个数组{15,7,26,3,16,20,1,4},将其转换成哈夫曼树

步骤

1. 每一个数据都可以看成一个节点，每一个节点又可以看做二叉树，将所有节点从小到大排列

2. 从排好序的数据中取出根节点权值最小的两颗二叉树

3. 将这两个二叉树组成一颗新的二叉树,新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4. 从原先数据中删除组成新二叉树的节点，然后将这颗新的二叉树放回原先数据中，再以根节点的权值大小再次排序，不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

   代码实现(java代码)

   创建一个节点类，封装数组中的数据

   class Node implements Comparable<Node> {
       Integer value;//封装数组中的值
       Node left;//指向左子节点
       Node right;//指向右子节点
   
       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.compareTo(o.value);
       }
   }

   编写方法，用给定的数组生成哈夫曼树

public class HuffmanTreeDemo {
    public static Node createHuffmanTree(int[] arr) {
        //1.首先利用集合将封装数据的节点存储起来
        List<Node> list = new ArrayList<>();
        for (int i : arr) {
            list.add(new Node(i));
        }
        //2.开始实现前面分析的四步操作
        //只要list中的数据不等于1.就一直操作
        while (list.size() != 1) {
            //四步操作
            //1.将node节点从小到大排列
            //注:因为Node类实现了Comparable接口，所以node对象可以排序
            Collections.sort(list);
            //2.取出两个最小的节点，即第一个和第二个节点
            Node leftNode = list.get(0);
            Node rightNode = list.get(1);
            //3.生成新的父节点,并且连接两个子节点
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
            //4.删除两个子节点，将新的父节点放进集合中
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parent);
        }
        //结束循环时，集合中就只剩下一个节点，将此节点作为哈夫曼树的根节点返回
        return list.get(0);
    }

    /**
     * 哈夫曼树的前序遍历方法
     *
     * @param node 传入的根节点
     */
    public static void preorder(Node node) {
        if (node == null) {
            System.out.println("空树不能遍历");
            return;
        }
        node.preorder();
    }

    //在主方法里面测试代码是否正确
    public static void main(String[] args) {
        //给定数组
        int[] arr = {15, 7, 26, 3, 16, 20, 1, 4};
        //调用方法
        Node root = createHuffmanTree(arr);
        //前序遍历
        preorder(root);
    }
}

测试结果如下

结语

只要能收获甜蜜，荆棘丛中也有蜜蜂忙碌的身影，未来的你一定会感谢现在努力的自己。