哈夫曼树的定义:给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree),哈夫曼树是带权路径长度最短的树。权值较大的结点离根较近。
权:将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。
结点的带权路径长度:从根结点到该结点之间路径长度与该结点的权的乘积。
树的带权路径长度:树中所有叶子结点的带权路径长度之和
前缀码:如果在一个编码系统中,任一个编码都不是其他任何编码的前缀(最左子串),则称该编码系统中的编码是前缀码。例如,一组编码01,001,010,100,110就不是前缀码,因为01是010的前缀,若去掉01或010就是前缀码。例如,名字中的郑霞、郑霞锦就不是前缀码。
哈夫曼编码:对一棵具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,右分支赋予1,则从根到每个叶子的通路上,各分支的赋值分别构成一个二进制串,该二进制串就称为哈夫曼编码。
每次用最小的两个元素构建子树,父节点为两元素之和,按这个规则构成一整颗哈夫曼树