哈夫曼树及实现

本文主要是介绍哈夫曼树及实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

哈夫曼树及实现

哈夫曼树(Huffman Tree)又称为最优二叉树，带权路径长度最短的树，权值较大的节点离根较近，哈夫曼树主要应用于数据压缩和编码；
路径：在一棵树中，从一个节点往下可以到达的孩子或孙子节点之间的通路，通路中分支的数目称为路径长度。如果规定根节点层数为1，则从根节点到第L层节点的路径长度为L-1；
节点的权和带权路径长度：如果将树中节点赋值给一个有着某种含义的数值，这个数值就是该节点的权。节点的带权路径长度为从根节点到该节点之间的路径长度与该节点的权的乘积；
树的带权路径长度（WPL）：所有叶子节点的带权路径长度之和。权值越大的节点离根节点越近的二叉树才是最优二叉树。

1. 构造一棵哈弗曼树

（1）从小到大排序，把给定的n个节点看成n棵独立的树，每棵树只有一个节点；

（2）选出权值最小的两棵树作为左右子树合并成一棵树，其根节点的权值为左右子树权值的和；

（3）将这两棵树从森林中删除，将新生成的树加入到森林中；

（4）重复步骤（2）和（3）指导只剩下一棵树。

import lombok.Data;
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};

这篇关于哈夫曼树及实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---