哈夫曼编码的自动生成
经过4个版本，我的哈夫曼编码的自动生成做好了，但这只是发报机的第一步，但是感觉编码的自动
生成每一个版本都让我收获不少，前两个版本都是手动连接哈夫曼树，第三个版本是采用自动连接，但是
做的时候，做得过于复杂，采用了双数组，一个存储未挂在树上的字母及其频率对象，一个用来存储哈夫
曼树的临时节点，但是这样做过于复杂，所以错误难免。今天早上经过对于第三版本的删减，修改优化，
在第四版中，哈夫曼编码的自动生成成功了！
在第四版中，只采用了一个数组，来存储临时节点，最终形成哈夫曼树，并且采用向上找双亲节点的
方式，生成每个叶节点的编码。具体代码解释，以及运行时的结果图如下：
哈夫曼树节点类的定义：
/**
* 定义构造哈夫曼树的节点类
* @author LONG 2013-04-05
* @version V4.0
*
*/
public class Node {
private char values; //在该节点存储的字母值
private int number = 0; //在该节点存储的字母的频率大小
private Node left = null; //定义该节点的属性左孩子节点
private Node right = null; //定义该节点的属性右孩子节点
private Node parent = null; //定义该节点的属性双亲节点
//设置该节点在双亲节点的左边还是右边，如果在左边则添加字符1，如果在右边则添加字符0
private String position = null;
/**
* 重写构造方法，在创建叶节点时调用
* @param values 传入的字母值
* @param number 字母的频率大小
*/
public Node(char values,int number){
this.values = values;
this.number = number;
}
/**
* 重写构造方法，在创建非叶节点时调用
* @param number
*/
public Node(int number){
this.number = number;
}
/**
* 恢复系统默认的构造方法
*/
public Node(){}
/**
* 返回该节点存储的字母
* @return
*/
public char getValues(){
return values;
}
/**
* 返回该节点存储的字母的频率
* @return
*/
public int getNumber(){
return number;
}
/**
* 设置该节点的左孩子
* @param left
*/
public void setLeft(Node left){
this.left = left;
}
/**
* 设置该节点的右孩子
* @param right
*/
public void setRight(Node right){
this.right = right;
}
/**
* 返回该节点的左孩子引用
* @return
*/
public Node getLeft(){
return left;
}
/**
* 返回该节点的右孩子引用
* @return
*/
public Node getRight(){
return right;
}
/**
* 设置该节点的父节点
* @param par
*/
public void setParent(Node par){
this.parent = par;
}
/**
* 返回该节点的父节点的引用
* @return
*/
public Node getParent(){
return parent;
}
/**
* 设置该节点是在双亲节点的右边还是左边，如果在左边则传入1否则传入0
* @param var
*/
public void setPosition(int var){
this.position = "" + var;
}
/**
* 得到该节点是处于双亲节点的左边还是右边
* @return
*/
public String getPosition(){
return position;
}
}
哈夫曼编码的实现类：
/**
* 实现哈夫曼树的主要类
* @author LONG 2013-04-05
* @version V4.0
*在4.0版本中，希望在节点中添加新的属性，即指向父节点的引用，以及记录自己被添加时处于左右边分支
*在节点中进行记录，最后通过由叶节点开始向上找自己的祖先，来得到自己的哈夫曼编码。
*
*/
public class HuffmanTree {
private Node[] leaf = null; //设置该树的叶子节点数组，在创建对象时进行初始化
private int length = 0; //用于记录叶子节点的数组长度
private int size = 0; //用于记录用户指定的数组的长度
private int count = 0; //用于记录用户输入元素的个数
/**
* 重写构造方法，设置创建对象时，指定该树叶子节点的个数，及所存储的字母个数
* @param size
*/
public HuffmanTree(int size){
this.size = size;
leaf = new Node[this.size];
}
/**
* 在叶子节点的数组中进行添加值
* @param values 添加进来的字母
* @param number 添加进来的字母频率
*
* 该方法首先需要判断传进来的字母是否已经存在，
*然后还有数组是否已经存满，如果满足添加的条件，
* 然后才进行创建节点，添加进去。
*/
public void add(char values,int number){
count++;//记录用户执行了多少次add方法，用来与用户指定的数组长度比较
if(!isFull() && !isSame(values)){
Node temp = new Node(values,number);
leaf[length++] = temp;
}
}
/**
* 生成哈夫曼编码与用户直接交流的方法，来确保类的封装性及安全性
*/
public void showCode(){
if(isFull() && size == count){
Node temp = showTree();
showResult(temp);
}else{
System.out.println("请检查输入的字母，不能出现重复，以及指定的大小是否与添加的值个数相同！");
}
}
/**
* 对初始化时判断存储的叶子节点数组是否已满，如果满了，则返回true，否则返回false
* @return
*/
private boolean isFull(){
boolean theResult = true;
if(length < leaf.length){ //说明数组未满
theResult = false;
}
return theResult;
}
/**
* 对传入的字母与已存在叶子数组中的元素的字母相比较，如果相同，则返回true，否则返回false
* @param var
* @return
*/
private boolean isSame(char var){
boolean theResult = false;
for(int i = 0; i < length; i++){
if(leaf[i].getValues() == var){
theResult = true;
}
}
return theResult;
}
/**
* 对传入的树的节点数组，按照节点中的频率由小到大进行冒泡排序，最后返回排好序的数组
* @param no
* @return
*/
private Node[] getNewNode(Node[] no){
for(int i = 0; i < length; i++){
for(int j = i + 1; j < length; j++){
if(no[i].getNumber() > no[j].getNumber()){
Node temp = no[i];
no[i] = no[j];
no[j] = temp;
}
}
}
return no;
}
/**
* 生成一颗哈夫曼树
*/
private Node showTree(){
Node result = null;
if(isFull()){ //首先判断是否元素已经填满
//判断节点数组中含有元素的个数，如果为1，说明哈夫曼树已经建好
while(length > 1){
//然后对于节点数组按照里面存储的频率大小进行排序，
//那么就知道数组的前两位就是需要连接起来的
leaf = getNewNode(leaf);
//设置新的节点的频率为前两个元素的频率之和
Node temp = new Node(leaf[0].getNumber() + leaf[1].getNumber());
leaf[0].setParent(temp);//设置节点对双亲节点的引用
leaf[1].setParent(temp);//设置节点对双亲节点的引用
temp.setLeft(leaf[0]);//设置第一个元素为左孩子
//因为该节点处于双亲节点的左边，所以传进的位置参数为1
leaf[0].setPosition(1);
temp.setRight(leaf[1]);//设置第二个元素为右孩子
//因为该节点处于双亲节点的右边，所以传进的位置参数为0
leaf[1].setPosition(0);
length -= 2; //将数组的长度减小2个单位
//对数组进行移位，因为前两个元素已经被挂在新的节点上
leaf = move(leaf,2);
leaf[length++] = temp;//添加新的节点放在数组最后面，并将数组长度加1
}
result = leaf[length - 1];//得到最终数组中的唯一一个元素的引用
}
return result;
}
/**
* 对节点数组进行移位，按照传进来的跨度extent来对数组元素进行移动
* @param node 传进的需要移位的数组
* @param extent 传进的需要移位的跨度大小
* @return 返回完成移位的数组
*/
private Node[] move(Node[] node,int extent){
for(int i = 0; i < length; i++){
node[i] = node[i + extent];
}
return node;
}
/**
* 遍历生成的哈夫曼树，输出叶节点上的字母的哈夫曼编码
* @param head
*/
private void showResult(Node head){
if(head.getLeft() == null && head.getRight() == null){ //当找到叶节点时
//首先输出叶节点上的字母
System.out.print(head.getValues() + " 哈夫曼编码是：");
Node temp = head; //创建动态节点变量指向此时的叶节点
String posi = ""; //创建空字符串，用来保存字母的哈夫曼编码
while(temp.getPosition() != null){//向上循环，找该节点的双亲，直到找到根节点
//每找到一个节点，就将它的位置参数读取出来，添加进编码字符串
posi = temp.getPosition() + posi;
temp = temp.getParent();//然后再让该节点指向它的双亲节点
}
System.out.println(posi); //最后输出哈夫曼编码
}else{
showResult(head.getLeft());
showResult(head.getRight());
}
}
}
那么我们可以看到，对于哈夫曼编码生成的主要部分已经完成，那么我们可以试着编写
如下简单的测试类，进行测试哈夫曼编码生成的效果。
测试部分：
/**
* 该类用于测试哈夫曼树的生成情况
* @author LONG 2013-04-05
* @version V4.0
*
*/
public class Manager {
public static void main(String[] args){
HuffmanTree hf = new HuffmanTree(6);
hf.add('s',12);
hf.add('a',2);
hf.add('c',21);
hf.add('b',7);
hf.add('e',9);
hf.add('f',11);
hf.showCode();
}
}
那么我们会得到如下所示结果：
可以看到在控制台输出了哈夫曼编码的结果，在这个过程中，用户只需要指定需要存入的字母的个数，
以及将字母及其频率添加进去，就可以自动得到哈夫曼编码。
但是用户如果输入有误，比如说添加的字母大于指定的字母数，或是小于指定的字母数，或是字母出
现重复，那么会有以下结果：
1.添加的字母大于指定的字母数
2.添加的字母小于指定的字母数
3.字母出现重复
至此，哈夫曼编码的自动生成OK了！下来就是对发报机的进一步研究。。。。。。