哈夫曼树.ppt

2020/6/131哈夫曼树及其应用2.路径长度4.结点的权3.树的路径长度5.结点带权路径长度6.树的带权路径长度1.路径什么是哈夫曼树哈夫曼树（最优树）及其应用路径长度的概念路径：从一个结点到另一个结点之间的分支序列结点之间的路径长度：从一个结点到另一个结点之间的分支数目树的路径长度（用PL表示）：从树的根到每一个结点的路径长度之和PL=0＋1＋1＋2＋2＋2＋2＋3＝1301432567PL=0＋1＋1＋2＋2＋3＋3＋3＝1501432567结点的权：给树的每个结点赋予的一个具有某种实际意义的实数。结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中叶子结点带权路径长度之和。abcd7524WPL=7*2+5*2+2*2+4*2=36树的带权路径长度记作：其中：Wi为树中每个叶子结点的权；Li为每个叶子结点到根的路径长度。niiiLWWPL1abcd7524WPL=7*2+5*2+2*2+4*2=36WPL最小的二叉树就称作最优二叉树或哈夫曼树。abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35哈夫曼树（最优树）加权路径长度最小的二叉树就是哈夫曼树。公式：niiiLWWPL12020/6/137具有不同带权路径长度的二叉树哈夫曼树带权路径长度达到最小的扩充二叉树即为哈夫曼树。哈夫曼树中，权值大的结点离根最近。2020/6/138问题1：什么样的二叉树的路径长度PL最小？一棵二叉树的路径长度为0结点至多只有1个（根）；路径长度为1结点至多只有2个（两个孩子）；路径长度为2结点至多只有4个；依此类推：路径长度为K结点至多只有2k个，所以n个结点的二叉树其路径长度至少等于如下序列的前n项之和。路径长度0，1，1，2，2，2，2，3，3，3，3，3，3，3，3，4，4，...结点数kk=1k=2k=3k=4k=5k=6k=7k=8...k=15由此可知，结点n对应的路径长度为log2n，所以前n项之和为:hk=1log2k2020/6/139完全二叉树的路径长度为：20×0+21×1+22×2+…+2h×h=hk=1log2kh为树的深度，其路径长度可达到最小，所以完全二叉树具有最小路径长度的性质，但不具有唯一性。例如：下列不同形状的二叉树均具有最小的路径长度ABCDEPL=0+1+1+2+2=6ABDCEPL=0+1+1+2+2=62020/6/1310问题2：什么样的带权树路径长度最小？例如：给定一个权值序列{2,3,4,7}，可构造的多种二叉树的形态。(a)WPL=2×2＋2×3+2×4+2×7=3223474237(b)WPL=1×2＋2×3+3×4+3×7=4142373742(c)WPL=1×7＋2×4+3×3+3×2=3018a711cdb5624(d)abcd7524(a)哈夫曼树的构造例：给定权值{7，5，2，4}，构造哈夫曼树。(b)6abcd75(c)11b5acd7方法：（1）初始化：由原始数据生成森林；（2）找最小树：在森林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。规定左子树根结点的权值小于右子树根结点的权值。（3）删除与加入：将新的二叉树加入到森林F中，去除原两棵权值最小的树；（4）判断：重复2、3步骤，直至F中只剩一棵树为止。哈夫曼树的应用（1）判定树在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。例1将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图（a)二叉树结构来实现。a60a70a80a90不及格中等良好优秀及格YNYNYNYN(a)输入10000个数据，则需进行28000次比较。分数0—5960—6970—7980—8990—99比例0.050.150.40.30.1070≤a80a6080≤a9060≤a70(b)(c)学生成绩分布不是均匀的情况：以比例数为权构造一棵哈夫曼树，如（b)判断树所示。再将每一比较框的两次比较改为一次，可得到（c)判定树。输入10000个数据，仅需进行22000次比较。2020/6/13192、哈夫曼编码(1)前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编码01，001，010，100，110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。(2)哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。哈夫曼树的应用2020/6/1320定理6-1哈夫曼编码是前缀码。证明：哈夫曼编码是根到叶子路径上的边的编码的序列，也就是等价边序列，而由树的特点知，若路径A是另一条路经B的最左部分，则B经过了A，因此，A的终点不是叶子。而哈夫曼编码都对应终点为叶子的路径，所以，任一哈夫曼码都不会与任意其他哈夫曼编码的前部分完全重叠，因此哈夫曼编码是前缀码。2020/6/1321定理6-2哈夫曼编码是最优前缀码。即对于n个字符，分别以它们的使用频度为叶子权，构造哈夫曼树，则该树对应的哈夫曼编码，能使各种报文（由这n种字符构成的文本）对应的二进制串的平均长度最短。证明：由于哈夫曼编码对应叶权为各字符使用频度的哈夫曼树，因此，该树为带权长度最小的树，即最小，其中Wi是第i个字符的使用频度，而Pi是第i个字符的编码长度，这正是度量报文的平均长度的式子。n1iiiwp146833442200001111T;ACS各字符编码是T；ACS000110110111上述电文编码：11010111011101000011111000011000方法：（1）用{2，4，2，3，3}作为叶子结点的权值生成一棵哈夫曼树，并将对应权值wi的叶子结点注明对应的字符；（2）约定左分支表示字符“0”，右分支表示字符‘1’（3）从叶子结点开始，顺着双亲反推上去，直到根结点，路径上的‘0’或‘1’连接的序列就是结点对应的字符的二进制编码的逆序。例2：要传输的电文是{CAS；CAT；SAT；AT}要传输的字符集是D={C，A，S，T，；}每个字符出现的频率是W={2，4，2，3，3}注意：编码的总长度恰好为哈夫曼树的带权路径长。构造二叉树给定一棵二叉树的先序序列和中序序列，可唯一确定一棵二叉树例：已知结点的先序遍历序列和中序遍历序列分别为：先序遍历序列：18，14，7，3，11，22，35，27中序遍历序列：3，7，11，14，18，22，27，35181473112235271、对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）实现编号。A）先序遍历B）中序遍历C）后序遍历D）从根开始进行层次遍历2、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A）空或只有一个结点B）高度等于其结点数C）任一结点无左孩子D）任一结点无右孩子3、有n个叶子结点的哈夫曼树的结点总数为（）A）不确定B）2nC）2n＋1D）2n－1CBD4、除根结点外，树上每个结点（）。A）可有任意多个孩子、任意多个双亲B）可有任意多个孩子、一个双亲C）可有一个孩子、任意多个双亲D）可有一个孩子、一个双亲5、树用双亲链表表示，则（）。A）可容易地实现求双亲及子孙的运算B）求双亲及子孙的运算均较困难C）可容易地实现求双亲运算，但求子孙运算较困难D）可容易地实现求子孙运算，但求双亲运算较困难BC6、若对一棵有16个结点地完全二叉树按层编号，则对于编号为7的结点x，它的双亲结点及右孩子结点的编号分别为（）。A）2，14B）2，15C）3，14D）3，157、如右图所示的二叉树，（1）其中序遍历序列为：（2）其先序遍历序列为：（3）其后序遍历序列为：（4）该二叉树的中序线索二叉树为：（5）该二叉树对应的森林为：Dabcdefjhi