数据结构导论第四章.ppt

《数据结构导论第四章.ppt》由会员分享，可在线阅读，更多相关《数据结构导论第四章.ppt（149页珍藏版）》请在三一办公上搜索。

1、1,复习前节,1、数据结构的基本概念2、顺序表、链表3、顺序栈、链栈4、顺序队、链队5、顺序串、链串6、数组和广义表,线性表,线性表的推广树的推广,2,第4章 树,4.1 树的基本概念4.2 二叉树4.3 二叉树的存储结构4.4 二叉树的遍历4.5 递归消除4.6 树和林4.7 判定树和哈夫曼树,3,本章项目：电文编码,4,文字,电文编码,电波,译码,摩尔斯电码（又译为摩斯电码）是一种时通时断的信号代码，这种信号代码通过不同的排列顺序来表达不同的英文字母、数字和标点符号等。它由美国人艾尔菲德维尔发明（1835年）。,5,网络信息传输：,文字,数字编码,电信号,电文编码,发送者,数字编码,文字,

2、电文编码,接收者,你好,0101010101,你好,核心问题：电文如何编码称为01串？,6,本章项目：电文编码问题涉及知识点：1、树的概念2、树的专业术语3、二叉树的概念4、哈夫曼树和哈夫曼编码,核心问题：如何将电报文字转换成可传送编码,7,自然中的树,抽象的树,知识点1：树的概念,8,旋转后,9,适当进行调整,A,B,C,D,E,F,G,H,I,10,数据结构中树的形态，具有分层特点,A,B,C,D,E,F,G,H,I,11,某姓氏族谱,12,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,.,对树中的结点给定一个符号名称，具有一对多的

3、特点,13,树描述的是一种层次结构，是一种一对多的逻辑关系,14,树(Tree)是n(n=0)个结点的有限集。n=0时称为空树。n1时，有且仅有一个称为根的结点；其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每个集合又是一棵树，称为子树,知识点1：树的概念,15,树的其他表示形式,A,B,C,D,E,F,H,G,M,16,结点：数据元素的内容及其指向其子树根的分支结点的度：结点拥有的子树的数目。树的度：树内各结点的度的最大值；,知识点2：树的专业术语,A、B、C、D、E、F、G、H、M均称为结点,A 结点的度为 2C 结点的度为 3M 结点的度为 0,树的度为3,17,叶子（

4、终端结点），非终端结点：度为0的结点称为叶子结点；度不为0的结点称为非终端结点。,18,结点的层数：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的高度（深度）：树中所有结点层次的最大值,19,孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；双亲在同一层的结点互为堂兄弟。,A是B、C的双亲,B、C是A的孩子,B、C是兄弟关系,E、F是堂兄弟关系,20,路径：若树中存在一个序列k1，k2kn，使得ki是ki+1的双亲，则称该结点序列为k1到kn的一条路径。路径长度：这些节点经过的边的条数,序列：A B D M E,序列：A

5、B D M,序列：A C F,是路径,非路径,是路径,21,子孙，祖先：以某结点为根的子树中的所有结点都被称为是该结点的子孙。从根结点到该结点路径上的所有结点称为该结点的祖先。,22,森林：多棵互不相交的树的集合构成森林,三棵树构成的森林,23,结点结点的度(Degree)叶子（Leaf)或终端结点分支结点或非终端结点树的度层次(Level)树的深度(Depth)孩子（child)双亲（Parent)兄弟(Sibling)祖先子孙路径,24,知识点3：二叉树的概念,二叉树(Binary Tree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子

6、树同样也都是二叉树,25,特征：每个结点最多只有两棵子树子树有左右之分，次序不能任意颠倒，只有一棵子树时也必须分清是左子树还是右子树,A,B,C,A,C,B,26,网络信息传输：,文字,数字编码,电信号,电文编码,发送者,数字编码,文字,电文编码,接收者,你好,0101010101,你好,核心问题：电文如何编码称为01串？,27,项目实现的进一步分析：项目核心问题：如何将电报文字转换成01编码 扩展问题：电文传送时的高效性,28,扩展问题：电文传送时的高效性,在计算机及通信中，常用二进制编码来表示字符，假设某电文通信中只使用A B C D四个字符每个字母用两位二进制数表示，例如传输100个字母

7、需要用200个二进制位,此种编码方式为等长编码，此时电文长度由电文字符数决定,对于电文：DABC可翻译为编码：对于编码：01 00 11 10可准确翻译为：,00表示A01表示B10表示C11表示D,B A D C,11 00 01 10,29,实际情况：字符在实际使用中出现频率不一样！,新问题1：如何让电文编码缩短,为提高电文传送效率，应让电文编码尽量短,考虑问题：出现频率高的字符编码位数少 出现频率低的字符编码位数多 以此降低电文总长度,常用汉字6335个，最常用字560个，常用字807个，次常用字1033个，共2400个。这些字占了书刊物汉字出现次数的99%,A 8.19 B 1.47

8、C 3.83 D 3.91E 12.25 F 2.26 G 1.71 H 4.57 I 7.10 J 0.14 K 0.41 L 3.77 前面十位是：E T A O I N R S D C,30,假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：,000 01 1 001 000,考虑问题：出现频率高的字符编码位数少 出现频率低的字符编码位数多 以此降低电文总长度,000表示A001表示B 01表示C 1表示D,A 5%B 10%C 15%D 70%,假定：,问题：传输100个字母所用的二进制位为,电文：ACDBA翻译成编码：编码：000 01 1 001翻译成电文:,35,+,3

9、10,+,215,170,+,=,145,A C D B,31,此种编码方式为不等长编码，采用不等长编码可缩短电文编码长度，从而提高电文传送效率,假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：,考虑问题：出现频率高的字符编码位数少 出现频率低的字符编码位数多 以此降低电文总长度,000表示A001表示B 01表示C 1表示D,A 5%B 10%C 15%D 70%,假定：,32,假定：,翻译：C B D B,翻译：C B D C D,新问题2：随意的不等长编码可能导致编码翻译时出现歧义,编码：000011001,问题：编码是任意给定的吗？,000表示A 001表示B 00表示C

10、1表示D,假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：,A 5%B 10%C 15%D 70%,000 01 1 00 1,00 001 1 001,00 001 1 00 1,错误！,错误！,33,新知识：设计不等长编码时，必须做到：任何一个字符的编码不能是另一个字符编码的前缀，这种编码为前缀码,新问题2：随意的不等长编码可能导致编码翻译时出现歧义,000表示A001表示B 01表示C 1表示D,我们设计的第一种编码,是前缀码,新问题3：如何设计前缀码,34,知识点4：哈夫曼树与哈夫曼编码,树的路径长度：树的根结点到树中每一个结点的路径长度之和。结点的带权的路径长度：该结点到

11、根结点之间的路程长度与该结点上权的乘积,路径：若树中存在一个序列k1，k2kn，使得ki是ki+1的双亲，则称该结点序列为k1到kn的一条路径。路径长度：这些节点经过的边的条数,35,知识点4：哈夫曼树与哈夫曼编码,树的路径长度：树的根结点到树中每一个结点的路径长度之和。结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积,树的路径长度：1+1+2+2+3+3结点a的带权路径长度：7*3,36,树的带权路径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(Weighted Path Length)。,树的带权路径长度：4*2+7*3+5*3+2*1,37,树的带权路

12、径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(Weighted Path Length)。由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树。,WPL=4*2+7*3+5*3+2*1=46,38,WPL=7*2+5*2+2*2+4*2=36,WPL=7*1+5*2+2*3+4*3=35,WPL=7*1+4*3+2*3+5*2=35,39,1、根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令其权值为wj;2、在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点

13、权值之和;3、从森林中删除这两棵树，同时将新得到的二叉树加入森林中;4、重复上述两步，直到森林中只含一棵树为止，这棵树即哈夫曼树。,哈夫曼树的构造方法,40,9,例如:已知权值 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树,5,6,2,7,第一步：把每个权值看作只有一个结点的树,41,9,例如:已知权值 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树,5,2,6,7,第二步：取权值最小的两棵树，合并成，新树的权值为两棵子树权值之和,7,42,9,例如:已知权值 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树,5,2,6,7,第三步：从森林中去掉被合并的结点，并将新合并的树加入到森

14、林中，继续执行第二步，直到森林合并成为一棵树,7,43,9,例如:已知权值 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树,5,2,6,7,7,13,第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树,44,9,例如:已知权值 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树,5,2,6,7,7,13,16,第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树,45,9,例如:已知权值 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树,5,2,6,7,7,13,16,第三步：从森林中去掉被

15、合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树,46,9,例如:已知权值 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树,5,2,6,7,7,13,16,29,第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树,构造完成,47,设计电文编码时，随意的不等长编码可能导致编码翻译时出现歧义使用前缀码，可解决不等长编码出现的歧义利用哈夫曼树可构造前缀码,构造方法：1，将字符集中的每个字符作为节点2，每个字符的出现频率作为节点的权值3，构造哈夫曼树4，令哈夫曼树中的左分支为0，右分支为1 从根到叶子节点的01序列即为

16、叶子节点的编码,48,假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：,A 5%B 10%C 15%D 70%,0.05,0.1,0.15,0.7,49,假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：,A 5%B 10%C 15%D 70%,0.05,0.1,0.15,0.7,0.15,50,假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：,A 5%B 10%C 15%D 70%,0.05,0.1,0.15,0.7,0.15,0.3,51,假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：,A 5%B 10%C 15%D 70%,0.05,0.1

17、,0.15,0.7,0.15,0.3,1,A,B,C,D,0,1,0,1,0,1,A的编码：000B的编码：001C的编码：01D的编码：1,电文：D A B C编码：1 000 001 01,每个字符的编码都不是另一字符编码的前缀,52,项目完成，总结：,1，树的概念2，专业术语的定义3，二叉树的概念4，哈夫曼树和哈夫曼编码,下节内容：1，二叉树的性质2，二叉树基本操作3，二叉树的应用,作业：P99 6.21,53,n(n0)个结点的树的高度:最低是多少？最高是多少？,答案：1，n,练习,54,答案：,一棵树应满足下列条件：（1）有且仅有一个结点没有前驱（双亲）,称该结点为树根;（2）除根结

18、点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。,判断,55,1、哈夫曼树只有度为0和2的结点，无度为1的结点；2、n个叶子的哈夫曼树的形态一般不唯一，但WPL是相同的；3、n个叶子的哈夫曼树共有2n-1个结点。,判断,答案：正确,56,0.1,0.2,0.3,0,1,练习：假设有字符集A，B，C，D其在电文中的使用频率分别为0.1，0.4，0.3，0.2请给出该字符集中每个字符的哈夫曼编码并将AABCDD电文翻译为哈夫曼编码,0.3,0.6,0,1,0.4,1,0,1,A,D,C,B,编码：A 100B 0C 11D 101,AABBCDD翻译：,

19、57,2009年10月考题：,58,4.2 二叉树,二叉树(Binary Tree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树同样也都是二叉树,59,特征：每个结点最多只有两棵子树子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清是左、右子树。,A,C,B,A,B,C,60,二叉树的五种形态,61,（1）初始化 INITIATE(BT)（2）求根 ROOT(BT)（3）求双亲 PARENT(BT,x)（4）求左孩子、右孩子Child(BT,x),RChild(BT,x)（5）建树 CREAT(x,LBT,RBT)（6）剪枝 D

20、ELLEFT(BT,x)和DELRIGHT(BT,x),二叉树的基本运算,62,1.一个非空二叉树的第i层上至多有2i-1个结点（i1）证明：i=1,只有根结点，显然成立 设i=k时成立，最多有2k-1个结点 当i=k+1时，最多的结点个数：2k-1*2=2k-1+1=2k=2(k+1)-1,二叉树的性质,63,2.深度为k的二叉树至多有2k-1个结点(k1),证明：二叉树的结点个数为：1+2+2k-1=2k-1,64,3.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。,证明：设n1为T中度为1的结点数，则总结点数：n=n0+n1+n2(1)另：根据各个结

21、点的前驱和后继情况分支条数=n-1分支条数=n1+2*n2(2)由(1)和(2)有：n1+2*n2=n0+n1+n2-1故 n0=n2+1;,65,考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上到下，从左到右。,满二叉树,深度为k且有2k-1个结点的二叉树,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,66,完全二叉树,深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1到n的结点一一对应时，称为完全二叉树。,a,b,c,d,e,f,g,h,i,j,67,1.满二叉树一定是一棵完全二叉树，反之完全二

22、叉树不一定是一棵满二叉树。()2.满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。(),判断题,68,4.具有n个结点的完全二叉树的深度:k=log2(n)+1,证明：假设n个结点的完全二叉树的深度为k，则n的值应大于深度为k-1的满二叉树的结点数2k-1-1，小于等于深度为k的满二叉树的结点数2k-1，即 2k-1-1n2k-1 进一步可推导出 2k-1 n2k两边取对数后，有 k-1 log2(n)k进一步可推导出 log2(n)k log2(n)+1因为k是整数，所以有k log2(n)+1,69,（a）如果i=1,此结点为根结点，无双亲；若i1,则其双亲结点

23、是i/2。（b）如果2in,则结点i无左孩子，i为叶子结点,否则其左孩子是结点2i。（c）如果2i+1n，则结点i无右孩子，否则其右孩子是结点2i+1。,5.如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,3,n,则对任一结点i（1in）有,a,b,c,d,e,f,g,h,i,j,70,1.一棵树高为K的完全二叉树至少有（）个结点A.2k 1 B.2k-1 1 C.2k-1 D.2k,习题,答案：C,71,2.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。,习题,结点总个数 n=2+3+4+x前驱后继 n-1=2*

24、1+3*2+4*3故 x=12 答案：12,72,习题,3.有关二叉树下列说法正确的是（）A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2,答案：B,73,4.3 二叉树的存储结构,顺序存储结构链式存储结构,74,二叉树的顺序存储结构,整个二叉树可以按照从上到下，从左到右的顺序编号；,a,b,c,d,e,f,g,h,i,j,75,1顺序存贮结构,将一棵二叉树按完全二叉树顺序存放到一维数组中,8,9,10,11,12,13,14,15,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,a b c d e f

25、 g h m,76,顺序存储结构举例,A B C,77,对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便;若为非完全二叉树,将会浪费大量存贮单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。,78,2.链式存储结构,二叉链表三叉链表,79,二叉树的链式存储结构,二叉链表,80,A,D,E,B,C,F,root,81,二叉链表的定义,struct btnode/结点结构 datatype data;struct btnode*lchild,*rchild;typedef struct btnode*bitreptr；bitreptr*root;,结点结构:,82,问题：如何找

26、到某结点的子树？如何找到某结点的双亲？,83,三叉链表,A,D,E,B,C,F,root,84,三叉链表的定义,struct btnode/结点结构 datatype data;struct btnode*lchild,*rchildtypedef struct btnode*bitreptr；bitreptr*root;,结点结构:,*parent;,;,85,链式存储的缺点；若一棵二叉树有n个结点,采用二叉链表作存贮结构时,共有2n个指针域,其中只有n-1个指针指向左右孩子,其余n+1个指针为空,没有发挥作用。,86,4.4 二叉树的遍历,遍历一棵二叉树是按某种次序系统地“访问”二叉树上的

27、所有结点，使每个结点恰好被“访问”一次。,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,“访问”的含义可以很广，如：输出结点的信息等,87,若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。,先（根）序的遍历算法：,88,若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。,中（根）序的遍历算法：,89,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,后（根）序的遍历算法：,90,先（根）序的遍历算法：,void Preorder(bitre

28、ptr r)/先序遍历二叉树 if(r！=NULL)visit(r);Preorder(r-lchild);Preorder(r-rchild);,91,中（根）序的遍历算法：,void Inorder(bitreptr r)/中序遍历二叉树 if(r！=NULL)Inorder(r-lchild);visit(r);Inorder(r-rchild);,92,后（根）序的遍历算法：,void Postorder(bitreptr r)/后序遍历二叉树 if(r！=NULL)Postorder(r-lchild);Postorder(r-rchild);visit(r);,93,二叉树的遍历算

29、法：,LDR、LRD、DLR,94,遍历举例,前序序列：abcdef中序序列：cbefda后序序列：cfedba,95,习题,1.给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是,LRN B.NRL C.RLN D.RNL,答案：D,96,习题,2.假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，请确定一棵二叉树,A B D G H C E F I,G D H B A E C I F,前序,中序,97,习题,8.试找出满足下列条件的二叉树1）先序序列与中序序列相同 2）中序序列与

30、后序序列相同3）先序序列与后序序列相同,答案1）不含左子树的二叉树2）不含右子树的二叉树3）空二叉树或只含根结点的二叉树,98,习题,4.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是()的二叉树 A空或只有一个结点 B.高度等于其结点数C任一结点无左孩子 D.任一结点无右孩子,先序：根左右后序：左右根答案：B,99,4.6 树和林,考虑存储结构时，主要考虑逻辑结构：数据元素数据元素之间的关系,100,树的存储结构,双亲表示法,孩子链表表示法,孩子兄弟链表表示法,101,孩子链表表示法,顺序存储结点+链式存储孩子结构；找孩子容易，找双亲难；,102,孩子兄弟链表表示法,两个指针：左孩子

31、指针，右孩子指针,103,双亲表示法,树的双亲表示法主要描述的是结点的双亲关系,顺序表示，存放顶点和双亲信息,104,请画出该树的孩子链表结构图,请画出该树的孩子兄弟链表结构图,双亲表示法结构图,105,树的遍历,前序遍历树若树非空，则：（1）访问树的根结点；（2）依次前序遍历树的第一棵子树、第二棵子树，,106,树的遍历,后序遍历树若树非空，则：（1）依次后序遍历树的第一棵子树、第二棵子树，（2）访问树的根结点；,107,树的遍历,层次遍历树1）访问树的根结点；2）依次前序遍历树的第一层结点、第二结点，,108,前序遍历序列：后序遍历序列：层次遍历序列：,ABCDE,BCEDA,ABCDE,

32、109,森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟,树、森林与二叉树的关系,树与二叉树的相互转换森林与二叉树的相互转换,110,1.树与二叉树的相互转换,树转换成的二叉树其右子树一定为空,111,2.森林与二叉树的相互转换,112,森林转换为二叉树,113,森林转换为二叉树,114,习题 将二叉树转换成树,115,D,E,F,G,H,I,J,L,K,F,C,习题 二叉树到森林的转换,116,习题,设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是()。A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右边兄弟C.在树T中，

33、X一定是叶子结点 D.在树T中，X一定有左边兄弟,答案：D,117,4.7 判定树和哈夫曼树,分类与判定树哈夫曼树与哈夫曼算法,118,分类与判定树,问题：编写程序实现将百分制成绩转换为五级制成绩,假设成绩已存入score变量中，转换后等级存入grade变量,if(score60)grade=“bad”;else if(score70)grade=“pass”;else if(score80)grade=“general”;else if(score90)grade=“good”;else if(score=100)grade=“excellent”;else grade=“error”；,1

34、19,程序已写出，但是此种判定形式是否最好呢？从何角度考虑程序是否最优？,问题：编写程序实现将百分制成绩转换为五级制成绩,if(score60)grade=“bad”;else if(score70)grade=“pass”;else if(score80)grade=“general”;else if(score90)grade=“good”;else if(score=100)grade=“excellent”;else grade=“error”；,120,问题：编写程序实现将百分制成绩转换为五级制成绩,if(score60)grade=“bad”;else if(score70)gra

35、de=“pass”;else if(score80)grade=“general”;else if(score90)grade=“good”;else if(score=100)grade=“excellent”;else grade=“error”；,现实中成绩在五个等级上的分布是不均匀的！假设分布规律如下：,121,假设成绩在五个等级上的分布规律如下：,if(score60)grade=“bad”;else if(score70)grade=“pass”;else if(score80)grade=“general”;else if(score90)grade=“good”;else if

36、(score=100)grade=“excellent”;else grade=“error”；,哪个判断执行次数较多？判定语句什么顺序最好？,122,假设成绩在五个等级上的分布规律如下：,0.30,0.05,0.40,0.10,0.15,0.30,0.60,1,0.15,先判断是否70-79之间再判断是否80-89后判断是否60-69再判断,123,假设成绩在五个等级上的分布规律如下：,良,不及格,中,优,及格,60-69,80-89,70-79,60,Y,N,N,Y,N,Y,Y,N,如何构造出最佳的判定树？,124,概 念,树的路径长度：树的根结点到树中每一个结点的路径长度的和。结点的带权

37、的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积树的带权的路径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(Weighted Path Length)。由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树。,125,有4个结点，权值分别为7，5，2，4，构造有4个叶子结点二叉树,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,126,由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树

38、。,哈夫曼树 的形态是不唯一,127,根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令其权值为wj;在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和;在森林中删除这两棵树，同时将新得到的二叉树加入森林中;重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。,构造Huffman树步骤,128,9,例如:已知权值 W=5,6,2,9,7,5,6,2,7,129,9,5,7,2,6,7,例如:已知权值 W=5,6,2,9,7,130,9,5,7,2,6,7,13,例如:已知权值 W=5,6,2,9,7,131,9,5,

39、7,2,6,7,13,16,例如:已知权值 W=5,6,2,9,7,132,9,5,7,2,6,7,13,16,29,例如:已知权值 W=5,6,2,9,7,133,9,5,7,2,6,29,7,13,16,根据权值构造得到哈夫曼树构造哈夫曼树的目的是什么呢？,例如:已知权值 W=5,6,2,9,7,134,假设成绩在五个等级上的分布规律如下：,0.30,0.05,0.40,0.10,0.15,0.30,0.60,1,0.15,先判断是否70-79之间再判断是否80-89后判断是否60-69再判断,135,在计算机及通信中，常用二进制编码来表示字符例如用00、01、10、11分别表示字母A、B

40、、C、D若A、B、C、D出现的频率是一样的，传输100个字母用200个二进制位。,前缀码,三、哈夫曼树的应用,136,A出现的频率为50 B出现的频率为25C出现的频率为20 D出现的频率为5用不等长的二进制序列表示字母A、B、C、D使传输的信息的二进制位尽可能少000表示D 用001表示C 01表示B 1表示A传输100个字母所用的二进制位为 35+320+225+150=175000011001表示什么？,2，前缀码,三、哈夫曼树的应用,DBAC,137,但当我们用000表示D 001表示C 00表示B 1表示A000011001表示什么？,BBAAC,BCAC,设计不等长编码时，必须做到

41、：任何一个字符的编码不能是另一个字符编码的前缀，这种编码为前缀码,000表示D 001表示C 01表示B 1表示A000011001表示DBAC,138,利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即：使得所传电文的总长度最短。,哈夫曼编码,139,1，要求必须是前缀码 利用二叉树可以构造前缀码,为什么选取哈夫曼编码构造方法,A,D,C,B,0,1,0,1,1,0,000表示D 001表示C 01表示B 1表示A如此编码符合前缀码规则,140,2，要求电文总长最短 假设每个字符在电文中出现的频率为wi 其编码长度为li 电文总长：wi*li 将wi作

42、为每个叶子节点的权值则 wi*li 是带权路径长度，符合哈夫曼树定义,为什么选取哈夫曼编码构造方法,141,1，将字符集中的每个字符作为节点2，每个字符的出现频率作为节点的权值3，构造哈夫曼树4，令哈夫曼树中的左分支为0，右分支为1 从根到叶子节点的01序列 即为叶子节点的编码,哈夫曼编码构造方法,142,0.1,0.2,0.3,0,1,例题：假设有字符集A，B，C，D其在电文中的使用频率分别为0.1，0.4，0.3，0.2请给出该字符集中每个字符的哈夫曼编码并将AABCDD电文翻译为哈夫曼编码,0.3,0.6,0,1,0.4,1,0,1,A,D,C,B,编码：A 100B 0C 11D 10

43、1,AABBCDD翻译：,143,哈夫曼树的性质,1、哈夫曼树只有度为0和2的结点，无度为1的结点；2、权值大的结点离根结点近；3、n个叶子的哈夫曼树的形态一般不唯一，但WPL是相同的；4、n个叶子的哈夫曼树共有2n-1个结点。,144,已知一棵二叉树的中根序列和后根序列分别是BDCEAFHG和DECBHGFA，试画出这棵二叉树,习题：,145,中序遍历：B D C E A F H G后序遍历：D E C B H G F A,146,147,148,实验：将百分制转为五级记分制（要求其算法时间性能尽可能高）,if a60 b=E else if a70 b=D else if a80 b=C else if a90 b=B else b=A;,149,最优二叉树（huffman树）,