创建赫夫曼树详解
说明
- 赫夫曼树又称哈夫曼树,是指带权路径长度(WPL)最小的一颗二叉树
- 带权路径长度等于该数的所有叶子节点的权值 * 该叶子节点所在树的路径长度
- 创建一颗赫夫曼树,指的是将一个数组中的所有元素全部当作二叉树的叶子节点,然后计算WPL,wpl最小的二叉树,也就是最优二叉树,成为赫夫曼树
- 创建赫夫曼树思路分析
- 先创建节点类,应当包含权值value,左子节点和右子节点及其他遍历方法,还要实现Comparable接口,方便使用Collections接口的排序方法对集合中节点进行排序
- 将数组中所有元素封装为一个节点,然后将所有的节点存储到一个集合中,方便使用
- 先取出排序后集合的前两个节点构成一颗新的二叉树,及权值最小的,然后将新的二叉树的父节点加入到集合,将子节点从集合删除,然后对集合中的元素重新排序,继续取前两个节点构成二叉树,能保证新二叉树的权值最小,依次进行如上操作
- 当集合中还有一个节点时,说明转换赫夫曼树完毕
- 源码及详解见下
源码及分析
package algorithm.tree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* @author AIMX_INFO
* @version 1.0
*/
public class HuffmanTree {
public static void main(String[] args) {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
Node root = createHuffmanTree(arr);
preOrder(root);
}
//前序遍历哈夫曼树
/**
*
* @param root 输入根节点
*/
public static void preOrder(Node root){
if (root != null){
root.preOrder();
}else {
System.out.println("树为空,不能遍历");
}
}
//编写创建哈夫曼树的方法
/**
*
* @param arr 要转化为哈夫曼树的数组
* @return 返回转换的哈夫曼树
*/
public static Node createHuffmanTree(int[] arr) {
//将数组中的元素封装到节点然后存储到集合中
List<Node> nodes = new ArrayList<>();
for (int value : arr) {
nodes.add(new Node(value));
}
//循环创建哈夫曼树
while (nodes.size() > 1) {
//对集合中的节点按照值的大小从小到大进行排序
Collections.sort(nodes);
//取出节点值最小的两个节点
Node leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
//创建新节点,连接左右节点
Node parent = new Node(leftNode.value + rightNode.value);
parent.left = leftNode;
parent.right = rightNode;
//删除左右节点
nodes.remove(leftNode);
nodes.remove(rightNode);
//将父节点添加到集合
nodes.add(parent);
}
//返回根节点
return nodes.get(0);
}
}
//创建节点类
//让此节点类实现Comparable接口,方法使用Collections工具类的节点排序方法
class Node implements Comparable<Node> {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
//编写前序遍历方法
public void preOrder(){
System.out.println(this);
if (this.left != null){
this.left.preOrder();
}
if (this.right != null){
this.right.preOrder();
}
}
@Override
public int compareTo(Node o) {
//实现compareTo方法,完成按照节点值大小从小到大排序
return this.value - o.value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}