Java 基础复习数据结构-哈夫曼树

1. 哈夫曼树

哈夫曼树也称作最优二叉树，当树中的节点带了权重信息了，带权路径长度最小的
二叉树叫做最优二叉树。带权路径长度=sum（权重*度）。sum 代表每个节点的之和。
加入有如下带权重的节点。

权重分别是 1、5、8、4。那么关于这些零散的节点，最优二叉树该如何构建呢？

首先先将离散节点从小到大升序排序
第二从离散节点中在挑选排序前两个节点当做一个新的父节点的两个子节点
第三从离散的节点中去除刚刚使用的两个节点
第四重复第二和第三步骤，直到所有离散节点剔除完毕。哈夫曼树就构建完成

用图形演示过程如下