数据结构题目60：哈弗曼编码的算法

题目：对m个字符进行编码，这m个字符用序号（1，2，3，...，m）代表，对应的权值集合为W=(w1, w2, w3, ..., wm)。
解题思路：根据二叉树的性质可知，具有m个叶结点的哈夫曼树共有n=2m-1个结点。因此算法中设置一个数组weight[0,..,n-1]分别存放n个结点的权值；数组parent[0,..,n-1]分别存放结点的双亲结点的位置；lchild[0,..,n-1]分别存放结点的左孩子位置；rchild[0,..,n-1]分别存放结点的右孩子位置（实际上，哈夫曼树采用的一种静态的三叉链表结构）；二维数组code[0,..,m-1][0,..,m-1]用来存放m个字符的哈夫曼编码，其中每个数组元素为一个二进制位，第i行中给出的是第i个字符的哈夫曼编码。
算法构成两部分：

1. 构造出哈夫曼树
   构造步骤如下：
   1.初始时，输入weight[0]至weight[m-1]的值，而所有parent, lchild与rchild域均置为0。于是，构成m棵树的树林。
   2.利用子算法SELECT(i-1,s1,s2)在树林中选择两棵根的权值最小的子树，其根结点分别有s1与s2指出，把s1与s2合并为以i为根的二叉树，s1与s2的parent指向i而不再是0。
   3.重复步骤2，直到构成具有m个叶结点的哈夫曼树。
2. 在哈夫曼树上完成对每个叶结点的编码
   对于每个叶结点，都是从叶结点开始到根结点为止来判断路径上每一条树枝是左树枝还是右树枝，从而在二维数组code的第i行中从第m列开始往左逐位填入相应的二进制元素。算法中设置一个数组start[0..m-1]，其中，start[i]用来指示填入的位置。当第i个叶结点编码完成时，start[i]的终值填入数组start中。第i个字符的编码为数组code中第i行从start[i]+1列开始到第m列为止的二进制位序列。下面给出算法和实例，可以进行观察分析。

const M=100
function HUFF_CODE(w, weight, parent, lchild, rchild, start, code, n, m) {
    let w=new Array(M), weight=[], parent=[], lchild=[], rchild=[], start=[], code=[][M], n, m
    let i, f, s1, s2, c
    for (i = 0; i < n; i++) {
        parent[i] = 0;
        lchild[i] = 0
        rchild[i] = 0
    }
    for (i = 0; i < m; i++) {
        weight[i] = w[i]
    }
    for (i = m; i < n; i++) {
        Selection(i-1, s1, s2)
        parent[s1] = i
        parent[s2] = i
        lchild[i] = s1
        rchild[i] = s2
        weight[i] = weight[s1] + weight[s2]
    }
    for (i = 0; i < m; i++) {
        start[i] = m
        f = parent[i]
        c = i
        while (f!=0) {
            if ( lchild[f] == 0 ) {
                code[i][start[i]] = 0
            } else {
                code[i][start[i]] = 1
            }
            start[i]--
            c = f
            f = parent[f]
        }
    }
}

实例：以"time tries truth"为例，有D=(t,i,m,e,r,s,u,h)，并以(1,2,3,4,5,6,7,8)来代表，则相应的权值集合为W=(4,2,1,2,2,1,1,1)。根据上述算法可以得到哈夫曼树的初始状态，结果状态，各字符的哈夫曼编码。