可以看出所有的叶子节点就是之前的离散节点,如果在采用广度遍历法遍历此树。那
么遍历的过程实际上就是最短遍历路径的遍历过程
2. 哈夫曼树的使用场景
其实哈夫曼树使用场景还真不少,例如 apache 负载均衡的按权重请求策略的底层
算法、咱们生活中的路由器的路由算法、利用哈夫曼树实现汉字点阵字形的压缩存储
(
http://www.cnki.com.cn/Article/CJFDTotal-LYGY200504016.htm
)、快速检索信
息等等底层优化算法,其实核心就是因为目标带有权重、长度远近这类信息才能构建
哈夫曼树模型。
3. 实现哈夫曼树
要想实现哈夫曼树其实就是将一堆零散的节点信息构建成一颗最优二叉树,之后再
按广度优先遍历它。
实现哈夫曼树其实就是构建哈夫曼树的过程,原理其实上面已经说了,这里再重复
一下。
首先先将离散节点从小到大升序排序
第二从离散节点中在挑选排序前两个节点当做一个新的父节点的两个子节点
第三从离散的节点中去除刚刚使用的两个节点
第四重复第二和第三步骤,直到所有离散节点剔除完毕。哈夫曼树就构建完成
2
/
6