java赫夫曼树

赫夫曼树：是一个权值最大的结点离根结点最近的优化树

权值就是每个结点的值

路径是通过一个结点往下可以达到孩子或孙子结点之间的通路

树的带权路径长度是所有叶子结点的带权路径长度与该结点的乘积 记为WPL

WPL最小的就是赫夫曼树

权值最大的结点距离根结点最近的二叉树是最右二叉树

从根结点到E的路径长度就是E结点的层数减去根结点的层数就是路径长度

E的带权路径长度就是它的路劲长度*E的权值=E的带权路径长度

假设把13,7,8,29,6,1组成一个赫夫曼树的各个结点的权值

首先需要把这些数做一个排序然后取出最小的两个结点

这最小的两个结点之和作为这个结点的父结点

重复步骤就可以组成一个赫夫曼树

 最终树的结构就是：

创建二叉树：

public class node implements Comparable {
    
    private int id;
    private node left;
    private node right;
    
    public void preSelect(){
        System.out.println(this);
        if(this.getLeft()!=null) this.getLeft().preSelect();
        if(this.getRight()!=null) this.getRight().preSelect();
    }

    public node(int id) {this.id = id;}

    public int getId() {return id;}

    public void setId(int id) {this.id = id;}

    public node getLeft() {return left;}

    public void setLeft(node left) {this.left = left;}

    public node getRight() {return right;}

    public void setRight(node right) {this.right = right;}

    @Override
    public String toString() {return "node{" + "id=" + id + '}';}
    
    @Override
    public int compareTo(node o) {return this.id-o.id;}

}

将普通二叉树转为赫夫曼树：

public class HuffmanTree {
    
    public node HuffmanChange(int[] array){
        
        List nodes = new ArrayList();
        
        for(int i:array){
            nodes.add(new node(i));
        }
        
        while(nodes.size()>1){
            Collections.sort(nodes);
            node leftNode = nodes.get(0);
            node rightNode = nodes.get(1);
            node newNode = new node(leftNode.getId()+rightNode.getId());
            newNode.setLeft(leftNode);
            newNode.setRight(rightNode);
            nodes.remove(0);
            nodes.remove(0);
            nodes.add(newNode);
        }
        //集合中一定会剩下一个元素因为nodes.size()>1的条件限制
        //也是最后两个数的父结点也就是最后的根结点
        System.out.println(nodes.size());
        
        return nodes.get(0);
    }
}