[toc]
数据结构之哈弗曼树
- 给定 n 个权值作为 n 个叶子结点,构造一棵二叉树, 若该树的
带权路径长度(
wpl)
达到最小,称这样的二叉树为最优二叉树
,也称为哈夫曼树(
Huffman Tree)
, 还有的书翻译为霍夫曼树
。
- 赫夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
1. 赫夫曼树几个重要概念☆
路径和路径长度:
在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径
。通路中分支的数目称为路径长度。若规定根结点的层数为 1,则从根结点到第 L 层结点的路径长度为 L-1
结点的权:
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。
结点的带权路径长度为:
从根结点到该结点之间的路径长度与该结点的权的乘积
☆树的带权路径长度:☆
树的带权路径长度规定为 所有叶子结点的带权路径长度之和,记为 WPL(weighted pathlength)
,权值越大的结点离根结点越近的二叉树才是最优二叉树。
2. 生成一颗赫夫曼树
给你一个数列 {13, 7, 8, 3, 29, 6, 1},要求转成一颗赫夫曼树.
2.1 构成赫夫曼树的步骤
- 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树。
- 图解
3. 代码实现
3.1 Node 节点
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
| /` * 创建节点类 * 为了让Node 对象持续排序Collections集合排序 * * @author DuanChaojie * @date 2020年3月15日 上午11:14:04 * @version 1.0 */ class Node implements Comparable<Node>{ int value; Node left; Node right; 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; }
public void preOrder() { System.out.println(this); if(this.left != null) { this.left.preOrder(); } if(this.right != null) { this.right.preOrder(); } }
}
|
3.2 实现功能及测试
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
| public class HuffmanTree {
public static void main(String[] args) { int[] arr = {13,7,8,3,29,6,1}; Node rootNode = createHuffmanTree(arr); preOrder(rootNode); } 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<Node>(); for (int value : arr) { nodes.add(new Node(value)); } while(nodes.size()>1) { Collections.sort(nodes); System.out.println("nodes="+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); } }
|
☆