数据结构讲义6.ppt

6.1 树的定义和基本术语 6.2 二叉树 6.2 二叉树 6.2 二叉树 6.2 二叉树 6.2 二叉树 6.2 二叉树 6.4 树和森林 6.4 树和森林 6.4 树和森林 6.4 树和森林 6.4 树和森林 6.4 树和森林 6.6 赫夫曼树及其应用 6.6 赫夫曼树及其应用 6.6 赫夫曼树及其应用 B C D F G H I J E B C D F G H I J E A B C D F G H I J E A 2 森林转换成相对应的二叉树： 增加一个虚拟的根结点，它的子结点为各棵树的根。 那么，就变成了树转换成二叉树的问题。 N B C D F G H I J E A T1 T2 …… T3 L R 先根：A B E F C G D H J I 后根：E F B G C J H I D A 6.4.3 树、森林的遍历 1 树的先根、后根遍历： 1）先根：类似于二叉树的先序遍历（NLR） N:根；L：第一棵子树，R：其余的子树，遍历方向由第二棵子树至最后一棵子树。 2）后根：类似于二叉树的中序遍历（LRN） L：第一棵子树，R：其余的子树，遍历方向由第二棵子树至最后一棵子树， N:根。 先序：B E F C G D H J I 后序：E F B G C J H I D B C D F G H I J E A B C D F G H I J E 2 森林的先序、后序遍历： 1）先序遍历类似于树的先序遍历。增加一个虚拟的根结点，它的子结点为各棵树的根。对这棵树进行先根遍历，即得到森林的先序序列（去掉树根结点）。 2）后序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的子结点为各棵树的根。对这棵树进行后根遍历，即得到森林的后序序列（去掉树根结点）。 路径长度：结点之间的树枝的总数 树的路径长度：从根到每一结点的路径长度之和 树的带权路径长度(WPL)： 叶子结点的带权路径长度之和 最优二叉树或赫夫曼树：树的带权路径长度 WPL 最小的二叉树 E G H L L E H G E G H L 7 7 7 5 2 4 4 4 2 2 5 5 WPL=36 WPL=46 WPL=35 6.6.1 最优二叉树（赫夫曼树） 分数 等级 比例 0~59 60~69 70~79 80~89 90~100 E D C B A 0.05 0.15 0.40 0.30 0.10 a60 a70 a80 a90 E D C B A Y N N N N Y Y Y 70≤ a80 C B E A D Y N Y Y N 80≤ a90 60≤ a70 a60 a80 a70 a90 a60 E D C A B N N N N N N Y Y Y Y 判定树： 6.6 赫夫曼树及其应用 WPL=3.15 WPL=2.05 WPL=2.2 (1) 由给定的n个权值{w0, w1, w2, …, wn-1}，构造具有n棵二叉树 的集合F = {T0, T1, T2, …, Tn-1}，其中每一棵二叉树Ti只有 一个带有权值wi的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到F中仅剩下一棵树为止： ① 在F中选取两棵根结点的权值最小的二叉树, 做为左、右 子树构造一棵新的二叉树。置新的二叉树的根结点的权值为 其左、右子树上根结点的权值之和。 ② 在F中删去这两棵二叉树。 ③ 把新的二叉树加入F。 6.6 赫夫曼树及其应用 赫夫曼算法： 赫夫曼树的构造过程 赫夫曼编码主要用途是实现数据压缩。设给出一段报文： CAST CAST SAT AT A TASA，字符集合是{C,A,S,T}，各个字符出现的频度(次数)是W={2,7,4,5}。若给每个字符以等长编码 A: 00 T: 10 C: 01 S: 11， 则总编码长度为(2+7+4+5)*2=36。若按各个字符出现的频度不同而给予不等长编码，可望减少总编码长度。 6.3.2 赫夫曼编码 以各字符出现的频度为权值建立赫夫曼树。左分支赋0，右分支赋1，得赫夫曼编码 A:0 T:10 C:110 S:111，总编码长度：7*1+5*2+(2+4)*3=35，比等长编码的总编码长度要短。 采用赫夫曼编码时，总编码长度正好等于赫夫曼树的带权路径长度WPL。 赫夫曼编码是一种无前缀编码。解码时不会混淆。 6 A, 7 S,