Java中的哈夫曼树

  1 package com.ietree.basic.datastructure.tree;
  2 
  3 import java.util.ArrayDeque;
  4 import java.util.ArrayList;
  5 import java.util.List;
  6 import java.util.Queue;
  7 
  8 /**
  9  * Created by ietree
 10  * 2017/5/1
 11  */
 12 public class HuffmanTree {
 13 
 14     public static class Node<E> {
 15         E data;
 16         double weight;
 17         Node leftChild;
 18         Node rightChild;
 19 
 20         public Node(E data, double weight) {
 21             this.data = data;
 22             this.weight = weight;
 23         }
 24 
 25         public String toString() {
 26             return "Node[data=" + data + ", weight=" + weight + "]";
 27         }
 28     }
 29 
 30     public static void main(String[] args) {
 31 
 32         List<Node> nodes = new ArrayList<Node>();
 33         nodes.add(new Node("A", 40));
 34         nodes.add(new Node("B", 8));
 35         nodes.add(new Node("C", 10));
 36         nodes.add(new Node("D", 30));
 37         nodes.add(new Node("E", 10));
 38         nodes.add(new Node("F", 2));
 39 
 40         Node root = HuffmanTree.create(nodes);
 41         System.out.println(breadthFirst(root));
 42 
 43     }
 44 
 45     /**
 46      * 构造哈夫曼树
 47      *
 48      * @param nodes 节点集合
 49      * @return 构造出来的哈夫曼树的根节点
 50      */
 51     private static Node create(List<Node> nodes) {
 52 
 53         // 只要nodes数组中还有2个以上的节点
 54         while (nodes.size() > 1) {
 55             quickSort(nodes);
 56             // 获取权值最小的两个节点
 57             Node left = nodes.get(nodes.size() - 1);
 58             Node right = nodes.get(nodes.size() - 2);
 59             // 生成新节点，新节点的权值为两个子节点的权值之和
 60             Node parent = new Node(null, left.weight + right.weight);
 61             // 让新节点作为权值最小的两个节点的父节点
 62             parent.leftChild = left;
 63             parent.rightChild = right;
 64             // 删除权值最小的两个节点
 65             nodes.remove(nodes.size() - 1);
 66             nodes.remove(nodes.size() - 1);
 67             // 将新生成的父节点添加到集合中
 68             nodes.add(parent);
 69         }
 70         // 返回nodes集合中唯一的节点，也就是根节点
 71         return nodes.get(0);
 72     }
 73 
 74     // 将指定数组的i和j索引处的元素交换
 75     private static void swap(List<Node> nodes, int i, int j) {
 76         Node tmp;
 77         tmp = nodes.get(i);
 78         nodes.set(i, nodes.get(j));
 79         nodes.set(j, tmp);
 80     }
 81 
 82     // 实现快速排序算法，用于对节点进行排序
 83     private static void subSort(List<Node> nodes, int start, int end) {
 84 
 85         // 需要排序
 86         if (start < end) {
 87             // 以第一个元素作为分界值
 88             Node base = nodes.get(start);
 89             // i从左边搜索，搜索大于分界值的元素的索引
 90             int i = start;
 91             // j从右边搜索，搜索小于分界值的元素的索引
 92             int j = end - 1;
 93             while (true) {
 94                 // 找到大于分界值的元素的索引，或者i已经到了end处
 95                 while (i < end && nodes.get(++i).weight >= base.weight) ;
 96                 // 找到小于分界值的元素的索引，或者j已经到了start处
 97                 while (j > start && nodes.get(--j).weight <= base.weight) ;
 98                 if (i < j) {
 99                     swap(nodes, i, j);
100                 } else {
101                     break;
102                 }
103             }
104             swap(nodes, start, j);
105             // 递归左子树序列
106             subSort(nodes, start, j - 1);
107             // 递归右子树序列
108             subSort(nodes, j + 1, end);
109         }
110     }
111 
112     public static void quickSort(List<Node> nodes) {
113         subSort(nodes, 0, nodes.size() - 1);
114     }
115 
116     // 广度优先遍历
117     public static List<Node> breadthFirst(Node root) {
118 
119         Queue<Node> queue = new ArrayDeque<Node>();
120         List<Node> list = new ArrayList<Node>();
121         if (root != null) {
122             // 将根元素入“队列”
123             queue.offer(root);
124         }
125         while (!queue.isEmpty()) {
126             // 将该队列的“队尾”的元素添加到List中
127             list.add(queue.peek());
128             Node p = queue.poll();
129             // 如果左子节点不为null，将它加入“队列”
130             if (p.leftChild != null) {
131                 queue.offer(p.leftChild);
132             }
133             // 如果右子节点不为null，将它加入“队列”
134             if (p.rightChild != null) {
135                 queue.offer(p.rightChild);
136             }
137         }
138         return list;
139 
140     }
141 
142 }