本文共 4126 字，大约阅读时间需要 13 分钟。

赫夫曼数（哈夫曼树）

基本介绍

1. 定义：给定n个权值作为n个叶子节点的值，构造一棵二叉树，若该树的带路径长度达到最小，这样的二叉树称之为最优二叉树，也称之为霍夫曼树。

• 霍夫曼树是带权路径长度最短的书，权值较大的结点离根较近。

3. 相关定义：

• 路径：在一个树中，从一个结点往下到达另外一个结点之间的通路，称之为路径
• 路径长度：通过分支的数目称之为路径长度。如：若规定根节点的层数为1，则从根节点到第L层结点路径长度为L - 1.
• 结点的权：给树中结点赋一个有着某种含义的数值，则该数值称之为该节点的权。
• 结点的带权路径长度：从根节点到该节点之间的路径与节点的权的乘积称之为带权路径长度。
• 树的带权路径长度（Weighted path length，Wpl）：树的所有叶子节点的带权路径长度之和，称之为树的带权路径长度。Wpl最小的二叉树，称之为霍夫曼树。
• • 实际意义：权值越大离根节点越近
• • 

霍夫曼树的创建（将数列转成霍夫曼树）

霍夫曼树的创建思路

1. 从小到大将数列进行排序，将每一个数据都视作一个结点，每一个节点都课看作一颗最简单的二叉树。
2. 取出根节点权值最小的两棵二叉树。
3. 组成一棵新的二叉树，该新的的二叉树的根节点的权值是前两棵二叉树根结点权值的和。
4. 再将这颗新的二叉树，以根节点的权值大小再进行整理排序。
5. 不断重复上述步骤，直到所有的数据都被处理，就得到一棵霍夫曼树。

图例

以{1，3，6，7，8}为例子，构建相应的霍夫曼树

注意：再以两个最小的权值作为基本的二叉树的过程中，两个最小的数没有绝对的左右之分，结果都一样，不过为了方便，习惯是小左大右。

代码实现

结点代码：

//创建节点类//为了让Node对象持续排序，并且具有比较的功能，继承Comparable接口class Node implements Comparable
   
    {
       int val;    Node left;    Node right;    public void preOrder(){
           System.out.println(this);        if (this.left != null){
               this.left.preOrder();        }        if(this.right != null){
               this.right.preOrder();        }    }    public Node(int val) {
           this.val = val;    }    @Override    public String toString() {
           return "Node{" +                "val=" + val +                '}';    }    @Override    public int compareTo(Node o) {
           return this.val - o.val;        //当前值大于传入值，    }}
   

调用结合类的排序方法直接排序

Collections.sort(nodes);    System.out.println(nodes);    //取出最小的两个    Node leftNode = nodes.get(0);    Node rightNode = nodes.get(1);    //构建一个新的二叉树,根节点的权值是两者之和    Node parent = new Node(leftNode.val + rightNode.val);    parent.left = leftNode;    parent.right = rightNode;    //从ArrayList中去除已经比较过的两个最小的结点    nodes.remove(leftNode);    nodes.remove(rightNode);    //将新生成的二叉树的根节点加入到集合中去    nodes.add(parent);    //重新排序已经修改过的节点    Collections.sort(nodes);    System.out.println("排序过集合=" + nodes);

第二次：

//第二轮，取出最小的两个节点    leftNode = nodes.get(0);    rightNode = nodes.get(1);    //生成最小的    Node parent2 = new Node(leftNode.val + rightNode.val);    parent2.left = leftNode;    parent2.right = rightNode;    //将原先的数组中删除已经排过序的结点    nodes.remove(leftNode);    nodes.remove(rightNode);    nodes.add(parent2);    Collections.sort(nodes);    System.out.println("第二次整理后的集合" + nodes);

总结代码：

public static Node createHuffManTree(int[] arr){
           //第一步，为了操作方便，先遍历arr[]数组        //将arr【】的每一个元素，构建为Node        //将Node放入ArrayList中去，便于直接排序管理        List
   
     nodes = new ArrayList
    
     ();        for (int val:arr){
               //for循环的加强结构：（数组成员数据类型 数组成员名：数组名）            nodes.add(new Node(val));        }//              Node leftNode;        Node rightNode;        Node[] nodes1 = new Node[arr.length - 1];        int i = 0;        Collection.sort(nodes);        while (nodes.size() > 1){
               leftNode = nodes.get(0);            rightNode = nodes.get(1);            Node parent = new Node(leftNode.val + rightNode.val);            parent.left = leftNode;            parent.right = rightNode;            nodes.remove(leftNode);            nodes.remove(rightNode);            nodes.add(parent);            Collections.sort(nodes);            System.out.println(nodes);        }        //返回霍夫曼树树，就是返回root结点        nodes.get(0).preOrder();        return nodes.get(0);    }
    
   

分析与总结

1. 如果不适用集合，单纯的使用数组，并且自己写方法去排序也可。但是数组的增删改除不易操作，不可以改变长度，没依次排序会空耗很多空间
2. 树的节点本就是对象，所以必须将数组中的整形数据转成对象，集合又便于操作。
3. 最然在生成新的根节点时，用的是同样的名字parent，但是地址不同，彼此之间也是通过结点自身的索引连接的。
4. 我还是建议修改成为数组类型，新建一个数组来保存新生成的结点，那样就可以单独调用每一个节点

Node[] nodes1 = new Node[arr.length - 1];        int i = 0;        while (nodes.size() > 1){
               leftNode = nodes.get(0);            rightNode = nodes.get(1);            nodes1[i] = new Node(leftNode.val + rightNode.val);            nodes1[i].left = leftNode;            nodes1[i].right = rightNode;            nodes.remove(leftNode);            nodes.remove(rightNode);            nodes.add(nodes1[i]);            Collections.sort(nodes);            System.out.println(nodes);        }

常见错误

1. 取一个除一个，还是取索引是0和1，出现角标越界

left = list.get(0);list.remove(left);right = list.get(1);list.remove(right);

异常：

分析与总结： 当仅仅只剩两个的时候，第一个取出来，还剩一个，然后第二次取出的索引是1，已经是第二个了，但是总共只剩一个了，所以出现角标越界。

转载地址：http://aqgpb.baihongyu.com/