首页 > 代码库 > 哈夫曼树
哈夫曼树
主要思想:
(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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。