数据结构——赫夫曼树（Java代码实现）

落日映苍穹つ 2023-02-11 03:28 102阅读 0赞

➢ **基本介绍**

1.  给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(WPL)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。
2.  赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

➢ **概念说明**

1.  路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2.  结点的权及带权路径长度：若将树中结点赋给一个有着某种含 义的数值，则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
3.  树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL，权值越大的结点离根結点越近的二叉树才是最优二叉树。
4.  WPL最小的就是赫夫曼树

➢ **构成赫夫曼树的步骤：**

1.  从小到大进行排序,将每一 个数据， 每个数据都是一个节点， 每个节点可以看成是一颗最简单的二叉树
2.  取出根节点权值最小的两颗二叉树
3.  组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
4.  再将这颗新的二叉树， 以根节点的权值大小再次排序，不断重复1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

如下图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
➢ **代码实现**

创建节点类，实现Comparable接口，用于排序

class HNode implements Comparable<HNode> { 
    	int value; // 节点的值
    	HNode left; // 左右子节点的指针
    	HNode right;
    
    	public HNode(int value) { 
    		this.value = value;
    	}
    
    	// 前序遍历
    	public void DLR() { 
    		System.out.println(this);// 先输出根节点
    		// 左子树递归
    		if (this.left != null) { 
    			this.left.DLR();
    		}
    		// 右子树递归
    		if (this.right != null) { 
    			this.right.DLR();
    		}
    	}
    
    	@Override
    	public String toString() { 
    		return "HNode[value = " + value + "]";
    	}
    
    	@Override
    	public int compareTo(HNode o) { 
    		return this.value - o.value; // 从小到大排序
    	}
    }

定义方法：用于创建赫夫曼树

public static HNode create(int[] arr) { 
    		// 把数组的数据取出来放在节点类当中排序
    		List<HNode> nodes = new ArrayList<HNode>();
    		for (int value : arr) { 
    			nodes.add(new HNode(value));
    		}
    		while (nodes.size() > 1) { 
    			// 先进行排序
    			Collections.sort(nodes);
    			// System.out.println("nodes = "+ nodes);
    			
    			// 取出最小的俩个数据
    			HNode leftnode = nodes.get(0);
    			HNode rightnode = nodes.get(1);
    
    			// 构建新的二叉树
    			HNode parent = new HNode(leftnode.value + rightnode.value);
    			parent.left = leftnode;
    			parent.right = rightnode;
    
    			// 从当中删除使用过的子节点
    			nodes.remove(leftnode);
    			nodes.remove(rightnode);
    
    			// 把父节点加入进去
    			nodes.add(parent);
    		}
    		// System.out.println("第一次处理后：" +nodes);
    		return nodes.get(0);
    	}

以及一个前序遍历的方法

public static void DLR(HNode root) { 
    		if (root != null) { 
    			root.DLR();
    		} else { 
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}

在mian函数当中进行测试

int arr[] = {  4, 8, 13, 9, 1 };
    		HNode root = create(arr);
    		DLR(root);
    
    遍历结果：可对照上述图片：
    HNode[value = 35]
    HNode[value = 13]
    HNode[value = 5]
    HNode[value = 1]
    HNode[value = 4]
    HNode[value = 8]
    HNode[value = 22]
    HNode[value = 9]
    HNode[value = 13]

或者简化一下数组当中的数据：如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521170406896.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020052117482979.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70