zcq

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