首页 > 代码库 > 哈夫曼树

哈夫曼树

2024-07-11 09:21:57   229人阅读

主要思想：

(1)对List集合中所有节点进行排序。

(2)找出List集合中权值最小的两个节点。

(3)以权值最小的两个节点作为子节点创建新节点。

(4)从List集合中删除权值最小的两个节点，将新节点添加到List集合中。

创建哈夫曼树结构类：

 

 1 public static class Node<E> implements Comparable<Node<E>>{ 2         E data; 3         double weight;//权值 4         Node leftChild;//左子树 5         Node rightChild;//右子树 6  7         public Node(E data, double weight) { 8             this.data =http://www.mamicode.com/ data; 9             this.weight = weight;10         }11 12         public String toString() {13             return "Node[data="http://www.mamicode.com/+ data +", weight=" + weight + "]";14         }15         16         @Override17         public int compareTo(Node<E> o) {18             if(o.weight > this.weight){19                 return 1;20             } else if(o.weight < this.weight){21                 return -1;22             } else23             return 0;24         }25         26     }

 

构造哈夫曼树：

 1 /** 2      * 构造哈夫曼树 3      *  4      * @param nodes 5      *            节点集合 6      * @return 构造出来的哈夫曼树的根节点 7      */ 8     private static Node createTree(List<Node> nodes) { 9         // 只要nodes数组中还有2个以上的节点10         while (nodes.size() > 1) {11             Collections.sort(nodes);12             // 获取权值最小的两个节点13             Node left = nodes.get(nodes.size() - 1);14             Node right = nodes.get(nodes.size() - 2);15             // 生成新节点，新节点的权值为两个子节点的权值之和16             Node parent = new Node(null, left.weight + right.weight);17             // 让新节点作为权值最小的两个节点的父节点18             parent.leftChild = left;19             parent.rightChild = right;20             // 删除权值最小的两个节点21             nodes.remove(nodes.size() - 1);22             nodes.remove(nodes.size() - 1);23             // 将新生成的父节点添加到集合中24             nodes.add(parent);25         }26         // 返回nodes集合中唯一的节点，也就是根节点27         return nodes.get(0);28     }

广度优先遍历：

 1 // 广度优先遍历 2     public static List<Node> breadthFirst(Node root) { 3         Queue<Node> queue = new ArrayDeque<Node>(); 4         List<Node> list = new ArrayList<Node>(); 5         if (root != null) { 6             // 将根元素入“队列” 7             queue.offer(root); 8         } 9         while (!queue.isEmpty()) {10             // 将该队列的“队尾”的元素添加到List中11             list.add(queue.peek());12             Node p = queue.poll();13             // 如果左子节点不为null，将它加入“队列”14             if (p.leftChild != null) {15                 queue.offer(p.leftChild);16             }17             // 如果右子节点不为null，将它加入“队列”18             if (p.rightChild != null) {19                 queue.offer(p.rightChild);20             }21         }22         return list;23     }

测试函数：

 1 public static void main(String[] args) { 2         List<Node> nodes = new ArrayList<Node>(); 3         nodes.add(new Node("A", 40.0)); 4         nodes.add(new Node("B", 8.0)); 5         nodes.add(new Node("C", 10.0)); 6         nodes.add(new Node("D", 30.0)); 7         nodes.add(new Node("E", 10.0)); 8         nodes.add(new Node("F", 2.0)); 9         Collections.sort(nodes);10         System.out.println(nodes);11         Node root = HuffmanTree.createTree(nodes);12         System.out.println(breadthFirst(root));13     }

 

 

 


联系
我们