赫夫曼树(java)

本文主要是介绍赫夫曼树(java)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、基本概念

1.1 什么是赫夫曼树

给定N个权值作为N个叶子结点，构造一颗二叉树；
该树的带权路径长度(WPL)最小；
权值越大的结点离根节点越近；

1.2 什么是权值

百科：将树中结点赋给一个有着某种含义的数值。什么意思？？？我的理解是将数值赋给结点类中的一个变量，那么结点本身就有了权值这个属性，但是我没看懂这个定义。

1.3 什么是路径

从父结点到达其孩子结点或者孙子结点之间的通路；
若根结点的层数规定为1，那么从根结点到L层结点的路径长度为L-1；

1.4 什么是带权路径长度(WPL)

规定WPL为所有叶子结点的带权路径之和；
叶子结点的WPL = 该叶子结点的权值 * 从根结点到该叶子结点的路径长度；

1.5 举例说明

叶子结点上标注的值就是权值；
对于A，根结点为第1层，值为13的叶子结点在第3层，那么从根结点到该结点的路径长度为3 - 1 = 2；
对于A，值为13的叶子结点的WPL = 13 * 2 = 26；
那么A的WPL = WPL1 + WPL2 + WPL3 + WPL4 = 62；
上面三棵树中，根据赫夫曼树的定义，只有B是赫夫曼树；

二、如何构建赫夫曼树

2.1 明确给定值

给定的是N个带有权值的叶子结点；

2.2 明确赫夫曼树的特点

权值越小的结点离根结点越远，这点很关键；

2.3 实现赫夫曼树

定义结点类并加入权值属性，将数组中的值赋给结点；
将带有权值的结点加入到集合中，并从小到大排序；
找到权值最小的两个叶子结点，创建新的结点，其左右孩子指向这两个结点；
从集合中移除上述两个叶子结点，并加入新创建的结点；
重复上述2-4步，直到集合中只有一个元素，直接返回；

2.4 关于实现赫夫曼树过程中的一点理解

当叶子结点从集合中移除后，其仍在内存中，这样我们创建的这棵小树的逻辑结构还在，这就是最底下的二叉树；

重新对集合中的元素排序后，按照同样的方式，能得到上一层的树结构；

最后得到最优二叉树，也就时赫夫曼树；

三、赫夫曼树的代码实现

3.1 定义具有权值属性的结点类

/*** 这是结点类，实现Comparable接口是为了能够排序* @author Administrator**/
class Node implements Comparable<Node> {int value;Node left;Node right;// 构造方法public Node(int value) {this.value = value;}@Overridepublic String toString() {return "" + value;}// 前序遍历public void preOrder() {System.out.print(this + " ");if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}// 这个表示从小到大@Overridepublic int compareTo(Node o) {return this.value - o.value;}
}

3.2 构建赫夫曼树

// 这个方法用来构建赫夫曼树public 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 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);}

3.3 完整代码实现

package practice;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;/*** 这关于是赫夫曼树的练习* @author Administrator**/
public class HuffmanTree {public static void main(String[] args) {int[] arr = { 8, 3, 7, 13 };Node root = createHuffmanTree(arr);preOrder(root);}// 这个方法用于前序遍历public static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("空树,无法遍历");}}// 这个方法用来构建赫夫曼树public 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 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接口是为了能够排序* @author Administrator**/
class Node implements Comparable<Node> {int value;Node left;Node right;// 构造方法public Node(int value) {this.value = value;}@Overridepublic String toString() {return "" + value;}// 前序遍历public void preOrder() {System.out.print(this + " ");if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}// 这个表示从小到大@Overridepublic int compareTo(Node o) {return this.value - o.value;}
}