一 点睛

在构造哈夫曼树的过程中，首先将每个节点的双亲、左孩子、右孩子都初始化为-1，找出所有节点中双亲为 -1 且权值最小的两个节点 t1 和 t2，并合并为一棵二叉树，更新信息（双亲节点的权值为 t1、t2 权值之和，其左孩子为权值最小的节点 t1，右孩子为次小的节点 t2，t1、t2 的双亲为双亲节点的编号）。重复此过程，建成一棵哈夫曼树。

二 数据结构

每个节点的结构都包括权值、双亲、左孩子、右孩子、节点字符信息五个域。如下图所示：

| <br>weight<br> | <br>parent<br> | <br>lchild<br> | <br>rchild<br> | <br>value<br> |

在结构体的编码过程中，bit[] 存放节点的编码，start 记录编码开始时的下标，在逆向编码存储时，start 从 n-1 开始依次递减，从后向前存储，当读取时，从start+1 开始到 n-1，从前向后输出，即该字符的编码。

三 算法实现

package tree;

import java.util.Scanner;

public class Huffman {
    static int MAXBIT = 100;
    static int MAXVALUE = 10000;
    static int MAXLEAF = 30;
    static int MAXNODE = MAXLEAF * 2 - 1;

    /* 构造哈夫曼树 */
    static void HuffmanTree(HNodeType HuffNode[], int n) {
    /*
    i、j： 循环变量，
    m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
    x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
        int i, j, x1, x2;
        double m1, m2;
        Scanner scanner = new Scanner(System.in);
        /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
        for (i = 0; i < 2 * n - 1; i++) {
            HuffNode[i].weight = 0; // 权值
            HuffNode[i].parent = -1;
            HuffNode[i].lchild = -1;
            HuffNode[i].rchild = -1;
        }
        /* 输入 n 个叶子结点的权值 */
        for (i = 0; i < n; i++) {
            System.out.println("请输入节点字符和节点权值：");
            HuffNode[i].value = scanner.next().charAt(0);
            HuffNode[i].weight = scanner.nextInt();
        }
        /* 构造 Huffman 树 */
        for (i = 0; i < n - 1; i++) { // 执行 n-1 次合并
            /* m1、m2 中存放两个无父结点且结点权值最小的两个结点 */
            m1 = m2 = MAXVALUE;
            x1 = x2 = 0;
            /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一棵二叉树 */
            for (j = 0; j < n + i; j++) {
                if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1) {
                    m2 = m1;
                    x2 = x1;
                    m1 = HuffNode[j].weight;
                    x1 = j;
                } else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1) {
                    m2 = HuffNode[j].weight;
                    x2 = j;
                }
            }
            /* 设置找到的两个子结点 x1、x2 的父结点信息 */
            HuffNode[x1].parent = n + i;
            HuffNode[x2].parent = n + i;
            HuffNode[n + i].weight = m1 + m2;
            HuffNode[n + i].lchild = x1;
            HuffNode[n + i].rchild = x2;
            //System.out.println("本轮中X1的权值：" + HuffNode[x1].weight + "\t本轮中X1的权值:" + HuffNode[x2].weight); // 用于测试
        }
    }

    /* 哈夫曼树编码 */
    static void HuffmanCode(HCodeType HuffCode[], HNodeType HuffNode[], int n) {
        HCodeType cd = new HCodeType();       /* 定义一个临时变量来存放求解编码时的信息 */
        int i, j, c, p;
        for (i = 0; i < n; i++) {
            cd.start = n - 1;
            c = i;
            p = HuffNode[c].parent;
            while (p != -1) {
                if (HuffNode[p].lchild == c)
                    cd.bit[cd.start] = 0;
                else
                    cd.bit[cd.start] = 1;
                cd.start--;        /*前移一位 */
                c = p;
                p = HuffNode[c].parent;    /* 设置下一循环条件 */
            }
            /* 把叶子结点的编码信息从临时编码 cd 中复制出来，放入编码结构体数组 */
            for (j = cd.start + 1; j < n; j++)
                HuffCode[i].bit[j] = cd.bit[j];
            HuffCode[i].start = cd.start;
        }
    }

    public static void main(String[] args) {
        int i, j, n;
        System.out.println("请输入n：");
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        /* 定义一个结点结构体数组 */
        HNodeType HuffNode[] = new HNodeType[MAXNODE];
        /* 定义一个编码结构体数组*/
        HCodeType HuffCode[] = new HCodeType[MAXLEAF];
        for (int i1 = 0; i1 < HuffNode.length; i1++) {
            HuffNode[i1] = new HNodeType();
        }
        for (int i1 = 0; i1 < HuffCode.length; i1++) {
            HuffCode[i1] = new HCodeType();
        }

        HuffmanTree(HuffNode, n);  //构造哈夫曼树
        HuffmanCode(HuffCode, HuffNode, n);  // 哈夫曼树编码
        // 输出已保存好的所有存在编码的哈夫曼编码
        for (i = 0; i < n; i++) {
            System.out.println(HuffNode[i].value + "哈夫曼编码是：");
            for (j = HuffCode[i].start + 1; j < n; j++) {
                System.out.printf(" " + HuffCode[i].bit[j]);
            }
            System.out.println();
        }
    }
}

// 节点的数据结构
class HNodeType {
    public double weight;
    public int parent;
    public int lchild;
    public int rchild;
    public char value;
}

// 每个节点的编码
class HCodeType {
    public int bit[] = new int[Huffman.MAXBIT];
    public int start;
}

四 测试结果

绿色为输入，白色为输出。