赫夫曼树（leetcode打卡）

赫夫曼树（leetcode打卡）

package com.atguigu.tree;

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

public class HufumanTree {
    public static void main(String[] args) {
        int [] arr={13,7,8,3,29,6,1};
        TreeNode hufumanTree = createHufumanTree(arr);
        preOrders(hufumanTree);
    }

    public static TreeNode createHufumanTree(int [] arr){
        List nodes=new ArrayList<>();
        for (int val : arr) {
            nodes.add(new TreeNode(val));
        }
        while (nodes.size()>1){
            Collections.sort(nodes);
            System.out.println(nodes);
            TreeNode leftNode = nodes.get(0);
            TreeNode rightNode = nodes.get(1);
            TreeNode parent = new TreeNode(leftNode.value + rightNode.value);
            parent.left=leftNode;
            parent.right=rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }

        return nodes.get(0);
    }

    public  static void preOrders(TreeNode root){
        if (root!=null){
            root.preOrder();
        }else {
            System.out.println("树为空");
        }
    }
}
class TreeNode implements Comparable{
     int value;
     TreeNode left;
     TreeNode right;

     public void preOrder(){
         System.out.println(this);
         if (this.left!=null){
             this.left.preOrder();
         }
         if (this.right!=null){
             this.right.preOrder();
         }
     }

    public TreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                '}';
    }


    @Override
    public int compareTo(TreeNode treeNode) {
        return this.value-treeNode.value;
    }
}