数据结构与算法之赫夫曼树的概述

ゞ浴缸里的玫瑰 2021-09-01 10:02 228阅读 0赞

### 数据结构与算法之赫夫曼树的概述 ###

*  基本概念
 *  创建赫夫曼树的流程实现
 *  代码实现

# 基本概念 #

1. 赫夫曼树也称之为最优二叉树，它是几个带权叶子节点构成的所有二叉树中带权路径最小的二叉树。
     2. 叶结点的带权路径：例如：（a）  A结点权为9，经过2个结点 即：2*9 = 18    从根节点出发经过几个节点的数量 * 该节点的权
     3. 树的带权路径WPL：树的带权路径长度WPL(weight  path  length) ： 树中所有叶子结点的带权路径长度之和。当WPL最小时称之为最优二叉树也称为赫夫曼树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]

# 创建赫夫曼树的流程实现 #

例： 一个数组： 5,7,8,3,29,23,11,14
    1.排序
    2.取出根节点权值最小的两颗二叉树
    3.组成一颗新的二叉树，前面取出来的两颗二叉树是新二叉树的两个子树
    4.根节点的权值是前面取出来的两颗二叉树的根节点的权值之和

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 1]

# 代码实现 #

1.创建实体
    public class Node implements Comparable<Node>{
    	//权值
    	int value;
    	//左节点
    	Node left;
    	//右节点
    	Node right;
    	
    	public Node (int value) {
    		this.value = value;
    	}
    
    	@Override
    	public int compareTo(Node o) {
    		return this.value - o.value;
    	}
    
    	@Override
    	public String toString() {
    		return "Node [value=" + value + ", left=" + left + ", right=" + right + "]";
    	}
    2.代码实现
    public class testHuffmanTree {
    
    	public static void main(String[] args) {
    		int[] arr = {3,7,8,29,5,11,23,14};
    		Node node = createHuffmanTree(arr);
    		//获取根节点的权值
    		System.out.println(node);
    	}
    
    	private static Node createHuffmanTree(int[] arr) {
    		//使用数组中所有的元素创建若干个二叉树，只有一个节点
    		List<Node> nodes = new ArrayList<Node>();
    		for(int value : arr) {
    			nodes.add(new Node(value));
    		}
    		//循环处理
    		while(nodes.size() > 1) {
    			Collections.sort(nodes);
    			Node left = nodes.get(nodes.size() - 1);
    			Node right = nodes.get(nodes.size() - 2);
    			Node parent = new Node(left.value + right.value);
    			nodes.remove(left);
    			nodes.remove(right);
    			nodes.add(parent);
    		}
    		return nodes.get(0);
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]: /images/20210901/d7f94ab2708d40a3a29ea6d22900e7c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 1]: /images/20210901/fe5f0f6d68424bf5bcc316b770f7b6b6.png