哈夫曼树实现

HuffmanTree.java

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

public class HuffmanTree {

    public static class Node<E> {
        E data;
        int weight;
        Node leftChild;
        Node rightChild;

        public Node(E data, int weight) {
            this.data = data;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }
    }

    private static Node createTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            // 从小到大排序
            Collections.sort(nodes, Comparator.comparingInt(o -> o.weight));

            Node left = nodes.get(0);  // 权重最小的
            Node right = nodes.get(1);  // 权重第二小的

            // 生成一个新的节点
            Node parent = new Node(null, left.weight + right.weight);
            parent.leftChild = left;
            parent.rightChild = right;

            nodes.remove(0);  // 删除最小的
            nodes.remove(0); // 删除第二小
            nodes.add(parent);
        }

        return nodes.get(0);
    }

    private static void printTree(Node root) {
        System.out.println(root.toString());

        if (root.leftChild != null) {
            System.out.print("left: ");
            printTree(root.leftChild);
        }
        if (root.rightChild != null) {
            System.out.print("right: ");
            printTree(root.rightChild);
        }
    }

    public static void main(String[] args) {
        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node("a", 10));
        nodes.add(new Node("b", 15));
        nodes.add(new Node("c", 12));
        nodes.add(new Node("d", 3));
        nodes.add(new Node("e", 4));
        nodes.add(new Node("f", 13));
        nodes.add(new Node("g", 1));

        Node root = createTree(nodes);
        printTree(root);
    }
}