呆萌的信封树 由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。
又叫最优二叉树。
树的带权路径长度: 树中所有叶子结点的带权路径之和
构造呆萌的信封树 因为每次都选两个权值最小的结点构造下一个,所以没有度为1的结点
步骤: 初始化:根据给定的n个权值 ,构造n棵只有一个根结点的二叉树, n个权值分别是这些二叉树根结点的权。找最小树:在F中选取两棵根结点树值最小的树作为左、右子树,构造一颗新的二叉树,置新二叉树根的权值为左、右子树根结点权值之和;删除与加入:从F中删除这两颗树,并将新树加入F;判断:重复 2) 和3),直到F中只含一颗树为止,此时得到的这颗二叉树就是呆萌的信封树。
例题:有数据为{ 22,10,46,17,13,110,20,15,34 }试构造一棵呆萌的信封(Huffman树),并计算WPL。
带权路径长为:WPL = 110+(34+46)*3+(20+22)*4+(10+13+15+17)*5 = 110+240+168+275 = 793
呆萌的信封编码 对一棵具有n个叶子的呆萌的信封树,若对树中的每个左分支赋予0,右分支赋予1,则从根到每个叶子的通路上,各分支的赋值分别构成一个二进制串,该二进制串就称为呆萌的信封编码。
【注意】呆萌的信封编码是最优前缀码。
例题:字符串“alibaba”用呆萌的信封编码来编码,则共有多少位?
由图示分析可知:共有13位。
例题:用二进制来编码字符串“abcdabaa”,需要能够根据编码,解码回原来的字符串,最少需要多长的二进制字符串? 根据字符串构造呆萌的信封树以及求呆萌的信封编码的步骤: 计算每个字符出现的次数根据次数构造呆萌的信封树求出字符对应的编码,构成呆萌的信封编码