数据结构第14讲

《数据结构第14讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构——第14讲主讲：张华杰Napoleonz@163.com0371-7657211第14讲Huffman树树的高级话题章节范围：6.5~6.8上次课的内容线索二叉树概念:线索、线索链表、线索二叉树、线索化算法如何找树中指定结点在某种序下的直接前驱/后继？如何对二叉树进行线索化？在线索二叉树上如何遍历？先/中/后序线索二叉树的特征树和森林树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法森林与二叉树的转换：二叉链表(firstchild-lchild,nextsibling-rchild)树和森林的遍历：先根遍历(先序)、后根遍历(中序)-

2、-赫夫曼(Huffman)树及其应用树与等价问题回溯法与树的遍历树的计数开拓问题求解的思路！--6.6赫夫曼树及其应用最优树路径长度：路径上的分支数目树的路径长度：树根到每一结点的路径长度之和结点的带权路径长度：该结点到树根之间的路径长度与结点上权的乘积树的带权路径长度：树中所有叶子结点的带权路径长度之和最优二叉树或赫夫曼树：树的带权路径长度最小的二叉树--6.6-不同带权路径长度的二叉树abcd0100117524000111cdba7524WPL=2*(7+5+2+4)=36WPL=1*7+2*5+3*(2+4)=35--6.6–赫夫曼树的应用赫

3、夫曼树的应用——最佳判定算法分数0~5960~6970~7980~8990~100比例0.050.150.400.300.10等级不及格及格中等良好优秀a<60?不及格0.050.150.400.300.10NNNNYYYYa<70?a<80?及格a<90?中等良好优秀WPL=3.15--6.6–赫夫曼树的应用(续)赫夫曼树的应用——最佳判定算法不及格0.050.150.400.300.10及格中等良好优秀WPL=2.0570≤a<8080≤a<90YN60≤a<70YNa<60NYNY--6.6–赫夫曼算法赫夫曼算法根据给定的n个权值构成n棵二叉树

4、的集合F，其中每棵二叉树中只有一个带权值的结点；在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和；在F中删除这两棵树，同时将新得到的二叉树加入到F中；重复2)和3)，直到F中只含一棵树为止。--6.6–赫夫曼树的特点赫夫曼树(最优二叉树)的特点赫夫曼树中无度为1的结点，为什么？若有n个权值，则形成的赫夫曼树中有2n-1个结点赫夫曼树的高度h与结点数m之间的关系若赫夫曼树的高度为h(h>0)，则树中最多有2h-1个结点满二叉树最少有2h-1个结点--6.6–赫夫曼编码赫

5、夫曼编码问题描述：已知电文中出现的一组字符及出现频率，试为该组字符编码以使得电文总长最短。前缀编码：某字符的编码不是其他字符编码的前缀赫夫曼编码过程：1)由n个权值，形成包含有2n-1个结点的赫夫曼树2)约定赫夫曼树的左分支表示字符‘0’，右分支表示字符‘1’，则从根结点到叶子结点的路径上的分支字符组成的字符串作为该叶子结点字符的编码。赫夫曼树和赫夫曼编码的存储结构选取由权值数n唯一确定树中的结点数一次性分配结点空间编码：从叶子到根的路径快速访问双亲译码：从根到叶子的路径快速访问孩子赫夫曼树：三叉静态链表--6.6–算法与例子赫夫曼编码的算法

6、教材P147算法6.12教材P148例6-25381119234278151429295810000000001111111平均码长=(0.23+0.29)*2+(0.11+0.14)*3+(0.05+0.03+0.07+0.08)*4=1.04+0.75+0.92=2.71若电文有1000个字符，则电文的码长为2.71*1000=2710--6.56.76.8开拓问题求解的思路6.5树与等价问题6.7回溯法与树的遍历6.8树的计数--6.5树与等价问题(1)等价关系和等价类如果集合S中的关系R是自反的、对称的和传递的，则称它为一个等价关系。设

7、R是集合S的等价关系。对任何x∊S,由[x]R={y

8、y∊S⋀xRy}给出的集合[x]R⊆S称为由x∊S生成的一个R等价类。如何划分等价类？问题描述：设集合S有n个元素，m个形如(x,y)(x,y∊S)的等价偶对确定了等价关系R，需求S的划分。--6.5树与等价问题(2)算法思想S中每个元素各自形成一个只含单个成员的子集对于输入的每一偶对(x,y)，判定x和y所属子集Si和Sj，若Si≠Sj，则将Si并入Sj并置Si为空(或将Sj并入Si并置Sj为空)需要用到的在集合上的操作构造只含单个成员的集合；判定某个单元素所在子集；归并两个互不相交的集合为一

9、个集合。抽象数据类型MFSet(见教材P140)--6.5树与等价问题(3)集合的表示位向量、有序表等MF