第六章 树和二叉树4.21.ppt

* 最优二叉树(又称赫夫曼树) 已知有n个权值{w1,w2,...,wn} 构造一棵有n个叶结点的二叉树，每个叶结点的权值为wi 其中WPL最小的那一棵称作最优二叉树，即赫夫曼树 最优又能怎样？ 7.赫夫曼树及其应用 * 例：一个判断成绩等级的程序 if(a 60) b = 不及格 else if(a 70) b = 及格 else if(a 80) b = 中等 else if(a 90) b = 良好 else b = 优秀 一个a最多要经过4次比较才能得出b 我们当然希望比较的总次数最小 7.赫夫曼树及其应用 * 假设有如下统计数据 原判定树为： 分数 0-59 60-69 70-79 80-89 90-100 概率 0.05 0.15 0.40 0.30 0.10 若一共有10000个输入数据 则总共的比较次数 = 500*1 + 1500*2 + 4000*3 + 3000*4 + 1000*4 = 31500 * 构造一棵赫夫曼树 有5个叶结点，权值分别为： 0.05(不及格), 0.15(及格), 0.4(中等),0.3(良好), 0.1(优秀) 判断成绩等级的程序图示如下： * 根据这棵赫夫曼树导出新的判定树： 总的比较次数 = 500*3 + 1500*3 + 4000*2 + 3000*2 + 1000*2 = 22000 31500 * 构造赫夫曼树 (1)根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树只含一个带权的根结点，其左右子树均空； 赫夫曼算法： d 7 a 1 c 5 b 3 F * 构造赫夫曼树 (2)在F中选两棵根结点的权值最小的二叉树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和； 赫夫曼算法： d 7 a 1 c 5 b 3 F a b 1 3 4 * 构造赫夫曼树 (3)在F中删除这两棵二叉树，同时将新得到的二叉树加入F； 赫夫曼算法： d 7 a 1 c 5 b 3 F a b 1 3 4 * 构造赫夫曼树 (4)重复(2)和(3)，直到F只含一棵二叉树，此即最优二叉树。 赫夫曼算法： d 7 c 5 F a b 1 3 4 a b 1 3 4 c 5 9 a b 1 3 4 c 9 5 d 16 7 F * 7.赫夫曼树及其应用 理解 为什么赫夫曼树的带权路径长度最小？ 它把权值小的结点放在底层 权值大的结点放在上层 练习： 给定权值7,6,3,32,5,26,12,9，构造相应的哈夫曼树，并计算其带权路径长度。为使结果答案尽可能唯一，请用左结点的值小于等于右结点的值来构造哈夫曼树。 * * * * * * * * * * * * * * * * * * 树的存储结构：孩子表示法 孩子表示法 每个结点可以有多个孩子 方法三：用一个静态数组，存放所有的结点 数组的每个数据元素，包括两部分：数据元素，指针；指针指向一个链表，链表结点的数据域是一个整数，表示该结点的孩子在数组中的下标； 特点： 顺序+链式存储结构； 找孩子容易，找双亲难； * 树的存储结构：孩子表示法 b d a e f c num 6 a 0 MAX-1 nodes 2 c 3 d 4 e 5 f 1 b ^ ^ ^ ^ 【例】 3 4 ^ 5 1 2 ^ * b d a e f c num 6 a 0 MAX-1 nodes 2 c 3 d 4 e 5 f 1 b ^ ^ ^ ^ -1 0 1 1 0 1 3 4 ^ 5 1 2 ^ 【例】 增加双亲信息(孩子-双亲表示法) * 双亲表示法 树中一个结点的孩子的数量不定 但双亲只有一个，所以保存每个结点的双亲 0 b d a e f c num 6 -1 0 1 1 1 a 0 MAX-1 nodes 2 c 3 d 4 e 5 f 1 b 【例】 优点 查找双亲、树根操作很快 缺点 查找孩子操作慢，需遍历整个结构 树的存储结构：双亲表示法 * 从向下的纵向和向右的横向描述树； 定义结点结构：数据元素和两个指针。一个指向该结点的第一个孩子，另一个指向该结点的下一个兄弟； firstchild data nextsibling 第一个儿子 下一个兄弟 又称二叉树表示法 树的存储结构：孩子兄弟表示法 * 即左孩子、右兄弟表示法 用二叉树来表示树 左指针指向其大儿子 右指针指向其兄弟 树的存储结构：孩子兄弟表示法 * 树、森林和二叉树的转换 转换步骤： step1: 将树中同一结点的兄弟相连； step2: 保留结点的最左孩子连线，删除其它孩子连线； step3: