数据结构—哈夫曼树(Java)
博客说明
文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!
说明
- 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)
赫夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
WPL最小的就是赫夫曼树
思路
- 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树,以根节点的权值大小 再次排序
- 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| package cn.guizimo.huffmantree;
import java.util.ArrayList; import java.util.Collections; import java.util.List;
public class HuffmanTree { public static void main(String[] args) { int arr[] = {13, 7, 8, 3, 29, 6, 1}; Node root = createHuffmanTree(arr); System.out.println("哈夫曼树前序遍历:"); preOrder(root);
}
public static void preOrder(Node root){ if(root != null){ root.preOrder(); }else { System.out.println("空树"); } }
public static Node createHuffmanTree(int[] arr) { List<Node> nodes = new ArrayList<>(); for (int value : arr) { nodes.add(new Node(value)); } while (nodes.size() > 1) { Collections.sort(nodes);
Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); Node parent = new Node(leftNode.value + rightNode.value); parent.left = leftNode; parent.right = rightNode;
nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(parent); } return nodes.get(0); } }
class Node implements Comparable<Node> { int value; Node left; Node right;
public void preOrder(){ System.out.println(this); if(this.left != null){ this.left.preOrder(); } if(this.right != null){ this.right.preOrder(); } }
public Node(int value) { this.value = value; }
@Override public String toString() { return "Node{" + "value=" + value + '}'; }
@Override public int compareTo(Node o) { return this.value - o.value; } }
|
测试
感谢
尚硅谷
以及勤劳的自己