一、定义
一些定义：
- 节点之间的路径长度：在树中从一个结点到另一个结点所经历的分支，构成了这两个结点间的路径上的经过的分支数称为它的路径长度
- 树的路径长度：从树的根节点到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
- 结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。
- 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
- 树的带权路径长度(Weighted Path Length of Tree：WPL)：定义为树中所有叶子结点的带权路径长度之和
如下面的二叉树，叶子节点的权值分别为5、6、2、4、7，的带权路径长度计算：
- 最优二叉树：从已给出的目标带权结点(单独的结点) 经过一种方式的组合形成一棵树.使树的权值最小.。最优二叉树是带权路径长度最短的二叉树。根据结点的个数，权值的不同，最优二叉树的形状也各不相同。它们的共同点是：带权值的结点都是叶子结点。权值越小的结点，其到根结点的路径越长。
如，给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，
它们的带权路径长度分别为：
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
(c)WPL=7*1+5*2+2*3+4*3=35
其中(c)树的WPL最小，可以验证，它就是哈夫曼树。
注意：
① 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。
② 最优二叉树中，权越大的叶子离根越近。
③ 最优二叉树的形态不唯一，WPL最小。
二、构造哈夫曼树
1） 根据给定的n个权值｛w1， w2， w3， w4……wn｝构成n棵二叉树的森林 F=｛T1 ， T2 ， T3…..Tn｝，其中每棵二叉树只有一个权值为wi 的根节点，其左右子树都为空；
2） 在森林F中选择两棵根节点的权值最小的二叉树，作为一棵新的二叉树的左右子树，且令新的二叉树的根节点的权值为其左右子树的权值和；
3）从F中删除被选中的那两棵子树，并且把构成的新的二叉树加到F森林中；
4）重复2 ，3 操作，直到森林只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。
构造过程如下图：
三、哈夫曼编码
从根节点出发，每个父节点都会有分支，现在给左右分支各赋予一个数值，做分支表示‘0’，有分支表示‘1’。当从根节点一直数到叶子结点过程中所经历的左右分支以‘0’、’1’表示时，每个叶子结点会形成一个特定的编码，这个就是哈夫曼编码，如上图中四个叶子结点的编码分别为：
A：101
B：11
C：100
D：0
在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：
（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；
（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
1 等长编码
这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。
2.不等长编码
在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。
因此，为了设计长短不等的编码，以便减少电文的总长，还必须考虑编码的唯一性，即在建立不等长编码时必须使任何一个字符的编码都不是另一个字符的前缀。
这个问题可以采用哈夫曼编码解决。
哈夫曼的WPL就是非叶子节点的权值之和
import lombok.Data;
@Data
public class HNode
{
public String data="";
public int count;
public HNode leftChild;
public HNode rightChild;
}
|
import java.util.*;
public class HuffmanTree
{
private HNode root;
private int wpl;
public HNode createTree(List<HNode> nodes)
{
wpl=0;
while (nodes.size()>1)
{
quickSort(nodes);
HNode left = nodes.get(0);
HNode right= nodes.get(1);
HNode newNodeRoot = new HNode();
newNodeRoot.setLeftChild(left);
newNodeRoot.setRightChild(right);
newNodeRoot.setCount(left.count+right.count);
nodes.remove(0);
nodes.remove(0);
nodes.add(0,newNodeRoot);
}
root=nodes.get(0);
return nodes.get(0);
}
private void quickSort(List<HNode> nodes)
{
nodes.sort(Comparator.comparingInt(o -> o.count));
}
public void preOrder(HNode root)
{
if (root==null)return ;
System.out.println("data="+root.data+" 权值"+root.count);
preOrder(root.leftChild);
preOrder(root.rightChild);
}
public void levelOrder(HNode root)
{
if (root==null)return ;
Queue<HNode> queue=new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty())
{
HNode top=queue.poll();
System.out.println("data="+top.data+" 权值"+top.count);
HNode left = top.leftChild;
HNode right = top.rightChild;
if (left!=null)queue.add(left);
if (right!=null)queue.add(right);
}
}
public int getWpl()
{
calculateWpl(root);
return wpl;
}
public void calculateWpl(HNode root)
{
if (root==null)return ;
if (root.leftChild!=null||root.rightChild!=null)wpl+=root.count;
calculateWpl(root.leftChild);
calculateWpl(root.rightChild);
}
}
|
测试代码
public static void main(String[] args)
{
Random random = new Random();
List<HNode> nodes=new ArrayList<>();
for (int i = 0; i < 5; i++)
{
HNode hNode = new HNode();
hNode.setCount(random.nextInt(10));
hNode.setData((char)(random.nextInt(26)+'a')+"");
nodes.add(hNode);
}
for (HNode node : nodes)
{
System.out.print(" data="+node.data+",count="+node.count);
}
System.out.println();
HuffmanTree huffmanTree = new HuffmanTree();
HNode root = huffmanTree.createTree(nodes);
huffmanTree.levelOrder(root);
System.out.println("带权路径长度之和wpl="+huffmanTree.getWpl());
}
|
测试结果
data=j,count=2 data=g,count=9 data=c,count=2 data=q,count=5 data=g,count=4
data= 权值22
data=g 权值9
data= 权值13
data=q 权值5
data= 权值8
data= 权值4
data=g 权值4
data=j 权值2
data=c 权值2
带权路径长度之和wpl=47
Process finished with exit code 0
|
生成哈夫曼编码
public void buildHuffmanCode(HNode root)
{
if (root==null)return ;
if (root.leftChild!=null)
{
root.leftChild.code=root.code+"0";
buildHuffmanCode(root.leftChild);
}
if (root.rightChild!=null)
{
root.rightChild.code=root.code+"1";
buildHuffmanCode(root.rightChild);
}
}
|
然后在哈夫曼树构建成功后调用此函数
得到的编码如下
data=j 编码=0 权值8
data=b 编码=10 权值5
data=n 编码=111 权值4
data=v 编码=1100 权值1
data=q 编码=1101 权值3
|