赫夫曼树HuffmanTree
1. 基本概念
- 路径:在树中,从一个节点到另外一个节点之间的分支构成这两个节点之间的路径;
- 路径长度:路径上的分支数称为路径长度;
- 若规定根节点的层数为1,则从根节点到第L层节点的路径长度为L - 1;
- 节点的权:对树中的节点赋一个具有某种含义的数值,则该数值称为该节点的权;
- 节点的带权路径长度:从根节点到该节点之间的路径长度与该节点的权的乘积(根节点到该节点路径长度l × 该节点权值w);
- 树的带权路径长度(WPL):所有叶子节点的带权路径长度之和,记为WPL(Weighted Path Length);
- WPL最小的二叉树就是Huffman Tree。因此权值越大的节点离根节点越近的二叉树才是最优二叉树。
2. Huffman Tree基本介绍
- 给定n个权值作为n个叶子节点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最短,则称这样的树为最优二叉树,也即哈夫曼树/赫夫曼树(Huffman Tree);
- Huffman Tree是带权路径长度最短的树,也即权值较大的节点应离根节点较近。
3. 构建Huffman Tree思路分析
- 给定一个数列{13,7,8,3,29,6,1},构建成赫夫曼树
- 将数列中的每个元素构建成Node节点,并将所有Node放入List中
- 开始循环重复下面步骤,直至List中只剩下一个元素,即只剩下赫夫曼树的root节点
- 对List从小到大排序,将List中的每一个节点都看作是一棵最简单的二叉树
- 取出根节点权值最小的两棵二叉树(也即权值最小的两个节点)
- 组成一棵新的二叉树,新的二叉树的根节点的权值是前面两棵二叉树根节点权值之和
- 从List中删除已经处理过的节点,并将新的二叉树的根节点权值加入List
- 返回List中唯一剩余的节点,即Huffman Tree的root节点,得到一棵Huffman Tree
4. 代码实现
package com.datastructure;
import java.util.*;
/**
* @author SnkrGao
* @create 2023-05-11 12:33
*/
public class HuffmanTree {
public static void main(String[] args) {
int[] arr = {13,7,8,3,29,6,1};
HuffmanNode root = createHuffmanTree(arr);
List<Integer> resList = new ArrayList<>();
List<List<Integer>> resList2 = new ArrayList<>();
System.out.println("前序遍历:");
resList = preorderTraversal(root,resList);
System.out.println(resList);
System.out.println("层序遍历:");
resList2 = levelorderTraversal(root);
System.out.println(resList2);
}
/**
* 构建哈夫曼树
* @param arr 用于构建哈夫曼树的数组
* @return 返回创建好的Huffman Tree的root节点
*/
public static HuffmanNode createHuffmanTree(int[] arr) {
// 遍历arr数组,对arr的每一个元素构建成节点并放入List中
List<HuffmanNode> nodes = new ArrayList<>();
for (int value : arr) {
nodes.add(new HuffmanNode(value));
}
while (nodes.size() > 1) {
// 对List排序
Collections.sort(nodes);
// 取出根节点权值最小的两个节点
HuffmanNode leftNode = nodes.get(0);
HuffmanNode rightNode = nodes.get(1);
// 构建一棵新的二叉树
HuffmanNode parent = new HuffmanNode(leftNode.getNo() + rightNode.getNo());
parent.setLeft(leftNode);
parent.setRight(rightNode);
// 从List中删除处理过的两个节点
nodes.remove(leftNode);
nodes.remove(rightNode);
// 将新构建的二叉树的根节点parent放入List
nodes.add(parent);
}
// 返回Huffman Tree的root节点
return nodes.get(0);
}
public static List<Integer> preorderTraversal(HuffmanNode root, List<Integer> list) {
if (root == null) {
System.out.println("哈夫曼树为空!");
return new ArrayList<>();
}
list.add(root.getNo());
if (root.getLeft() != null) {
list = preorderTraversal(root.getLeft(), list);
}
if (root.getRight() != null) {
list = preorderTraversal(root.getRight(), list);
}
return list;
}
public static List<List<Integer>> levelorderTraversal(HuffmanNode root) {
if (root == null) {
System.out.println("哈夫曼树为空!");
return new ArrayList<>();
}
List<List<Integer>> resList = new ArrayList<>();
Queue<HuffmanNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int queueSize = queue.size();
List<Integer> levelList = new ArrayList<>();
for (int i = 0; i < queueSize; i++) {
HuffmanNode tmpNode = queue.poll();
levelList.add(tmpNode.getNo());
if (tmpNode.getLeft() != null) {
queue.offer(tmpNode.getLeft());
}
if (tmpNode.getRight() != null) {
queue.offer(tmpNode.getRight());
}
}
resList.add(levelList);
}
return resList;
}
}
/**
* 为了让HuffmanNode节点对象支持Collections集合排序
* 让HuffmanNode实现Comparable接口
*/
class HuffmanNode implements Comparable<HuffmanNode>{
private int no;
private HuffmanNode left;
private HuffmanNode right;
public HuffmanNode(int no) {
this.no = no;
}
// 重写compareTo方法
@Override
public int compareTo(HuffmanNode o) {
// 排序规则:表示从小到大排序
return this.no - o.no;
}
@Override
public String toString() {
return "HuffmanNode{" +
"no=" + no +
'}';
}
public int getNo() {
return no;
}
public void setLeft(HuffmanNode left) {
this.left = left;
}
public HuffmanNode getLeft() {
return left;
}
public void setRight(HuffmanNode right) {
this.right = right;
}
public HuffmanNode getRight() {
return right;
}
}
5. 补充知识
在java中,Comparable和Comparator都是用来进行元素排序的,但二者有着本质上的区别:
-
用法不同:
-
Comparable接口只有一个compareTo方法,实现Comparable接口并重写compareTo方法,就可以实现某个类的排序,其支持Collections.sort和Arrays.sort。
- compareTo方法仅接受一个参数,即要比较的对象。排序规则是用当前对象与要比较的对象进行比较,并返回一个int类型的值。从小到大排序的规则是:当前对象值 - 要比较对象值;从大到小排序的规则是:要比较对象值 - 当前对象值。
- 注意:如果自定义对象没有实现Comparable接口,则不能使用Collections.sort方法进行排序。
-
Comparator的排序方法是compare,compare方法接收两个参数,排序规则与compareTo类似。
- Comparator除了可以通过创建自定义比较器外,还可以通过匿名内部类的方式,更快速、便捷地完成自定义比较器的功能。
-
-
运用场景不同:
- 使用Comparable必须要修改原有的类,在该类中实现Comparable接口并重写compareTo方法,因此Comparable更像是“对内”进行排序的接口;
- 而Comparator的使用则不同,无需修改原有的类。即使是对第三方提供的类,仍然可以通过创建新的自定义比较器Comparator实现对其的排序功能。也即通过Comparator接口可以实现和原有类的解耦,所以Comparator可以看作是“对外”提供排序的接口。