import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.function.Consumer;

public class HuffmanTree {

    private Node root;

    /**
     * 创建一颗哈夫曼树
     * 
     * @param list
     */
    public void createTree(List<Node> list) {
        Node leftChild;
        Node rightChild;
        Node parent;
        while (list.size() > 1) {
            Collections.sort(list);
            leftChild = list.get(0);
            rightChild = list.get(1);
            parent = new Node(leftChild.data + "-" + rightChild.data, leftChild.weight + rightChild.weight);
            parent.leftChild = leftChild;
            parent.rightChild = rightChild;
            leftChild.parent = parent;
            rightChild.parent = parent;
            list.remove(leftChild);
            list.remove(rightChild);
            list.add(0, parent);
        }
        root = list.get(0);
    }

    /**
     * 广度优先打印
     */
    public void breadth() {
        List<Node> list = new ArrayList<Node>();
        Queue<Node> queue = new ArrayDeque<Node>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            list.add(queue.peek());
            Node node = queue.poll();
            if (node.leftChild != null) {
                queue.add(node.leftChild);
            }
            if (node.rightChild != null) {
                queue.add(node.rightChild);
            }
        }
        list.forEach(new Consumer<Node>() {

            @Override
            public void accept(Node t) {
                System.out.println("node=" + t);
            }
        });
    }

    private static class Node implements Comparable<Node> {
        String data;
        int weight;
        Node parent;
        Node leftChild;
        Node rightChild;

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

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

        @Override
        public String toString() {
            String left = null;
            if (leftChild != null) {
                left = leftChild.data;
            }
            String right = null;
            if (rightChild != null) {
                right = rightChild.data;
            }
            return "[" + data + ", " + weight + ",left=" + left + ",right=" + right + "]";
        }
    }

    public static void main(String[] args) {
        List<Node> list = new ArrayList<>();
        list.add(new Node("A", 20));
        list.add(new Node("B", 10));
        list.add(new Node("C", 40));
        list.add(new Node("D", 50));
        list.add(new Node("E", 30));
        list.add(new Node("F", 70));
        list.add(new Node("G", 5));

        HuffmanTree tree = new HuffmanTree();
        tree.createTree(list);

        tree.breadth();
    }
}