package week_10.homework;

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

public class HuffmanTree {
    public static  Node createTree(List<Node> nodes) {
        // 只要nodes数组中有2个以上的节点
        while (nodes.size() > 1) {
            //进行从大到小的排序
            Collections.sort(nodes);
            //获取权值最小的两个节点
            Node left = nodes.get(nodes.size() - 1);
            Node right = nodes.get(nodes.size() - 2);
            //生成新节点，新节点的权值为两个子节点的权值之和
            Node parent = new Node('无', left.getWeight() + right.getWeight());
            //让新节点作为两个权值最小节点的父节点
            parent.setLeft(left);
            left.setCodenumber("0");
            parent.setRight(right);
            right.setCodenumber("1");
            //删除权值最小的两个节点
            nodes.remove(left);
            nodes.remove(right);
            //将新节点加入到集合中
            nodes.add(parent);
        }
        return nodes.get(0);
    }


    public static  List<Node> breadthFirstTraversal(Node root) {
        List<Node> list = new ArrayList<Node>();
        Queue<Node> queue = new ArrayDeque<Node>();

       //将根元素加入“队列
        if (root != null) {
            queue.offer(root);
            root.getLeft().setCodenumber(root.getCodenumber() + "0");
            root.getRight().setCodenumber(root.getCodenumber() + "1");
        }

        while (!queue.isEmpty()) {
            //将该队列的“队尾”元素加入到list中
            list.add(queue.peek());
            Node node = queue.poll();

            //如果左子节点不为null，将它加入到队列
            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
                node.getLeft().setCodenumber(node.getCodenumber() + "0");
            }
           //如果右子节点不为null，将它加入到队列
            if (node.getRight() != null) {
                queue.offer(node.getRight());
                node.getRight().setCodenumber(node.getCodenumber() + "1");
            }
        }
        return list;
    }

}