Huffman Tree是树的带权路径最短的树,每次都从一堆节点中选出权值最小的两个节点组合成一个新的节点,原来的节点从那堆节点中删去,新产生的节点加入到那堆节点中。
伪代码如下,利用HuffmanTree上节点数已知的特点逐个构建树上非叶子结点,然后从叶子到根去得到HuffmanCode
HUFFMAN(n, key[], huffcode[]) leaf = Node[2*n]//一共有2*n-1个节点,零号节点不用 priority_queue<Node*> pq for i = 1 to n leaf[i].parent = leaf[i].left = leaf[i].right = 0 leaf[i].key = key[i] pq.push(&leaf[i]) for i = n+1 to 2*n-1//创建n-1个非叶子节点,同时创建HuffmanTree top1 = pq.pop() top2 = pq.pop() leaf[i].key = top1.key + top2.key leaf[i].left = top1 leaf[i].right = top2 leaf[i].parent = nil pq.push(&leaf[i]) for i = 1 to n//从叶子到根得到每个字符的huffman编码 p = &leaf[i] while p->parent != nil q = p->parent if p == q.left huffcode[i] = '0' + huffcode[i] else huffcode[i] = '1' + huffcode[i]