目录

一：赫夫曼树的介绍

二：赫夫曼树的构建

三：赫夫曼树的代码展示

一：赫夫曼树的介绍

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

二：赫夫曼树的构建

 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

例如有四个叶子节点 a b c d 权值分别为 12、5、6、21
创建赫夫曼树前森林如下

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

在森林中取出 b c节点 形成一棵新树M

(3)从森林中删除选取的两棵树，并将新树加入森林；

将新树M添加到森林后 森林如下

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
  **  4.1重复步骤（2）

在森林中取出权为11的节点以及a节点组成一棵新树N

  **  4.2重复步骤（3）

将新树N添加到森林中 森林如下

  **  4.3重复步骤（2）

在森林中取出b节点和权为23的节点组成一棵新树S

则新树S就是我们要创建的赫夫曼树

三：赫夫曼树的代码展示

package tree;

public class HufmNode implements Comparable<HufmNode>{
	private int values;
	
	private HufmNode left;
	
	private	HufmNode right;
	
	public HufmNode(int values) {
		this.values = values;
	}
	
	
	@Override
	public int compareTo(HufmNode node) {
		return this.getValues() - node.getValues();
	}
	
	
	@Override
	public String toString() {
		return "HufmNode [values=" + getValues() + "]";
	}


	//前序遍历
	public void preSelect() {
		System.out.println(this);
		if(this.getLeft() != null) {
			this.getLeft().preSelect();
		}
		if(this.getRight() != null) {
			this.getRight().preSelect();
		}
	}


	public int getValues() {
		return values;
	}


	public void setValues(int values) {
		this.values = values;
	}


	public HufmNode getLeft() {
		return left;
	}


	public void setLeft(HufmNode left) {
		this.left = left;
	}


	public HufmNode getRight() {
		return right;
	}


	public void setRight(HufmNode right) {
		this.right = right;
	}
	

}

package tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HufmTree {
	public static void main(String[] args) {
		int[] arr = new int[] {13,7,8,29,6,1};
		HufmNode hfmn= creatHufmTree(arr);
		hfmn.preSelect();
		
	}
	//把数列转为赫夫曼树
	public static HufmNode creatHufmTree(int[] arr) {
		//遍历数组
		
		//将元素转为Node
		//将Node放入集合中并且排序，从小到大
		List<HufmNode> nodes = new ArrayList<HufmNode>();
		for(int i: arr) {
			nodes.add(new HufmNode(i));
		}
		//从小到大排序
		while(nodes.size() > 1) {
			//获取最小元素
			Collections.sort(nodes);
			HufmNode left = nodes.get(0);
			HufmNode right = nodes.get(1);
			//创建新的结点
			HufmNode root = new HufmNode(left.getValues() + right.getValues());
			root.setLeft(left);
			root.setRight(right);
			//删除
			nodes.remove(left);
			nodes.remove(right);
			//加
			nodes.add(root);
		}
		return nodes.get(0);
		
	} 
	public static void preSelect(HufmNode root) {
		if(root == null) {
			System.out.println("空树...");
		}else {
			root.preSelect();
		}
	}
}