哈夫曼树

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

• 路径长度：从根结点到某结点的边数
• 结点的带权路径长度：从根结点到该节点之间的路径长度与该结点的权的乘积
• 树的带权路径长度(WPL)：所有叶子结点的带权路径长度之和
• 哈夫曼树：WPL最小的二叉树

思路分析

给定数列{6,8,1,9,3}（权值）要求转化为一颗哈夫曼树
1、将数列按权值从小到大排序
2、取出权值最小的两个结点组成一颗新的二叉树,该二叉树的根节点为两个子结点的权值之和
3、将剩余的结点和第2步中二叉树的根结点重新组合成一个新的数列
4、重复执行123步直至数列中所有的结点都被处理就得到了一颗哈夫曼树

代码实现

/**
 * 实现Comparable<Node>是为了更方便结点的排序
 */
public class Node implements Comparable<Node>{

    private int value;/*结点权值*/
    private Node left;/*左子结点*/
    private Node right;/*右子结点*/

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

    /*前序遍历*/
    public void preDisplay(){
        System.out.println(this);
        if (this.left != null) {
            this.left.preDisplay();
        }
        if (this.right != null) {
            this.right.preDisplay();
        }
    }
    
	getter and setter 方法
	
    @Override
    public String toString() {
        return "[" + "value=" + value + ']';
    }

    @Override
    public int compareTo(Node node) {
        //表示从小到达排序
        return this.value - node.value;
    }
}

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

public class HuffManTree {

    public static void main(String[] args) {
        int arr[] = {6,8,1,9,3};
        Node huffmanTreeRoot = createHuffmanTree(arr);
        preShow(huffmanTreeRoot);
    }

    public static Node createHuffmanTree(int[] arr){
        /*将arr数组中的每个元素构成Node结点然后将Node放入ArrayList中*/
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            nodes.add(new Node(arr[i]));
        }
        while(nodes.size() >= 2){
            /*将nodes中的元素按value的值从小到大排序*/
            Collections.sort(nodes);
            /*取出最小的两个结点*/
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            /*构建二叉树*/
            Node parent = new Node(left.getValue()+right.getValue());
            parent.setLeft(left);
            parent.setRight(right);

            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);
        }
        /*返回哈夫曼树的根结点*/
        return nodes.get(0);
    }

    public static void preShow(Node root){
        if (root != null){
            root.preDisplay();
        }else{
            System.out.println("该树为空");
        }
    }
}

运行结果

[value=27]
[value=10]
[value=4]
[value=1]
[value=3]
[value=6]
[value=17]
[value=8]
[value=9]

Process finished with exit code 0