代码实现

    1. package com.atguigu.huffmantree;
    3. /**
    4.  * ClassName:  <br/>
    5.  * Description:  <br/>
    6.  * Date: 2021-03-01 11:58 <br/>
    7.  * @project data_algorithm
    8.  * @package com.atguigu.huffmantree
    9.  */
    11. import java.util.ArrayList;
    12. import java.util.Collections;
    13. import java.util.List;
    15. public class HuffmanTree {
    17.     public static void main(String[] args) {
    18.         int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
    19.         Node root = createHuffmanTree(arr);
    21.         //测试一把
    22.         preOrder(root); //
    24.     }
    26.     //编写一个前序遍历的方法
    27.     public static void preOrder(Node root) {
    28.         if(root != null) {
    29.             root.preOrder();
    30.         }else{
    31.             System.out.println("是空树，不能遍历~~");
    32.         }
    33.     }
    35.     // 创建赫夫曼树的方法
    36.     /**
    37.      *
    38.      * @param arr 需要创建成哈夫曼树的数组
    39.      * @return 创建好后的赫夫曼树的root结点
    40.      */
    41.     public static Node createHuffmanTree(int[] arr) {
    42.         // 第一步为了操作方便
    43.         // 1. 遍历 arr 数组
    44.         // 2. 将arr的每个元素构成成一个Node
    45.         // 3. 将Node 放入到ArrayList中
    46.         List<Node> nodes = new ArrayList<Node>();
    47.         for (int value : arr) {
    48.             nodes.add(new Node(value));
    49.         }
    51.         //我们处理的过程是一个循环的过程
    54.         while(nodes.size() > 1) {
    56.             //排序 从小到大
    57.             Collections.sort(nodes);
    59.             System.out.println("nodes =" + nodes);
    61.             //取出根节点权值最小的两颗二叉树
    62.             //(1) 取出权值最小的结点（二叉树）
    63.             Node leftNode = nodes.get(0);
    64.             //(2) 取出权值第二小的结点（二叉树）
    65.             Node rightNode = nodes.get(1);
    67.             //(3)构建一颗新的二叉树
    68.             Node parent = new Node(leftNode.value + rightNode.value);
    69.             parent.left = leftNode;
    70.             parent.right = rightNode;
    72.             //(4)从ArrayList删除处理过的二叉树
    73.             nodes.remove(leftNode);
    74.             nodes.remove(rightNode);
    75.             //(5)将parent加入到nodes
    76.             nodes.add(parent);
    77.         }
    79.         //返回哈夫曼树的root结点
    80.         return nodes.get(0);
    82.     }
    83. }
    85. // 创建结点类
    86. // 为了让Node 对象持续排序Collections集合排序
    87. // 让Node 实现Comparable接口
    88. class Node implements Comparable<Node> {
    89.     int value; // 结点权值
    90.     char c; //字符
    91.     Node left; // 指向左子结点
    92.     Node right; // 指向右子结点
    94.     //写一个前序遍历
    95.     public void preOrder() {
    96.         System.out.println(this);
    97.         if(this.left != null) {
    98.             this.left.preOrder();
    99.         }
    100.         if(this.right != null) {
    101.             this.right.preOrder();
    102.         }
    103.     }
    105.     public Node(int value) {
    106.         this.value = value;
    107.     }
    109.     @Override
    110.     public String toString() {
    111.         return "Node [value=" + value + "]";
    112.     }
    114.     @Override
    115.     public int compareTo(Node o) {
    116.         // TODO Auto-generated method stub
    117.         // 表示从小到大排序
    118.         return this.value - o.value;
    119.     }
    121. }