哈夫曼树（java实现）

image.png

image.png

最优的体现是：在搜索的时候，花费的时间最短（整体上花费的时间最小），也可以用在归并上，优先归并短的，则总体的归并时间最短
构造哈夫曼树（从下往上构造）：

image.png

image.png

image.png

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class HuffmanTreeTest {
    /**
     * 根节点
     */
    HuffmanTreeNode root;

    /**
     * 构造哈夫曼树(从下往上构建)
     * @param queue 采用优先级队列，保证队列按权值有序
     * @return
     */
    public HuffmanTreeNode createHuffmanTree(PriorityQueue<HuffmanTreeNode> queue){
        if(queue==null)
            return root;
        else if(queue.size()==1){
            root=queue.poll();
            return root;
        }else {
            //左孩子
            HuffmanTreeNode left;
            //右孩子
            HuffmanTreeNode right;
            while (queue.size()>1){
                left=queue.poll();
                right=queue.poll();
                //构造父节点
                HuffmanTreeNode parent=new HuffmanTreeNode(left.getPow()+right.getPow(),left,right);
                queue.offer(parent);
            }
            root=queue.poll();
            return root;
        }
    }

    /**
     * 层次遍历，用于测试
     * @param treeNode
     */
    public void levelTraverseBTree(HuffmanTreeNode treeNode){
        StringBuilder sb=new StringBuilder();
        Queue<HuffmanTreeNode> queue=new LinkedList<>();
        queue.offer(treeNode);
        while (!queue.isEmpty()){
            HuffmanTreeNode root=queue.poll();
            sb.append(root.getPow());
            sb.append(" ");
            if(root.getLeft()!=null)
                queue.offer(root.getLeft());
            if(root.getRight()!=null)
                queue.offer(root.getRight());
        }
        System.out.println(sb.toString().trim());
    }
    public static void main(String[] args){
        PriorityQueue<HuffmanTreeNode> queue=new PriorityQueue<>();
        queue.add(new HuffmanTreeNode("a",9));
        queue.add(new HuffmanTreeNode("b",4));
        queue.add(new HuffmanTreeNode("c",5));
        queue.add(new HuffmanTreeNode("d",2));
        
        HuffmanTreeTest test=new HuffmanTreeTest();
        HuffmanTreeNode node=test.createHuffmanTree(queue);
        //测试
        test.levelTraverseBTree(node);
       
    }
}

/**
 * 哈夫曼树
 */
public class HuffmanTreeNode implements Comparable{
    /**
     * 数据
     */
    private String data;

    /**
     * 权值
     */
    private int pow;

    /**
     * 左孩子
     */
    HuffmanTreeNode left;

    /**
     * 右孩子
     */
    HuffmanTreeNode right;

    public HuffmanTreeNode(){}
    public HuffmanTreeNode(int pow, HuffmanTreeNode left, HuffmanTreeNode right) {
        this.pow = pow;
        this.left = left;
        this.right = right;
    }

    public HuffmanTreeNode(String data, int pow) {
        this.data = data;
        this.pow = pow;
    }

    public String getData() {
        return data;
    }

    public int getPow() {
        return pow;
    }

    public HuffmanTreeNode getLeft() {
        return left;
    }

    public HuffmanTreeNode getRight() {
        return right;
    }
    
    @Override
    public String toString() {
        return "HuffmanTree{" +
                "data=" + data +
                ", pow=" + pow +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    /**
     * 按照权值升序排序
     * @param pow
     * @return
     */
    @Override
    public int compareTo(Object pow) {
        return this.pow-((HuffmanTreeNode)pow).pow;
    }
}