数据结构与算法 课件 第五章树与二叉树.ppt

变长编码变长编码前缀特性：一个编码方案中，任何一个字符的编码都不是该方案中任何其他字符编码的前缀，这样的编码称为具有前缀特性正是因为编码方案具有前缀特性，才能够保证译码过程的正确性和唯一性。可以使用二叉树来表示一个编码方案在二叉树的分支上标注0或1，从根到某结点的路径上，各分支标注的0或1组成一个编码哈夫曼树二叉树中，叶结点的带权路径长度定义为叶结点的权值乘上其到根结点的路径长度二叉树的带权路径长度，就是树中所有叶结点的带权路径长度之和二叉树的外部带权路径长度记为WPL其中n为叶结点个数，wk为第k个叶结点的权值，lk为第k个叶结点的路径长度各字符出现的频度分别是6、12、25、30，构造4棵二叉树，分别计算其WPL值4棵二叉树的带权路径长度WPL分别为134、195、139和146我们的任务是构造具有最小WPL且满足前缀特性的编码树设有n个权值{w1,w2,…,wn}，构造具有n个叶结点的二叉树，每个叶结点带有一个权值wi。在所有这样的二叉树中，带权路径长度WPL最小的一棵二叉树称为哈夫曼树构造哈夫曼树的算法根据给定的n个权值{w1,w2,…,wn}(n≥2)，构造含n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti(1≤i≤n)只有一个根结点，它带有权值wi(i=1,2,…,n)在F中选出两棵根结点权值最小（如果有相等的权值，则任意选）的二叉树分别作为左、右子树，新增加一个根结点，从而构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点的权值之和。然后从F中删去选出的这两棵树，加入这棵新构造的树重复步骤②，直到F中只有一棵树时为止，这棵树就是哈夫曼树示例已知字符集S={a,b,c,d,e}，对应的权值为{17,25,12,6,14}，试构造哈夫曼树，并计算其WPL初始时，5个权值分别对应一棵单结点的树，并按权值从小到大排序选择权值最小的两棵树进行合并，新增加的根结点表示为圆形结点。新树的根结点的权值是18，选择权值小的树作为左子树，权值大的树作为右子树继续选择权值最小的两棵树进行合并。新树的根结点的权值是31。将选中的两棵树删除，增加新合并的树继续这个过程最后得到的结果WPL=14?2+17?2+6?3+12?3+25?2=166哈夫曼算法得到的哈夫曼树中没有度为1的结点，因为每次合并时都选择了两棵树分别作为左子树和右子树初始时如果给定的权值个数为n，则哈夫曼树的构建过程需要n-1步。得到的哈夫曼树中，叶结点个数为n，分支结点个数为n-1，结点总数为2n-1哈夫曼编码在哈夫曼树中，对于所有的分支结点，其左分支标以0，右分支标以1。这样标记以后，将从根到叶结点的路径上标记的0和1依次收集起来，可以得到叶结点对应字符的具体编码，这就是哈夫曼编码哈夫曼树及编码编码的带权平均码长=译文总位数/原文字符总数=166/74?2.24已知译文其原文是什么？从哈夫曼树根开始，根据编码的各位决定选择的分支，前2位是11，故得到字符b。接下来，00对应于字符e。依此类推。最终得到的原文是becabdeb**画出表达式树先根据运算符的优先级对表达式加括号去掉最外层括号。中间的运算符为根，前后两部分分别对应于左子树和右子树对左子树递归执行步骤②对右子树递归执行步骤②当遇到空串时，递归结束例5-12已知算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE答案：D第四节堆及优先队列前一种关系表明，任何一个分支结点的值都不大于它子结点的值，所以树根结点的值是全部结点中的最小值。这样的堆称为最小堆或小根堆后一种关系表明，任何一个分支结点的值都不小于它子结点的值，故树根结点的值是全部结点中的最大值。这样的堆称为最大堆或大根堆树根结点称为堆顶堆的定义中还隐含了递归的含义，当用完全二叉树的形式表示堆时，树中的任意一棵子树都可以构成堆，并且保持与原来同样的性质最大堆中任何结点的子树仍是最大堆最小堆中任何结点的子树仍是最小堆最小堆和最大堆堆的类型定义#defineHeapSize30 //堆的容量typedefintELEMType; //元素类型typedefstructHeap{ ELEMTypeheap[HeapSize]; //存放元素的数组 intn; //堆中当前元素个数};堆的基本操作intcreatHeap(maxHeap*H,ELEMTypearr[]