package com.xcc.dataStructures.demo10_huffman;

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

/**
 * 赫夫曼树
 *
 * @author xiaocheng
 * @date 2020/12/17 10:16
 */
public class HuffmanTree {

    public static void main(String[] args) {
//        int[] arr = { 13, 7, 8, 3, 29, 6, 1 };
        int[] arr = { 13, 7, 8, 3 };
        Node root = createHuffman(arr);
        preOrder(root);
    }

    /**
     * 前序遍历
     */
    public static void preOrder(Node root) {
        if (root == null) {
            System.err.println("当前二叉树为空！");
            return;
        }
        root.preOrder();
    }

    /**
     * 构建赫夫曼树
     */
    public static Node createHuffman(int[] arr) {
        List<Node> list = new ArrayList<>(arr.length);
        for (int value : arr) {
            list.add(new Node(value));
        }

        while (list.size() > 1) {
            Collections.sort(list);
            //先排序，从小到大
            Node leftNode = list.get(0);
            Node rigthNode = list.get(1);
            Node parent = new Node(leftNode.no + rigthNode.no);
            parent.left = leftNode;
            parent.rigth = rigthNode;

            list.remove(leftNode);
            list.remove(rigthNode);
            list.add(parent);
        }
        return list.get(0);
    }

    static class Node implements Comparable<Node>{
        int no;
        Node left;
        Node rigth;

        /**
         * 前序遍历
         */
        public void preOrder() {
            System.out.println(no);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.rigth != null) {
                this.rigth.preOrder();
            }
        }

        public Node(int no) {
            this.no = no;
        }

        @Override
        public String toString() {
            return "Node[" +
                    "no=" + no +
                    ']';
        }

        @Override
        public int compareTo(Node node) {
            return this.no - node.no;
        }
    }

}