赫夫曼树分析

什么是赫夫曼树
就是wpl: 就是树的带权路径长度最小
什么是路劲长度
什么是结点的权, 结点的带权路径长度

int[] arr = {13,7,8,3,29,6,1};
将这个arr变成一个赫夫曼树
就应该是这样的

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

public class HefumanshuTest {
    public static void main(String[] args) {
        int[] arr  = {13,7,8,3,29,6,1};
        Nodes anHefumanshuByarr = getAnHefumanshuByarr(arr);
        anHefumanshuByarr.qianxu();

    }
    //创建算法, 根据arr创建一个赫夫曼树
    public static Nodes getAnHefumanshuByarr(int[] arr){
        //先将int的数组变成树节点的ArrayList
        List nodes = new ArrayList();
        for (int value: arr){
            nodes.add(new Nodes(value));
        }


        

        //将以上步骤整合就是
        while(nodes.size() > 1){
            Collections.sort(nodes);

            //先取出权值最小的两颗二叉树
            Nodes left = nodes.get(0);
            Nodes right = nodes.get(1);
            //合并成一颗新的二叉树, 并且父节点的权值就是他们的权值的和
            Nodes parent = new Nodes(left.value+right.value);
            parent.left = left;
            parent.right = right;


            //从树节点的ArrayList中删除已经处理的节点
            nodes.remove(left);
            nodes.remove(right);
            //再将新的树的父节点存放进ArrayList, 并从新排序
            nodes.add(parent);
        }

        //最后返回ArrayList的最后一个节点, 及是赫夫曼树的root
        return nodes.get(0);

    }

}

//创建树节点
class Nodes implements Comparable{
    int value ; //权值
    Nodes left;
    Nodes right;

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

    @Override
    public String toString() {
        return "Nodes{" +
                "value=" + value +
                '}';
    }

    //让树节点去继承comparable接口, 继承compareTo方法, 实现从小到大或者从大到小的排序
    @Override
    public int compareTo(Nodes o) {
        //表示从小到大排序 , 如是从大到小就是负的形式
        return this.value-o.value;
    }

    //前序遍历
    public void qianxu(){
        System.out.println(this);
        if (this.left!= null){
            this.left.qianxu();
        }
        if (this.right!= null){
            this.right.qianxu();
        }
    }
}

前序遍历结果

Nodes{value=67}
Nodes{value=29}
Nodes{value=38}
Nodes{value=15}
Nodes{value=7}
Nodes{value=8}
Nodes{value=23}
Nodes{value=10}
Nodes{value=4}
Nodes{value=1}
Nodes{value=3}
Nodes{value=6}
Nodes{value=13}