哈夫曼树的实现-Java实现

哈夫曼的核心思想在于，wpl最小；

 1 package dataSrtuct.TreeAlgorithm;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Collections;
 5 import java.util.List;
 6 
 7 public class HuffmanTree {
 8     public static void main(String[] args) {
 9         int[] arr={13,7,8,3,29,6,1};
10         Node root=CHuffmanTree(arr);
11         preOrder(root);
12     }
13     public static Node CHuffmanTree(int[] arr){
14         List<Node> list=new ArrayList<>();
15         for (int val: arr) {
16             list.add(new Node(val));
17         }
18         while (list.size()>1){
19             Collections.sort(list);
20             Node node=new Node(list.get(0).val+list.get(1).val);
21             node.left=list.get(0);
22             node.right=list.get(1);
23             //注意源码是重新创建了一个数组，所以删除一个元素，整体是相当与前移了，只需重复删除第一个即可；
24             list.remove(0);
25             list.remove(0);
26             list.add(node);
27         }
28         return list.get(0);
29     }
30     public static void preOrder(Node node){
31         if (node!=null)
32             node.preOrder(node);
33         else
34             System.out.println("是空树");
35     }
36 }
37 class Node implements Comparable<Node>{
38     int val;
39     Node left;
40     Node right;
41     public Node(int val){
42         this.val=val;
43     }
44 
45     @Override
46     public int compareTo(Node o) {
47         return this.val-o.val;
48     }
49 
50     @Override
51     public String toString() {
52         return "Node{" +
53                 "val=" + val +
54                 '}';
55     }
56     public void preOrder(Node node){
57         System.out.println(node.val);
58         if (node.left!=null)
59             preOrder(node.left);
60         if (node.right!=null)
61             preOrder(node.right);
62     }
63 }