Question

第十一章：树结构应用之哈夫曼编码解码

Answer 1

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

编码：
1.输入字符串，通过getWeight()获取其权重即每个字符出现的次数并利用权重及字符生成Node结点，组成sourceData列表。
2.调用makeHuffman()方法，通过getmin2()函数可获得最小权重的两个字符，再让其形成父亲结点，并赋予左子结点右子结点，遍历sourceData完生成huffman结点，即哈夫曼树的根结点。
3.调用traverse()方法，将以huffman为根结点的树遍历形成列表。
4.调用strToHuffmanCode()方法，会去调用getCode()方法，会去根据huffman形成路径表route2，再跟原字符串一个一个字符进行比对，找到就添加其路径最终生成huffmancode
5.获取二进制表示的哈夫曼编码后，调用huffmanCodeBytes函数可以将二进制树转为带符号的十进制树，以八位二进制数为一组例如11010110,第一位为符号位，1表示负转为十进制数应将其余位取反并加1，再转为十进制数再*-1，就可以得到最终的十进制数。
解码：
调用decimalToBinary()函数将带符号的十进制数转为二进制数，再调用byteToBitString()比对route路径表 得到字符