构建赫夫曼树

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

/**
 * @author chenyi
 * @Description 构建赫夫曼树
 * @date 2022/2/21 10:06
 */
public class HuffmanTree {

    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        Node root = createHuffmanTree(arr);
        // 输出来看看
        perOrder(root);
    }

    public static void perOrder(Node node){
        if(node==null) {
            return;
        }
        System.out.print(node.val + " ");
        perOrder(node.left);
        perOrder(node.right);
    }

    private static Node createHuffmanTree(int[] arr) {
        // 将整数数组变为节点集合
        List<Node> nodeList = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            nodeList.add(new Node(arr[i]));
        }
        while (nodeList.size()>1) {
            Collections.sort(nodeList);
            // 取出最小的两个节点，两个节点之后构建出第三个节点
            Node node1 = nodeList.remove(0);
            Node node2 = nodeList.remove(0);
            Node node3 = new Node(node1.val+node2.val);
            node3.left = node1;
            node3.right = node2;
            nodeList.add(node3);
        }
        return nodeList.get(0);
    }


}

class Node implements Comparable<Node>{

    int val;
    Node left;
    Node right;

    @Override
    public int compareTo(Node o) {
        return this.val-o.val;
    }
    public Node(int val) {
        this.val = val;
    }

}