哈夫曼树（最优二叉树）

带权路径长度结点的权有某种现实含义的数值如表示结点的重要性等结点的带权路径长度从树的根到该结点的路径长度经过的边数与该结点上权值的乘积树的带权路径长度树中所有叶结点的带权路径长度之和WPL, Weighted Path LengthWPL∑i1nwili\mathrm{WPL} \sum_{i1}^{n} w_{i}l_{i}WPLi1∑n​wi​li​哈夫曼树的定义在含有nnn个带权叶结点的二叉树中其中带权路径长度WPL最小的二叉树称为哈夫曼树也称最优二叉树。哈夫曼树的构造给定nnn个权值分别为w1,w2,...,wnw_1, w_2,..., w_nw1​,w2​,...,wn​的结点构造哈夫曼树的算法描述如下1将这nnn个结点分别作为nnn棵仅含一个结点的二叉树构成森林FFF。2构造一个新结点从FFF中选取两棵根结点权值最小的树作为新结点的左、右子树并且将新结点的权值置为左、右子树上根结点的权值之和。3从FFF中删除刚才选出的两棵树同时将新得到的树加入FFF中。4重复步骤2和3直至FFF中只剩下一棵树为止。哈夫曼编码固定长度编码——每个字符用相等长度的二进制位表示可变长度编码——允许对不同字符用不等长的二进制位表示若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码由哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点各个字符出现的频度作为结点的权值。可以用于数据的压缩