哈夫曼树（三）Java详解

哈夫曼树分别通过C和C++实现。本章给出了哈夫曼树的java版本。

目录
1。哈夫曼树简介
2。哈夫曼树图文分析
3。哈夫曼树的基本操作
4。哈夫曼树完整源代码

转载请注明出处：http://www.sychzs.cn/skywang12345/

更多内容：数据结构与算法系列目录

哈夫曼树简介

哈夫曼树，中文名称为哈夫曼树或哈夫曼树，它是最优二叉树。

定义：给定n个权重作为n个叶子节点，构造一棵二叉树。如果树的加权路径长度达到最小值，则该树称为哈夫曼树。 这个定义涉及几个不熟悉的概念。下面是哈夫曼树。我们看图来回答一下吧。

(01) 路径和路径长度

定义：在树中，从一个节点向下可以到达的子节点或孙节点之间的路径称为路径。路径中的分支数量称为路径长度。如果指定根节点的层数为1，则从根节点到第L层节点的路径长度为L-1。
示例 ：100 和 80 的路径长度为 1，50 和 30 的路径长度为 2，20 和 10 的路径长度为 3。

(02) 节点权重和加权路径长度

定义：如果树中的某个节点被赋予了一个具有一定意义的值，那么这个值就称为该节点的权重。节点的带权路径长度为：从根节点到该节点的路径长度与该节点的权重的乘积。
示例：节点20的路径长度为3，其加权路径长度=路径长度*权重=3*20=60。

(03) 树的加权路径长度

定义：树的加权路径长度指定为所有叶子节点的加权路径长度之和，记为WPL。
？ 10 = 100 + 160 + 60 + 30 = 350。

比较下面两棵树

上面的两棵树都是以{10,20,50,100}为叶子节点的树。

左边的树 WPL=2*10 + 2*20 + 2*50 + 2*100 = 360
右边的树WPL=350

WPL > 右侧树的WPL。除了上面两个例子之外，你还可以计算其他情况，但实际上右边的树是{10,20,50,100}对应的哈夫曼树。至此，你应该对哈夫曼树的概念有了一定的了解。我们来看看如何构造哈夫曼树。

哈夫曼树的图解分析

假设有n个权重，构建的哈夫曼树有n个叶子节点。 n个权重分别设置为w₁，w₂，...，w_n。哈夫曼树的构造规则是：

1。将 w₁、w₂、…、w_n 想象成一个有 n 棵树的森林（每棵树只有一个节点）；
2。选择森林中根节点权值最小的两棵树合并，作为新树的左右子树，新树的根节点权值就是它的左右子树。树根节点的权重之和；
3。从森林中删除选定的两棵树，并将新树添加到森林中；
4。重复步骤(02)和(03)，直到森林中只剩下一棵树，这就是得到的哈夫曼树。

以{5,6,7,8,15}为例构建哈夫曼树。

第 1 步：创建一片森林。森林里有 5 棵树。这5棵树的权重分别是5、6、7、8和15。
步骤2：在森林中，选择根节点权重最小的两棵树（5和6）进行合并，并将它们作为新树的左右子树（没关系）谁是左或右），这里我们选择较小的一个作为左孩子），新树的权重是左右孩子权重之和。即，新树的权重为11。然后，从森林中删除“树5”和“树6”，并向森林中添加一棵新树（树11）。
步骤3：在森林中，选择根节点权重最小的两棵树（7和8）进行合并。生成的新树的权重为 15。然后，从森林中删除“Tree 7”和“Tree 8”，并将一棵新树（Tree 15）添加到森林中。
步骤4：在森林中，选择根节点权重最小的两棵树（11和15）进行合并。得到的新树的权重为26。然后，将“树11”和“树15”从森林中移除，并向森林中添加一棵新树（树26）。
第5步：在森林中，选择根节点权重最小的两棵树（15和26）进行合并。得到的新树的权重为41。然后，从森林中移除“树15”和“树26”，并在森林中添加一棵新树（树41）。
此时，森林里只有一棵树（树41）。这棵树就是我们需要的哈夫曼树！

哈夫曼树的基本操作

哈夫曼树的重点是如何构造哈夫曼树。本文在构建Huffman时，使用了之前介绍过的“（二叉堆）最小堆”。下面解释哈夫曼树。

1。基本定义

公共类 HuffmanNode 实现 Comparable、Cloneable {受保护的 int 键； // 重量
    受保护的 HuffmanNode 左； // 左孩子
    保护 HuffmanNode 权利； // 右孩子
    受保护的 HuffmanNode 父节点； // 父节点

    protected HuffmanNode(int key, HuffmanNode left, HuffmanNode right, HuffmanNodeparent) {
        this.key = 键；
        this.left = 左；
        this.right = 正确；
        this.parent = 父级；
    }

    @覆盖
    公共对象克隆（）{
        对象 obj=null;

        尝试 {
            obj = (HuffmanNode)super.clone();//Object中的clone()标识了要复制的是哪个对象。
        } catch(CloneNotSupportedException e) {
            System.out.println(e.toString());
        }

        返回对象；
    }

    @覆盖
    公共 int 比较（对象 obj）{
        返回 this.key - ((HuffmanNode)obj).key;
    }
}

HuffmanNode 是哈夫曼树的节点类。

公共课霍夫曼{

    私有 HuffmanNode mRoot； // 根节点

    ...
}

Huffman是哈夫曼树对应的类。它包含哈夫曼树的根节点以及哈夫曼树的相关操作。

2。构建哈夫曼树

/*
 * 创建哈夫曼树
 *
 * @param权重数组
 */
公共霍夫曼（int a[]）{
    HuffmanNode 父节点 = null;
    MinHeap 堆；

    // 创建数组a对应的最小堆
    堆 = new MinHeap(a);

    for(int i=0; i