赫夫曼树

赫夫曼树

• 定义：WPL最小的二叉树就是赫夫曼树，WPL全称weight path length，中文意思是树的带权路径长度，规定为所有叶子节点的带权路径长度之和，计算方法是权值*带权路径长度

权值，也就是给某一节点赋予的值大小

带权路径长度，为权值所在层数-1

• 如果该树的wpl最小，则是最优二叉树

• 代码：

package com.guodaxia.huffman;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 哈夫曼树创建
 * @ author Guo daXia
 * @ create 2022/11/28
 */
public class HuffmanDemo {
    public static void main(String[] args) {
        int[] arr={13,8,7,3};//排序后：{3,7,8,13}
        Node huffmanTree = createHuffmanTree(arr);
        preOrder(huffmanTree);
    }
    /**
     * 方法：创建赫夫曼树
     * @param arr 二叉树
     * @return  返回一个创建好的赫夫曼树的root
     */
    public static Node createHuffmanTree(int[] arr){

        //使用Java集合存储每个元素
        //1.遍历数组
        //2.数组的每个元素构成一个个Node
        //3.将Node放入到ArrayList中
        ArrayList<Node> nodes = new ArrayList<>();
        for (int value:arr){
            Node node = new Node(value);
            nodes.add(node);
        }
        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.leftNode=leftNode;
            parent.rightNode=rightNode;
            //删除两个旧节点(从ArrayList中）
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将parent加入到ArrayList中
            nodes.add(parent);
        }
        //此时，剩下一颗 二叉树，即为哈夫曼树
        return nodes.get(0);//返回root
    }
    //前序遍历方法
    public static void preOrder(Node root){
        if (root!=null){
            root.preOrder();
        }else {
            System.out.println("空树，不能遍历！");
        }
    }
}
//节点类
class Node implements Comparable<Node>{
    Node leftNode;
    Node rightNode;
    int value;//节点权值

    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(){
        //先输出root节点
        System.out.println(this);
        if (this.leftNode!=null){
            this.leftNode.preOrder();
        }
        if (this.rightNode!=null){
            this.rightNode.preOrder();
        }
    }
}

• 运行结果：

Node{value=31}
Node{value=13}
Node{value=18}
Node{value=8}
Node{value=10}
Node{value=3}
Node{value=7}

• 总结：
  1. 哈夫曼树好比一串葡萄，所有的叶子节点是原二叉树的节点，通过将叶子节点权值最大的放在首层，将第二大权值放在第二层，直到所有叶子节点挂上。
  2. 哈夫曼树计算机运算快
  3. wpl为构建出哈夫曼树的除了叶子节点的权值之和