【数据结构】哈夫曼树

1、基本概念

• 路径：一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径，如图：
  
  从根节点1到叶子节点4的路径:1,2,4

• 路径长度：在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度，还是上图，根节点1到叶子结点4的路径经过了2个边，也就是说，若规定根节点的层数为1，则从根节点到N层的结点的的路径长度为：N-1

• 结点的带权路径长度：树的每一个结点，都可以拥有自己的“权重”（Weight），权重在不同的算法当中可以起到不同的作用。结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积,还是上图，如结点4的权重是10，那结点4的带权路径长度就是10*2 = 20。

• 树的带权路径长度：在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。

2、什么是哈夫曼树？

• 给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
• 哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

• WPL最小的就是哈夫曼树

3、哈夫曼树构建图解

• 给定一个数列：

• 第一步：把每一个叶子结点，都当做树一颗独立的树（只有根结点的树），同时建个辅助队列，按照权值从小到大存储了所有叶子结点，用于后续哈夫曼树的构建辅助。

• 第二步：选择当前权值最小的两个结点，生成新的父结点，借助辅助队列，我们可以找到权值最小的结点1和4，并根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和。

• 第三步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列

也就是从队列中删除1和4，插入5，并且仍然保持队列的升序。

• 第四步：继续选择当前权值最小的两个结点，生成新的父结点。

• 第五步：继续移除上一步选择的两个最小结点，把新的父节点加入队列。

• 第六步：继续选择当前权值最小的两个结点，生成新的父结点。

• 第七步：继续移除上一步选择的两个最小结点，把新的父节点加入队列。

• 第八步：继续选择当前权值最小的两个结点，生成新的父结点。

• 第九步：继续移除上一步选择的两个最小结点，把新的父节点加入队列。

• 第十步：继续选择当前权值最小的两个结点，生成新的父结点。

• 此时，队列中仅有一个结点，说明整个森林已经合并成了一颗树，而这棵树就是我们想要的哈夫曼树：

4、代码实现哈夫曼树

• 树节点

package com.data.structure.tree;

/**
 * 树节点
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/7/20
 */
public class Node implements Comparable<Node>{
    /**
     * 节点权值
     */
    int value;
    /**
     * 指向左子结点
     */
    Node left;
    /**
     * 指向右子节点
     */
    Node right;

    public Node(int value){
        this.value = value;
    }

    /**
     * 前序遍历,先输出父结点，再遍历左子树和右子树
     */
    public  void preOrder(){

        System.out.println(this);

        if(null != this.left){
            this.left.preOrder();
        }
        if(null != this.right){
            this.right.preOrder();
        }
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }

    @Override
    public  String toString(){
        return "Node[value="+value+"]";
    }



}

• 哈夫曼树

package com.data.structure.tree;

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

/**
 * 哈夫曼树
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/7/20
 */
public class HuffmanTree {


    public static void main(String[] args) {
        int arr[] = {2,3,7,9,18,25};
        Node root = createHuffmanTree(arr);
        preOrder(root);
    }
    /**
     * 前序遍历
     * @param root
     */
    public static void preOrder(Node root){
        if (null != root){
            root.preOrder();
        }else {
            System.out.println("该树为空！");
        }
    }

    /**
     * 构建哈夫曼树
     * @param arr
     * @return
     */
    public static Node createHuffmanTree(int[] arr){
        List<Node> nodes = new ArrayList<>();

        for(int value : arr){
            nodes.add(new Node(value));
        }

        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);
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}

本文地址：https://blog.csdn.net/aaa_bbb_ccc_123_456/article/details/107462776