哈夫曼树是数据结构中的一种数据类型，是最优二叉树，它的定义是给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。
要想实现哈夫曼树，首先要了解几个定义：
（1）路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
（2）结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
（3）树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
哈夫曼的操作实现：
基本定义：
public class HuffmanNode implements Comparable, Cloneable {
protected int key; // 权值
protected HuffmanNode left; // 左孩子
protected HuffmanNode right; // 右孩子
protected HuffmanNode parent; // 父结点
protected HuffmanNode(int key, HuffmanNode left, HuffmanNode right, HuffmanNode parent) {
this.key = key;
this.left = left;
this.right = right;
this.parent = parent;
}
@Override
public Object clone() {
Object obj=null;
try {
obj = (HuffmanNode)super.clone();//Object 中的clone()识别出你要复制的是哪一个对象。
} catch(CloneNotSupportedException e) {
System.out.println(e.toString());
}
return obj;
}
@Override
public int compareTo(Object obj) {
return this.key - ((HuffmanNode)obj).key;
}
}
具体实现过程：
package huffman;
import java.io.*;
import java.util.*;
public class Huffman {
private String str;// 最初用于压缩的字符串
private String newStr = "";// 哈夫曼编码连接成的字符串
private Node root;// 哈夫曼二叉树的根节点
private boolean flag;// 最新的字符是否已经存在的标签
private ArrayList<String> charList;// 存储不同字符的队列 相同字符存在同一位置
private ArrayList<Node> NodeList;// 存储节点的队列
public void creatHfmTree(String str) {
this.str = str;
charList = new ArrayList<String>();
NodeList = new ArrayList<Node>();
// 1.统计字符串中字符以及字符的出现次数
// 基本思想是将一段无序的字符串如ababccdebed放到charList里，分别为aa,bbb,cc,dd,ee
// 并且列表中字符串的长度就是对应的权值
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i); // 从给定的字符串中取出字符
flag = true;
for (int j = 0; j < charList.size(); j++) {
if (charList.get(j).charAt(0) == ch) {
// 如果找到了同一字符
String s = charList.get(j) + ch;
charList.set(j, s);
flag = false;
break;
}
}
if (flag) {
charList.add(charList.size(), ch + "");
}
}
// 2.根据第一步的结构，创建节点
for (int i = 0; i < charList.size(); i++) {
String data = charList.get(i).charAt(0) + ""; // 获取charList中每段字符串的首个字符
int count = charList.get(i).length(); // 列表中字符串的长度就是对应的权值
Node node = new Node(data, count); // 创建节点对象
NodeList.add(i, node); // 加入到节点队列
}
// 3.对节点权值升序排序
Sort(NodeList);
while (NodeList.size() > 1) {
// 当节点数目大于一时
// 4.取出权值最小的两个节点，生成一个新的父节点
// 5.删除权值最小的两个节点，将父节点存放到列表中
Node left = NodeList.remove(0);
Node right = NodeList.remove(0);
int parentWeight = left.count + right.count;// 父节点权值等于子节点权值之和
Node parent = new Node(parentWeight, left, right);
NodeList.add(0, parent); // 将父节点置于首位
}
// 6.重复第四五步，就是那个while循环
// 7.将最后的一个节点赋给根节点
root = NodeList.get(0);
}
public void Sort(ArrayList<Node> nodelist) {
for (int i = 0; i < nodelist.size() - 1; i++) {
for (int j = i + 1; j < nodelist.size(); j++) {
Node temp;
if (nodelist.get(i).count > nodelist.get(j).count) {
temp = nodelist.get(i);
nodelist.set(i, nodelist.get(j));
nodelist.set(j, temp);
}
}
}
}
public void output(Node node) {
if (node.lChild != null) {
output(node.lChild);
}
System.out.print(node.count + " "); // 中序遍历
if (node.rChild != null) {
output(node.rChild);
}
}
public void output() {
output(root);
}
public static void main(String[] args) {
Huffman huff = new Huffman();//创建哈弗曼对象
huff.creatHfmTree("sdfassvvdfgsfdfsdfs");//构造树
}