哈夫曼树
1.概念：
- 给定n个权值最为n个叶子的节点，构建成一颗二叉树。如果次树的带权路径长度最小，则称此二叉树为最优二叉树，也叫哈夫曼树。
- WLP：带权路径长度
-
公式：
-
Wk:第k个叶子的节点权值
-
Lk:根节点到第k个叶子的节点长度
-
例如下列二叉树：
- 给定4个叶子节点，权值分别为{2，3，5，8}，可以构造出4中形状不同的二叉树，但它们的带权路径长度可能不同。
如上图可看出：1、最后两个树的带权路径长度相同且也是最小的，所以可看作哈夫曼树
? 2、权值最小的节点越靠下，越大越靠近根节点
2.构建哈夫曼树
（1）、在{2，3，5，8}这几个节点看作叶子节点（即后面没有子节点）
? 
（2）、在这几个节点中选出权值最小和次小的两个节点。构成一个新二叉树（最小为左字节的、次小为右子节点），新二叉树的权值为这两个权值之和.
（3）、删除已经使用过的节点。将新创建的节点加入到还没被使用过的节点集合中，找出最小和次小的节点权值。又构成一颗新的二叉树。
（4）、重复(2)的操作
? 
（5）、重复上面操作：删除已使用的节点，将新的节点加入未使用节点的集合中，发现只有一个节点，其权值为18.则此哈夫曼树创建完成，根节点权值为18.
代码如下：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 构造哈夫曼树
*/
public class test1 {
public static void main(String[] args) {
int[] arr={2,3,5,8};
//调用自定义的哈夫曼树方法，生成哈夫曼树
hafmantree(arr);
}
/**
* ,构造哈夫曼数方法
*
* @param arry
*/
public static void hafmantree(int[] arry) {
//创建集合用于存放节点值
List<Node> nlis = new ArrayList<Node>();
//遍历集合
for (int value : arry) {
//将每个数组元素看作Node节点对象，并存入list集合内
nlis.add(new Node(value));
}
/*
由于集合中存入的是一个个的Node对象，而Node对象已经被我们声明成了按照从小到大的可排序对象。
所以这里我们为可以通过Collections工具类中的sort方法进行排序
*/
//循环条件：只有一个节点，即最终根节点
while (nlis.size() > 1) {
Collections.sort(nlis);
//查看集合中还未被使用的节点
System.out.println(nlis);
//到了这里说明集合中的所有节点（权值）都是按照从小到大的顺序
//获取最小的节点值（二叉树左节点）:子节点
Node lileft = nlis.get(0);
//获取第2小的节点值（二叉树右节点）：子节点
Node lireght = nlis.get(1);
/*创建新的Node节点对象（二叉树）:
此节点对象是最小的两个节点之和所生成的最新的节点。三个节点可以看成一个二叉树，即：
根节点(insternode对象)、左子节点(lileft.value)、右子节点(lireght.value)
*/
Node insternode = new Node(lileft.value + lireght.value);
//此二叉树的左节点
insternode.left = lileft;
//此二叉树的右节点
insternode.right = lireght;
//删除已经被处理过的节点
nlis.remove(lileft);
nlis.remove(lireght);
//将最新的节点加入到list集合中
nlis.add(insternode);
//重新对最新的list数组进行排序
Collections.sort(nlis);
}
//查看最终根节点
System.out.println(nlis);
}
}
/**
* ,构造哈夫曼数节点类,
* 此类也可以看成一个二叉树：根节点(Node对象)、左节子点(left)、右字节点(right)
* 实现Comparable接口：说明此类是可通过Collections工具类排序的，
*/
class Node implements Comparable<Node> {
int value; //每个节点的值（权值）
Node left; //每个二叉树的左指向节点
Node right; //每个二叉树的右指向节点
//构造方法，这里只需要初始化value实例变量，用于对象的赋值，而 left 与 right 本身就是此对象，可直接用于value赋值
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//支持从小到大排序
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}
结果：
3.构建哈夫曼编码
-
这里是对一段字符串进行哈夫曼编码，所以需要先处理字符串
-
在哈夫曼树的基础上，规定了路径编码。
-
遍历已经创建好了的哈夫曼树，从它的根节点遍历次树到叶子节点，左子路径编码：0 、右子路径编码：1
import java.util.*;
/**
* 构造哈夫曼数+生成哈夫曼编码,编程实现。
*/
public class test1 {
public static void main(String[] args) {
//需要转换为哈夫曼编码的字符串
String valus="asdsgddbhj ,sjsh";
//将字符串存以node对象存入list集合中
List<Node> list = ListAndNode(valus);
//生成哈夫曼树
Node node = HFMTree(list);
//得到哈夫曼编码
HFMTable(node,"",andindex);
System.out.println(yezijied); //{32=1010, 97=1011, 98=1100, 115=01, 100=111, 103=1101, 104=001, 106=100, 44=000}
}
/*
第四步：
创建哈夫曼编码表：将叶子节点以0、1表示。0===》向左子节点走。1===》向右子节点走
yezijied:存放叶子节点对应的哈夫曼编码。此集合作业与全局
andindex：拼接编码。(拼接对应的0或1，形参最终的哈夫曼编码)
*/
static Map<Byte,String> yezijied=new HashMap<>();
static StringBuilder andindex=new StringBuilder();
/**