本文共 2238 字，大约阅读时间需要 7 分钟。

➢ 基本介绍

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

➢ 概念说明

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

➢ 构成赫夫曼树的步骤：

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

如下图所示

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

class HNode implements Comparable
   
     {
   	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
   
     nodes = new ArrayList
    
     ();		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]

或者简化一下数组当中的数据：如下图所示：

转载地址：http://jgmzi.baihongyu.com/