Download presentation
Presentation is loading. Please wait.
1
数据结构与算法 Data Structure Algorithms
烟台南山学院信息科技学院 数据结构与算法教学组
2
6.4 树和森林 1. 树和森林与二叉树的转换 2. 树和森林的存储方式 3. 树和森林的遍历
3
1. 树和森林与二叉树的转换 讨论1:树如何转为二叉树? 转换步骤: 加线 抹线 旋转 step1: 将树中同一结点的兄弟相连;
1. 树和森林与二叉树的转换 讨论1:树如何转为二叉树? 转换步骤: step1: 将树中同一结点的兄弟相连; step2: 保留结点的最左孩子连线,删除其它孩子连线; step3: 将同一孩子的连线绕左孩子旋转45度角。 加线 抹线 旋转
4
树转二叉树举例: 方法:加线—抹线—旋转 根结点肯定没有右孩子! 兄弟相连 长兄为父 孩子靠左 a b e i d f h g c a b
5
讨论2:二叉树怎样还原为树? 要点:把所有右孩子变为兄弟! a b e i d f h g c a b e i d f h g c
6
即F={T1, T2, …,Tm} B={root, LB, RB}
讨论3:森林如何转为二叉树? 即F={T1, T2, …,Tm} B={root, LB, RB} 法一: ① 各森林先各自转为二叉树; ② 依次连到前一个二叉树的右子树上。 法二:森林直接变兄弟,再转为二叉树 (参见教材P138图6.17,两种方法都有转换示意图)
7
森林转二叉树举例:(法二) A 兄弟相连 长兄为父 孩子靠左 头根为根 A B C D E F G H J I A B C D E F G
8
即B={root, LB, RB} F={T1, T2, …,Tm}
讨论4:二叉树如何还原为森林? 即B={root, LB, RB} F={T1, T2, …,Tm} 要点:把最右边的子树变为森林,其余右子树变为兄弟 G H J I A B C D E F G H J I A B C D E F A B C D E F G H J I
9
2. 树和森林的存储方式 树有三种常用存储方式: ①双亲表示法 ②孩子表示法 ③孩子兄弟表示法 1、用双亲表示法来存储
①双亲表示法 ②孩子表示法 ③孩子兄弟表示法 1、用双亲表示法来存储 思路:用一组连续空间来存储树的结点,同时在每个结点中附设一个指示器,指示其双亲结点在链表中的位置。 data parents 1 树结构 2 3 n parents data 结点结构
10
例1: 双亲表示法 1 2 3 4 5 6 7 8 A B C D E F G H I 1 2 3 -1 A B C G E I D H F
例1: 双亲表示法 1 2 3 4 5 6 7 8 A B C D E F G H I 1 2 3 -1 A B C G E I D H F 1 缺点:求结点的孩子时需要遍历整个结构。
11
思路:将每个结点的孩子排列起来,形成一个带表头(装父结点)的线性表(n个结点要设立n个链表);
2、用孩子表示法来存储 思路:将每个结点的孩子排列起来,形成一个带表头(装父结点)的线性表(n个结点要设立n个链表); 再将n个表头用数组存放起来,这样就形成一个混合结构。 例如: 1 2 3 4 5 6 7 8 g f e d c b a h b c a b e c d f h g d e f g h
12
思路:用二叉链表来表示树,但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子; 右指针指向该结点的下一个兄弟结点。
3、用孩子兄弟表示法来存储 思路:用二叉链表来表示树,但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子; 右指针指向该结点的下一个兄弟结点。 nextsibling data firstchild 指向右兄弟 指向左孩子
13
问:树转二叉树的“连线—抹线—旋转” 如何由计算机自动实现? 答:用“左孩子右兄弟”表示法来存储即可。 存储的过程就是转换的过程!
例如: a b e c d f h g a b c d e f g h 问:树转二叉树的“连线—抹线—旋转” 如何由计算机自动实现? 答:用“左孩子右兄弟”表示法来存储即可。 存储的过程就是转换的过程!
14
先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历 中序遍历森林中第一棵树的根结点的子树森林; 访问第一棵树的根结点;
森林的遍历 A B C D E F G H J I 先序遍历 若森林为空,返回; 访问森林中第一棵树的根结点; 先序遍历第一棵树中根结点的子树森林; 先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历 中序遍历森林中第一棵树的根结点的子树森林; 访问第一棵树的根结点; 中序遍历除去第一棵树之后剩余的树构成的森林。
15
6.5 Huffman树及其应用 一、最优二叉树(霍夫曼树) d e b a c f g 预备知识:若干术语 路 径: 路径长度:
路 径: 路径长度: 树的路径长度: 带权路径长度: 树的带权路径长度: 霍 夫 曼 树: 由一结点到另一结点间的分支所构成 路径上的分支数目 a→e的路径长度= 2 从树根到每一结点的路径长度之和。 树长度= 10 结点到根的路径长度与结点上权的乘积 树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。
16
Huffman树简介: WPL = wklk 树的带权路径长度如何计算? 哈夫曼树则是:WPL 最小的树。 经典之例: WPL=36
Weighted Path Length Huffman树简介: WPL = wklk k=1 n 树的带权路径长度如何计算? 哈夫曼树则是:WPL 最小的树。 经典之例: Huffman树 c d a b 2 4 5 7 (b) b d a c 7 5 2 4 (c) a b d c 7 5 2 4 (a) WPL=36 WPL=46 WPL= 35
17
先举例! 构造霍夫曼树的基本思想: 权值大的结点用短路径,权值小的结点用长路径。 构造Huffman树的步骤(即Huffman算法):
(1) 由给定的 n 个权值{w0, w1, w2, …, wn-1},构造具有 n 棵扩充二叉树的森林F = { T0, T1, T2, …, Tn-1 },其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点,其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止: ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。 先举例!
18
例1:设有4个字符d,i,a,n,出现的频度分别为7,5,2, 4,怎样编码才能使它们组成的报文在网络中传得最快?
法1:等长编码。例如用二进制编码来实现。 取 d=00,i=01,a=10,n=11 法2:不等长编码,例如用哈夫曼编码来实现。 取 d=0; i=10, a=110, n=111 最快的编码是哪个? 是非等长的Huffman码! 怎样实现Huffman编码? 先要构造Huffman树!
19
操作要点1:对权值的合并、删除与替换 构造Huffman树的步骤: ——在权值集合{7,5,2,4}中,总是合并当前值最小的两个权
注:方框表示外结点(叶子,字符对应的权值), 圆框表示内结点(合并后的权值)。
20
操作要点2:按左0右1对Huffman树的所有分支编号!
——将 Huffman树 与 Huffman编码 挂钩 1 d a i n Huffman编码结果:d=0, i=10, a=110, n=111 WPL=1bit×7+2bit×5+3bit(2+4)=35 特点:每一码都不是另一码的前缀,绝不会错译! 称为前缀码
21
霍夫曼编码的基本思想是:概率大的字符用短码,概率小的用长码。由于霍夫曼树的WPL最小,说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。
例2(严题集6.26③):假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成,它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10},试为这8个字母设计哈夫曼编码。如果用0~7的二进制编码方案又如何? 解:先将概率放大100倍,以方便构造哈夫曼树。 权值集合 w={7, 19, 2, 6, 32, 3, 21, 10}, 按哈夫曼树构造规则(合并、删除、替换),可得到哈夫曼树。
22
为清晰起见,重新排序为: w={2, 3, 6, 7, 10, 19, 21, 32} × w1={5, 6, 7, 10, 19, 21, 32} × 100 w2={7, 10, 11, 19, 21, 32} × w3={11, 17, 19, 21, 32} × 21 19 40 32 60 w4={19, 21, 28, 32} × 28 w5={28,32,40} × b c a d e g f h w6={40,60} × 17 11 10 7 w7={100} 6 2 3 5 哈夫曼树
23
对应的哈夫曼编码(左0右1): 2 3 5 6 11 10 7 32 17 28 21 19 40 60 b c a d e g f h 1
100 b c a d e g f h 1 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 1100 00 11110 1110 10 11111 01 1101 000 001 010 011 100 101 110 111 Huffman码的WPL=2( ) + 4( ) +5( ) = =2.61 WPL=3( )=3 二进制码
24
另一种结果表示:
25
例3(实验二方案3):设字符集为26个英文字母,其出现频度如下表所示。
要求编程实现: 先建哈夫曼树,再利用此树对报文“This program is my favorite”进行编码和译码。 注:若圆满实现了此方案,平时成绩将以满分计。 51 48 1 15 63 57 20 32 5 频度 z y x w v u t 字符 16 18 8 23 80 p 21 f q g r 47 h s o n m l k j 103 22 13 64 186 i e d c b a 空格
26
提示1:霍夫曼树中各结点的结构可以定义为如下5个分量:
char weight parent lchild Rchild 提示2:霍夫曼树的存储结构可采用顺序存储结构: 将整个霍夫曼树的结点存储在一个数组中:HT[1..n]; 将结点的编码存储在HC[1..n]中。 提示3:霍夫曼树如何构造?构造好之后又如何求得各结点对应的霍夫曼编码?——算法参见教材P147。 参考资料 实验二补充材料中的方案二程序; 喻信星空FTP网站上的“数据结构”演示程序
27
二叉树小结 1、定义和性质 树 2、存储结构 森林 3、遍历 4、线索化:线索树 霍夫曼树 霍夫曼编码 顺序结构 链式结构 先序遍历
二叉链表 三叉链表 中序遍历 后序遍历 先序遍历 3、遍历 霍夫曼树 先序线索树 中序线索树 后序线索树 4、线索化:线索树 霍夫曼编码
28
附:中序遍历迭代算法(利用堆栈) 时间复杂度O(n) void iter_inorder(tree_pointer node) {
int top= -1; /* initialize stack */ tree_pointer stack[MAX_STACK_SIZE]; for (;;) { for (; node; node=node->left_child) add(&top, node);/* add to stack */ node= delete(&top); /* delete from stack */ if (!node) break; /* empty stack */ printf(“%D”, node->data); node = node->right_child; } 时间复杂度O(n)
29
附:层序遍历算法(利用队列) void level_order(tree_pointer ptr)
/* level order tree traversal */ { int front = rear = 0; tree_pointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; /* empty queue */ addq(front, &rear, ptr); for (;;) { ptr = deleteq(&front, rear); + * E * D / C A B
Similar presentations