TNode.java

定义Huffman编码的节点
/**
 *

 赫夫曼编码的节点定义类

 *
 * @version 1.0, 2007-01-8
 * @author 
 * @since JDK1.6
 */
class TNode
{
    /**权值*/
    protected int w;
    /**左孩子节点*/
    TNode lChild = null;
    /**右孩子节点*/
    TNode rChild = null;

    /**（仅对叶子节点有效）赫夫曼编码*/
    String huffCode = null;

    /**
     * 构造一个赫夫曼编码节点的实例。设定左右子树和权值
     *
     * @param w int 权值
     * @param l TNode 左孩子节点
     * @param r TNode 右孩子节点
     */
    public TNode(int w,TNode l,TNode r)
    {
        this.w = w;
        lChild = l;
        rChild = r;
    }

    /**
     * 构造一个赫夫曼编码叶子点的实例。仅仅设定权值
     *
     * @param w int 权值
     */
    public TNode(int w)
    {
        this.w = w;
    }

    /**
     * 判断本节点是否为叶子节点
     *
     * @return boolean 为叶子节点则返回true
     */
    public boolean isLeaf()
    {
        return (rChild==null && lChild == null);
    }

    /**
     * 返回本节点的权值
     *
     * @return int 本节点的权值
     */
    public int getWeight()
    {
        return w;
    }

    /**
     * 返回本节点的左孩子节点
     *
     * @return TNode 左孩子节点
     */
    public TNode leftChild()
    {
        return lChild;
    }

    /**
     * 返回本节点的右孩子节点
     *
     * @return TNode 右孩子节点
     */
    public TNode rightChild()
    {
        return rChild;
    }

    /**
     * 设置节点的赫夫曼编码
     * @param str String 被设置的赫夫曼编码
     */
    public void setHuffCode(String str)
    {
        huffCode = str;
    }

    /**
     * 得到节点的赫夫曼编码
     * @return String 被设置的赫夫曼编码
     */
    public String getHuffCode()
    {
        return huffCode;
    }
}

Tree.java

import java.util.*;

/**
 *

 最优二叉树类

 *
 * @version 1.0, 2007-01-8
 * @author 
 * @since JDK1.6
 */
class Tree
{
    /**最优二叉树的根节点*/
    protected TNode root;

    /**存储叶子节点的权值*/
    protected List<Integer> leafWList = new ArrayList<Integer>();

    /**临时队列，用于存放待组合的节点*/
    protected List<TNode> tmpList = new LinkedList<TNode>();

    /**存放带权节点*/
    protected TNode[] leafArr = null;

    /**
     * 从键盘读取各个权值
     *
     */
    public void getLeafWeight()
    {
        Scanner scan = new Scanner(System.in);

        System.out.println("请输入各叶子节点的权值，0为结束：");

        while(scan.hasNextInt())
        {
            int i = scan.nextInt();

            if(i==0)
                break;
            leafWList.add(new Integer(i));
        }

        scan = null;

        return ;
    }

    /**
     * 找出临时队列中权值最小的节点从队列中移出并返回
     *@return TNode 权值最小的节点
     */
    public TNode min()
    {
        Iterator<TNode> itr = tmpList.iterator();
        TNode minNode = itr.next();
        int min = minNode.getWeight();

//找到最小的节点
        TNode tmpNode;
        while(itr.hasNext())
        {
            tmpNode = itr.next();
            if(tmpNode.getWeight()<min)
            {
                min = tmpNode.getWeight();
                minNode = tmpNode;
            }
        }

//最小的节点移出临时队列
        tmpList.remove(minNode);

//处理垃圾
        itr = null;
        tmpNode = null;

        return minNode;

    }

    /**
     * 根据权值创建叶子节点并加入临时队列
     *
     */
    public void makeLeafNode()
    {
        leafArr = new TNode[leafWList.size()];

        for(int i=0;i<leafWList.size();i++)
        {
            TNode node = new TNode(leafWList.get(i).intValue());
            leafArr[i] = node;
            tmpList.add(node);
        }
    }

    /**
     * 根据权值构造最优的二叉树
     *
     */
    public void makeBestTree()
    {
//根据权值创建叶子节点并加入临时队列
        makeLeafNode();

        TNode minNode1 = null,minNode2 = null;
        TNode node = null;
//构造最优树
        while(tmpList.size()!=1)
        {
            minNode1 = min();
            minNode2 = min();

            node = new TNode(minNode1.getWeight()+minNode2.getWeight(),minNode1,minNode2);
            tmpList.add(node);
        }

        root = node;

    }
    /**
     * 先序遍历的递归调用
     *
     */
    protected void preT(TNode t)
    {
        if(t.isLeaf())
        {
            System.out.print(t.getWeight() + " ");
            return ;
        }
        else
        {
            System.out.print(t.getWeight() + " ");
            preT(t.lChild);
            preT(t.rChild);
        }
    }

    /**
     * 先序遍历最优二叉树
     *
     */
    public void preOrderTraverse()
    {
        preT(root);
    }

    public static void main(String [] args)
    {
        Tree t = new Tree();
        t.getLeafWeight();
        t.makeBestTree();
        t.preOrderTraverse();
    }
}

HuffmanCode.java

/**
 *

 赫夫曼编码类

 *
 * @version 1.0, 2007-01-8
 * @author 
 * @since JDK1.6
 */
public class HuffmanCode extends Tree
{

    public HuffmanCode()
    {
        init();
    }

    /**
     * 初始化节点值并构造最优二叉树
     *
     */

    public void init()
    {
        super.getLeafWeight();
        super.makeBestTree();
    }

    /**
     * 生成赫夫曼编码的递归函数
     *
     * @param t TNode 当前遍历节点
     * @param s String 目前遍历至此的赫夫曼编码
     */
    protected void hufT(TNode t,String s)
    {
        if(t.isLeaf())
        {
            t.setHuffCode(s);
        }
        else
        {
            hufT(t.lChild,s+"0");
            hufT(t.rChild,s+"1");
        }
    }

    /**
     * 生成赫夫曼编码的外部调用函数
     *
     */
    public void makeHuffCode()
    {
        hufT(root,"");

    }

    /**
     * 查看所有的赫夫曼编码值
     *
     */
    public void viewHuffCode()
    {
        for(int i=0;i<leafArr.length;i++)
        {
            System.out.println(leafArr[i].w + ":" +leafArr[i].getHuffCode());
        }
    }

    public static void main(String [] args)
    {
        HuffmanCode hc = new HuffmanCode();
        hc.makeHuffCode();
        hc.viewHuffCode();
    }
}