[数据结构与算法]哈夫曼树代码实现

public class Node implements Comparable<Node> {
    int value;
    Node left;
    Node right;

    public Node (int value) {
        this.value = value;
    }
    @Override
    public int compareTo(Node o) {//重写比较方法
        return -(this.value - o.value);
    }

    @Override
    public String toString() {//重写toString方法
        return "Node [value=" + value + "]";
    }

}


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

/**
 * @author admin
 * @version 1.0.0
 * @ClassName TestHuffmanTree.java
 * @Description TODO
 * @createTime 2021年09月02日 20:39:00
 */
public class TestHuffmanTree {
    public static void main(String[] args) {
        int[] arr={3,7,8,29,5,11,23,14};//传入要进行哈夫曼数操作的数组
        Node node =creatHuffmanTree(arr);//对数组进行操作
        System.out.println(node);
    }

    private static Node creatHuffmanTree(int[] arr) {
        List<Node> nodes = new ArrayList<>();//调用ArrayList,即可扩容的数组
        for(int value:arr){
            nodes.add(new Node(value));//向该数组依次加入结点
        }

        while(nodes.size()>1){//数组的长度等于1时则代表到最后一个结点了停止循环
            Collections.sort(nodes);//调用Collections接口的排序方法
            Node left=nodes.get(nodes.size()-1);//得到权值最小的那个数
            Node right=nodes.get(nodes.size()-2);//得到权值次小的那个数
            Node parent=new Node(left.value+right.value);//创建父节点
            nodes.remove(left);//移除最小和次小的结点
            nodes.remove(right);
            nodes.add(parent);//向数组中加入父节点
        }
        return nodes.get(0);//返回那个父节点
    }
}