基本介绍
- 给定n个权值作为n个叶子节点，构造一颗二叉树，若该 树的带权路径长度(wpl) 达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。
- 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近
重要概念
-
路径和路径长度：在一棵树中，从一个节点到另一个节点之间的通路(经过的所有节点)称为路径，路径中”边“的数目称为路径长度。若规定根节点的层数为1，则从根节点到第L层节点的路径长度为L-1。
-
结点的权和结点的带权路径长度：若赋给结点一个有着某种含义的数值，则这个数值称为该节点的权。该结点到根结点的路径长度与该结点的权的乘积称为该结点的带权路径长度。
-
树的带权路径长度：所有叶子节点的带权路径长度之和，记为WPL(weighted path lenght)。
-
赫夫曼树：WPL最小的二茬树，也被称为最优二叉树。
赫夫曼树创建流程
给定一个数列{13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树。
- 将每个数据当成一个结点，构成一个节点集合，每个节点可以看成是一颗最简单的二叉树。
- 取出根节点权值最小的两颗二叉树组成一颗新的二叉树，该新的二叉树的根节点的权值是两颗小二叉树节点权值之和，并将两颗小二叉树从集合中移除。
- 将这颗新的二叉树以根节点的权值大小和集合里的二叉树进行比较，重复第二步，直到集合里只剩下一颗二叉树，也就是赫夫曼树。
代码实现
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
|
package com.eh.ftd.dsa.ds;
import com.google.common.collect.Lists;
import java.util.List;
/**
* 赫夫曼树
*
* @author David Li
* @create 2020/06/28 00:33
*/
public class HuffmanTree {
/**
* 定义节点
*/
static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
public Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(data);
}
}
/**
* 前序遍历，用来展示创建好的赫夫曼树
*/
public static void preOrder(Node node) {
System.out.print(node + " ");
if (node.left != null) {
preOrder(node.left);
}
if (node.right != null) {
preOrder(node.right);
}
}
public static Node createHuffmanTree(int[] arr) {
// 构建一个有序的节点集合
List<Node> nodeList = Lists.newArrayList();
for (int a : arr) {
nodeList.add(new Node(a));
}
nodeList.sort((o1, o2) -> o1.data - o2.data);
// 取出根节点权值最小的两颗二叉树组成一颗新的二叉树，该新的二叉树的根节点的权值是两颗小二叉树节点权值之和，并将两颗小二叉树从集合中移除。
while (nodeList.size() > 1) {
Node n1 = nodeList.get(0);
Node n2 = nodeList.get(1);
Node parent = new Node(n1.data + n2.data, n1, n2);
nodeList.remove(n1);
nodeList.remove(n2);
nodeList.add(parent);
nodeList.sort((o1, o2) -> o1.data - o2.data);
}
return nodeList.get(0);
}
public static void main(String[] args) {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
preOrder(createHuffmanTree(arr));
}
}
|
参考
https://baijiahao.baidu.com/s?id=1663514710675419737&wfr=spider&for=pc
