【数据结构】哈夫曼树
程序员文章站
2022-05-04 08:48:52
【数据结构】哈夫曼树1、基本概念2、什么是哈夫曼树?3、哈夫曼树构建图解4、代码实现哈夫曼树1、基本概念路径:一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径,如图:从根节点1到叶子节点4的路径:1,2,4路径长度:在一棵树中,从一个结点到另一个结点所经过的“边”的数量,被我们称为两个结点之间的路径长度,还是上图,根节点1到叶子结点4的路径经过了2个边,也就是说,若规定根节点的层数为1,则从根节点到N层的结点的的路径长度为:N-1结点的带权路径长度:树的...
【数据结构】哈夫曼树
1、基本概念
-
路径:一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径,如图:
从根节点1到叶子节点4的路径:1,2,4 -
路径长度:在一棵树中,从一个结点到另一个结点所经过的“边”的数量,被我们称为两个结点之间的路径长度,还是上图,根节点1到叶子结点4的路径经过了2个边,也就是说,若规定根节点的层数为1,则从根节点到N层的结点的的路径长度为:N-1
-
结点的带权路径长度:树的每一个结点,都可以拥有自己的“权重”(Weight),权重在不同的算法当中可以起到不同的作用。结点的带权路径长度,是指树的根结点到该结点的路径长度,和该结点权重的乘积,还是上图,如结点4的权重是10,那结点4的带权路径长度就是10*2 = 20。
-
树的带权路径长度:在一棵树中,所有叶子结点的带权路径长度之和,被称为树的带权路径长度,也被简称为WPL。
2、什么是哈夫曼树?
- 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。
- 哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
- WPL最小的就是哈夫曼树
3、哈夫曼树构建图解
- 给定一个数列:
- 第一步:把每一个叶子结点,都当做树一颗独立的树(只有根结点的树),同时建个辅助队列,按照权值从小到大存储了所有叶子结点,用于后续哈夫曼树的构建辅助。
- 第二步:选择当前权值最小的两个结点,生成新的父结点,借助辅助队列,我们可以找到权值最小的结点1和4,并根据这两个结点生成一个新的父结点,父节点的权值是这两个结点权值之和。
- 第三步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列
也就是从队列中删除1和4,插入5,并且仍然保持队列的升序。
- 第四步:继续选择当前权值最小的两个结点,生成新的父结点。
- 第五步:继续移除上一步选择的两个最小结点,把新的父节点加入队列。
- 第六步:继续选择当前权值最小的两个结点,生成新的父结点。
- 第七步:继续移除上一步选择的两个最小结点,把新的父节点加入队列。
- 第八步:继续选择当前权值最小的两个结点,生成新的父结点。
- 第九步:继续移除上一步选择的两个最小结点,把新的父节点加入队列。
- 第十步:继续选择当前权值最小的两个结点,生成新的父结点。
- 此时,队列中仅有一个结点,说明整个森林已经合并成了一颗树,而这棵树就是我们想要的哈夫曼树:
4、代码实现哈夫曼树
- 树节点
package com.data.structure.tree;
/**
* 树节点
*
* @author wangjie
* @version V1.0
* @date 2020/7/20
*/
public class Node implements Comparable<Node>{
/**
* 节点权值
*/
int value;
/**
* 指向左子结点
*/
Node left;
/**
* 指向右子节点
*/
Node right;
public Node(int value){
this.value = value;
}
/**
* 前序遍历,先输出父结点,再遍历左子树和右子树
*/
public void preOrder(){
System.out.println(this);
if(null != this.left){
this.left.preOrder();
}
if(null != this.right){
this.right.preOrder();
}
}
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
@Override
public String toString(){
return "Node[value="+value+"]";
}
}
- 哈夫曼树
package com.data.structure.tree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 哈夫曼树
*
* @author wangjie
* @version V1.0
* @date 2020/7/20
*/
public class HuffmanTree {
public static void main(String[] args) {
int arr[] = {2,3,7,9,18,25};
Node root = createHuffmanTree(arr);
preOrder(root);
}
/**
* 前序遍历
* @param root
*/
public static void preOrder(Node root){
if (null != root){
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);
}
}
本文地址:https://blog.csdn.net/aaa_bbb_ccc_123_456/article/details/107462776
上一篇: MySQL数据库入门详细笔记
下一篇: 经典问题