哈夫曼树你需要了解一下

本文介绍: 哈夫曼树（Huffm an Tree）是一种特殊的二叉树，也被称为最优二叉树。在计算机科学中，它是由权值作为叶子节点构造出来的一种二叉树。哈夫曼树的特点是，对于给定的n个权值，构造出的哈夫曼树具有最小的带权路径长度（WPL）。具体来说，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码。这个变长编码表是通过评估来源符号出现机率的方法得到的。出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码。这样，编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

哈夫曼树（Huffm an Tree）是一种特殊的二叉树，也被称为最优二叉树。在计算机科学中，它是由权值作为叶子节点构造出来的一种二叉树。哈夫曼树的特点是，对于给定的n个权值，构造出的哈夫曼树具有最小的带权路径长度（WPL）。

具体来说，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码。这个变长编码表是通过评估来源符号出现机率的方法得到的。出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码。这样，编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

在构建哈夫曼树时，通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。对于给定的n个权值，构造出的哈夫曼树有n个叶子结点。

哈夫曼树是由哈夫曼在1951年提出的。当时，他在麻省理工学院（MIT）攻读博士学位，并和修读信息论课程的同学面临选择完成学期报告或期末考试。他的导师罗伯特·法诺出的学期报告题目是：查找最有效的二进制编码。

哈夫曼在研究这个问题的过程中，发现无法证明哪个已有编码是最有效的，因此他转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fa no co d in g）的最大弊端──自顶向下构建树。

import java.util.*;

class Node {
    int weight;
    Node left, right;

    Node(int weight) {
        this.weight = weight;
        left = right = null;
    }
}

class HuffmanTree {
    private static final int R = 2; // 哈夫曼树中每个节点的左子树和右子树的数量

    private Node root; // 根节点

    // 构建哈夫曼树
    public void build(int[] weights) {
        int[] queue = new int[weights.length]; // 存储节点的索引
        for (int i = 0; i < weights.length; i++) {
            queue[i] = i + 1; // 将节点的索引加入队列
        }
        PriorityQueue<Node> pq = new PriorityQueue<>(R); // 使用优先队列存储节点
        for (int i = 0; i < weights.length; i++) {
            Node node = new Node(weights[i]); // 创建新节点
            pq.offer(node); // 将节点加入优先队列
            if (pq.size() > R) { // 如果优先队列中的元素数量超过R，则合并两个最小节点
                Node min1 = pq.poll(); // 取出最小节点1
                Node min2 = pq.poll(); // 取出最小节点2
                Node parent = new Node(min1.weight + min2.weight); // 创建父节点
                parent.left = min1; // 设置左子树
                parent.right = min2; // 设置右子树
                pq.offer(parent); // 将父节点加入优先队列
            }
            if (i == weights.length - 1) { // 如果遍历完所有节点，则根节点为当前队列中最大的节点
                root = pq.poll();
            }
        }
    }
}