Applications: Haffman Tree 叶结点权值集合为 W={1,3,5,7} 的哈夫曼树的构造过程可以计算出其带权路径长度为 29, 由此可见, 对于同一组给定叶结点所构造的哈夫曼树, 树的形状可能不同, 但带权路径长度值是相同的, 一定是最小的第一步第二步

Size: px

Start display at page:

Download "Applications: Haffman Tree 叶结点权值集合为 W={1,3,5,7} 的哈夫曼树的构造过程可以计算出其带权路径长度为 29, 由此可见, 对于同一组给定叶结点所构造的哈夫曼树, 树的形状可能不同, 但带权路径长度值是相同的, 一定是最小的第一步第二步"

嗣通
7 years ago
Views:

1 Data Structure & Algorithm Analysis Trees & Binary Trees Zibin Zheng( 郑子彬 ) School of Data and Computer Science, SYSU 课程主页 : 1

2 Applications: Haffman Tree 叶结点权值集合为 W={1,3,5,7} 的哈夫曼树的构造过程可以计算出其带权路径长度为 29, 由此可见, 对于同一组给定叶结点所构造的哈夫曼树, 树的形状可能不同, 但带权路径长度值是相同的, 一定是最小的第一步第二步第三步第四步哈夫曼树的建立过程 Data Structure & Algorithm Analysis 2

3 Applications: Haffman Tree 哈夫曼树的存储表示在构造哈夫曼树时, 可以设置一个结构数组 HuffNode 保存哈夫曼树中各结点的信息, 根据二叉树的性质可知, 具有 n 个叶结点的哈夫曼树共有 2n-1 个结点, 所以数组 HuffNode 的大小设置为 2n-1 由哈夫曼树的构造过程, 显然的, 每次合并两棵树会多出一个节点, 而由最初的节点森林到一颗哈夫曼树, 一共要合并 (n-1) 次因而, 对于一个 n 个叶节点的哈夫曼树, 一共会拥有 n+(n-1)=2n- 1 个节点 Data Structure & Algorithm Analysis 3

4 Applications: Haffman Tree 在数据通讯中, 经常需要将传送的文字转换成由二进制字符 0,1 组成的二进制串, 称之为编码例 : 假设要传送的电文为 ABACCDA, 电文中只含有 A,B,C,D 四种字符表 6.4 字符的四种不同的编码方案字符编码字符编码字符编码字符编码 A 000 A 00 A 0 A 01 B 010 B 01 B 110 B 010 C 100 C 10 C 10 C 001 D 111 D 11 D 111 D 10 (a) (b) (c) (d) Data Structure & Algorithm Analysis 4

5 Applications: Haffman Tree 若采用表 6.4(a) 所示的编码, 则电文的代码为 , 长度为 21 在传送电文时, 我们总是希望传送时间尽可能短, 这就要求电文代码尽可能短, 显然, 这种编码方案产生的电文代码不够短若采用表 6.4(b) 所示的编码, 则电文的代码为 , 长度为 14 在这种编码方案中, 四种字符的编码均为两位, 是一种等长编码如果在编码时考虑字符出现的频率, 让出现频率高的字符采用尽可能短的编码, 出现频率低的字符采用稍长的编码, 构造一种不等长编码, 则电文的代码就可能更短若采用表 6.4(c) 所示的编码时, 上述电文的代码为 , 长度仅为 13 若采用表 6.4(d) 所示的编码时, 上述电文的代码为 , 长度仅为 17 不同的编码方式产生不同的数据存储消耗!! Data Structure & Algorithm Analysis 5

6 Applications: Haffman Tree 哈夫曼树可用于构造使电文的编码总长最短的编码方案具体做法如下 : 设需要编码的字符集合为 {d 1,d 2,,d n }, 它们在电文中出现的次数或频率集合为 {w 1,w 2,,w n }, 以 d 1,d 2,,d n 作为叶结点, w 1,w 2,,w n 作为它们的权值, 构造一棵哈夫曼树, 规定哈夫曼树中的左分支代表 0, 右分支代表 1, 则从根结点到每个叶结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码, 我们称之为哈夫曼编码 Data Structure & Algorithm Analysis 6

7 Applications: Haffman Tree 在哈夫曼编码树中, 树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和, 也就是电文的代码总长, 所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码 Data Structure & Algorithm Analysis 7

8 Applications: Haffman Tree 在建立不等长编码时, 必须使任何一个字符的编码都不是另一个字符编码的前缀, 这样才能保证译码的唯一性存在前缀编码我们称之为具有二义性的译码采用哈夫曼树进行编码, 则不会产生上述二义性问题因为, 在哈夫曼树中, 每个字符结点都是叶结点, 它们不可能在根结点到其它字符结点的路径上, 所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀, 从而保证了译码的非二义性 Data Structure & Algorithm Analysis 8

9 Applications: Haffman Tree 实现哈夫曼编码的算法可分为两大部分 : (1) 构造哈夫曼树 ; (2) 在哈夫曼树上求叶结点的编码求哈夫曼编码, 实质上就是在已建立的哈夫曼树中, 从叶结点开始, 沿结点的双亲链域回退到根结点, 每回退一步, 就走过了哈夫曼树的一个分支, 从而得到一位哈夫曼码值由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的 0,1 序列, 因此先得到的分支代码为所求编码的低位码, 后得到的分支代码为所求编码的高位码 Data Structure & Algorithm Analysis 9

10 Applications: Haffman Tree 下图是权值集合 W={8, 3, 4, 6, 5, 5} 构造 Huffman 树的过程所构造的 Huffman 树的 WPL 是 : WPL= = 第一步第二步第三步第四步第五步 Huffman 树的构造过程第六步 Data Structure & Algorithm Analysis 10

11 Applications: Haffman Tree 例 6.5 假设有一个电文字符集中有 8 个字符, 每个字符的使用频率分别为 {0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}, 现以此为例设计哈夫曼编码为方便计算, 将所有字符的频度乘以 100, 使其转换成整型数值集合, 得到 {5,29,7,8,14,23,3,11}; 哈夫曼编码设计如下图 Data Structure & Algorithm Analysis 11

12 Applications: Haffman Tree Data Structure & Algorithm Analysis 12

13 哈夫曼算法的存储结构 struct element { int weight; int lchild, rchild, parent; }; 1. 设置一个数组 hufftree[2n-1] 保存哈夫曼树中各点的信息, 数组元素的结点结构 weight lchild rchild parent 其中 :weight: 权值域, 保存该结点的权值 ; lchild: 指针域, 结点的左孩子结点在数组中的下标 ; rchild: 指针域, 结点的右孩子结点在数组中的下标 ; parent: 指针域, 该结点的双亲结点在数组中的下标 Data Structure & Algorithm Analysis 13

14 伪代码 1. 数组 hufftree 初始化, 所有元素结点的双亲左右孩子都置为 -1; 2. 数组 hufftree 的前 n 个元素的权值置给定值 w[n]; 3. 进行 n-1 次合并 3.1 在二叉树集合中选取两个权值最小的根结点, 其下标分别为 i 1, i 2 ; 3.2 将二叉树 i 1 i 2 合并为一棵新的二叉树 k; Data Structure & Algorithm Analysis 14

15 weight parent lchild rchild 初态 Data Structure & Algorithm Analysis 15

16 i weight parent lchild rchild i 2 k 过程 Data Structure & Algorithm Analysis 16

17 4 5 5 weight parent lchild rchild 2 3 i i k 过程 Data Structure & Algorithm Analysis 17

18 9 5 weight parent lchild rchild i 1 i 2 k 过程 Data Structure & Algorithm Analysis 18

19 void HuffmanTree(element hufftree[ ], int w[ ], int n ) { for (i = 0; i <2*n-1; i++) { hufftree [i].parent = -1; hufftree [i].lchild = -1; hufftree [i].rchild = -1; } for (i = 0; i < n; i++) hufftree[i].weight = w[i]; for (k = n; k < 2*n-1; k++) { Select(huffTree, i1, i2); hufftree[k].weight = hufftree[i1].weight+hufftree[i2].weight; hufftree[i1].parent = k; hufftree[i2].parent = k; hufftree[k].lchild = i1; hufftree[k].rchild = i2; } } Data Structure & Algorithm Analysis 19

20 Applications: Haffman Tree 哈夫曼编码的实现算法首先根据字符的权值构建哈夫曼树, 然后从每个叶结点开始不断的向上搜索双亲结点, 直到根点为止, 得出字符的哈夫曼编码编码的存储结构 : typedef struct // 哈夫曼编码的存储结构 { char bits[n]; // 保存编码的数组 int start; // 编码有效起始位置, 该位置之后的 01 串为字符的编码 char ch; // 字符 } CodeType ; CodeType code[n+1]; // 字符编码数组, 下标为 0 的单元空出 Data Structure & Algorithm Analysis 20

21 Applications: Haffman Tree huffmancode(hufmtree tree[],codetype code[]) /* 利用哈夫曼树求字符的哈夫曼编码 */ { int i,c,p; for(i=1;i<=n;i++) // N 次循环, 分别得到 N 个字符的编码 { code[i].start=n; c=i; p=tree[i].parent; // 获取字符的双亲 while (p!=-1) // 一直往上层查找, 直到根结束 { code[i].start--; if(tree[p].lchild==c) code[i].bits[code[i].start] ='0'; else code[i].bits[code[i].start] ='1'; c=p; p=tree[p].parent; } } } Data Structure & Algorithm Analysis 21

22 Applications: Haffman Tree Decision Problem 例 : 编制一个将百分制转换为五级分制的程序只要用条件语句便可完成 if (a<60) b= E ; else if (a<70) b= D else if (a<80) b= C else if (a<90) b= B else b= A ; 考试成绩分布表 75% 以上的数据需进行三次或三次以上的比较才能得出结果 Data Structure & Algorithm Analysis 22

23 Applications: Haffman Tree 判定树 < 不及格 0.10 <60? < 及格 0.15 <70? < 中 0.25 <80? < <90? 良优 WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4 = 3.15 Data Structure & Algorithm Analysis 23

24 Applications: Haffman Tree 最佳判定树按 Huffman 算法改造判定树 < < <60? <70? 不及格及格 < <80? < <90? 中良优 WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = = 2.25 Data Structure & Algorithm Analysis 24

25 堆 (Heap) 堆的定义及其实现最小堆完全二叉树 : 顺序表示 K i K 2i+1 && K i K 2i+2 最大堆完全二叉树 : 顺序表示 K i K 2i+1 && K i K 2i+2 Data Structure & Algorithm Analysis 25

26 堆 (Heap) 堆的性质从逻辑的角度来讲, 堆是一种树形结构, 而且是一种特殊的完全二叉树此完全二叉树的每个结点对应于序列中的一个关键码, 根结点对应于关键码 K 0, 按层次从左至右依次类推说其特殊, 主要是因为堆序只是局部有序, 即最小堆对应的完全二叉树中所有内部结点的值均不大于其左右孩子的关键码值, 而一个结点与其兄弟之间没有必然的联系最小堆不像二叉搜索树那样实现了关键码的完全排序相比较而言, 只有当结点之间是父子关系的时候, 才可以确定这两个结点关键码的大小关系 Data Structure & Algorithm Analysis 26

27 堆 (Heap) 最小堆的类定义 #define DefaultSize 10 template <class Type> class MinHeap : public MinPQ <Type> { private: Type * heap; // 存放最小堆元素的数组 int CurrentSize; // 最小堆当前元素个数 int MaxHeapSize; // 最多允许元素个数 void FilterDown ( int i, int m ); // 从 i 到 m 自顶向下进行调整成为最小堆 void FilterUp ( int i ); // 从 i 到 0 自底向上进行调整成为最小堆 public: MinHeap ( int sz ); // 建立空堆 MinHeap ( Type arr[ ], int n ); MinHeap ( const MinHeap& R ); ~MinHeap ( ) { delete [ ] heap; } int Insert ( const Type& x ); // 插入 int Remove ( Type& x ); // 删除 int IsEmpty ( ) const // 判堆空否 { return CurrentSize == 0; } int IsFull ( ) const // 判堆满否 { return CurrentSize == MaxHeapSize; } void MakeEmpty ( ) { CurrentSize = 0; } } Data Structure & Algorithm Analysis 27

28 堆 (Heap) 有序关键码序列 K = {09,17,65,23,45,78,87,53} 所对应的最小堆形成的完全二叉树形式为下图所示 : 最小堆对应的完全二叉树 Data Structure & Algorithm Analysis 28

29 堆 (Heap) 无序的关键码序列 K = {53,17,78,23,45,65,87, 09}, 如何建立最小堆? i i currentpos = i = 3 currentpos = i = 2 自下向上逐步调整为最小堆 Data Structure & Algorithm Analysis 29

30 最小堆调整算法最小堆的向下调整算法 template <class Type> void MinHeap<Type> :: FilterDown ( int start, int EndOfHeap ) { int i = start, j = 2*i+1; // j 是 i 的左子女 Type temp = heap[i]; while ( j <= EndOfHeap ) { } if ( j < EndOfHeap && heap[j] > heap[j+1] ) j++; if ( temp <= heap[j] ) break; else { } } heap[i] = temp; heap[i] = heap[j]; // 下面的上浮 i = j; j = 2*j+1; // 向下滑动 // 两子女中选小者 Data Structure & Algorithm Analysis 30

31 最小堆调整算法 i 53 i currentpos = i = 0 23 Data Structure & Algorithm Analysis 31

32 最小堆调整算法 i i Data Structure & Algorithm Analysis 32

33 最小堆的插入 template <class Type> int MinHeap<Type> :: Insert ( const Type &x ) { // 在堆中插入新元素 x } if ( CurrentSize == MaxHeapSize ) // 堆满 { cerr << " 堆已满 " << endl; return 0; } heap[currentsize] = x; FilterUp (CurrentSize); CurrentSize++; return 1; 堆的插入 // 插在表尾 // 向上调整为堆 // 堆元素增一最小堆的向上调整算法 template <class Type> void MinHeap<Type> :: FilterUp ( int start ) { // 从 start 开始, 向上直到 0, 调整堆 int j = start, i = (j-1)/2; // i 是 j 的双亲 Type temp = heap[j]; while ( j > 0 ) { if ( heap[i] <= temp ) break; else { heap[j] = heap[i]; j = i; i = (i -1)/2;} } heap[j] = temp; } Data Structure & Algorithm Analysis 33

34 最小堆的插入 09 i 09 i j j 在堆中插入新元素 11 Data Structure & Algorithm Analysis 34

35 最小堆的插入 i i j 09 j Data Structure & Algorithm Analysis 35

36 最小堆的删除 template <class Type> int MinHeap <Type> :: Remove ( Type &x ) { if (!CurrentSize ) { cout << 堆已空 " << endl; return 0; } } x = heap[0]; // 最小元素出队列 heap[0] = heap[currentsize-1]; CurrentSize--; // 用最小元素填补 FilterDown ( 0, CurrentSize-1 ); // 调整 return 1; 在最小堆中删除元素 Data Structure & Algorithm Analysis 36

37 Data Structure & Algorithm Analysis 37

38 森林的遍历先序遍历的规则若森林 F 为空, 返回 ; 否则访问 F 的第一棵树的根结点 ; 先序遍历第一棵树的子树森林 ; 先序遍历其它树组成的森林 B A C E D G K F I H J 森林的二叉树表示 ABCDE FG HIKJ Data Structure & Algorithm Analysis 38

39 森林的遍历中序遍历的规则若森林 F 为空, 返回 ; 否则中序遍历第一棵树的子树森林访问 F 的第一棵树的根结点中序遍历其它树组成的森林 Data Structure & Algorithm Analysis 39

40 森林的遍历广度优先遍历 ( 层次序遍历 ) 若森林 F 为空, 返回 ; 否则依次遍历各棵树的根结点 ; 依次遍历各棵树根结点的所有子女 ; 依次遍历这些子女结点的子女结点 Data Structure & Algorithm Analysis 40

41 树森林与二叉树的转换从树的孩子兄弟表示法可以看到, 如果设定一定规则, 就可用二叉树结构表示树和森林, 这样, 对树的操作实现就可以借助二叉树存储, 利用二叉树上的操作来实现本节将讨论树和森林与二叉树之间的转换方法 1. 树与二叉树的转换对于一棵无序树, 树中结点的各孩子的次序是无关紧要的, 而二叉树中结点的左右孩子结点是有区别的为避免发生混淆, 我们约定树中每一个结点的孩子结点按从左到右的次序顺序编号 Data Structure & Algorithm Analysis 41

42 树森林与二叉树的转换如图 6.28 所示的一棵树, 根结点 A 有 B C D 三个孩子, 可以认为结点 B 为 A 的第一个孩子结点, 结点 C 为 A 的第二个孩子结点, 结点 D 为 A 的第三个孩子结点将一棵树转换为二叉树的方法是 : (1) 树中所有相邻兄弟之间加一条连线 A B C D E F G 图 6.28 一棵树 (2) 对树中的每个结点, 只保留它与第一个孩子结点之间的连线, 删去它与其它孩子结点之间的连线 (3) 以树的根结点为轴心, 将整棵树顺时针转动一定的角度, 使之结构层次分明 Data Structure & Algorithm Analysis 42

43 树森林与二叉树的转换可以证明, 树作这样的转换所构成的二叉树是唯一的图 6.29(a) (b) (c) 给出了树转换为二叉树的转换过程示意图图 6.29 树转换为二叉树的过程示意由上面的转换可以看出, 在二叉树中, 左分支上的各结点在原来的树中是父子关系, 而右分支上的各结点在原来的树中是兄弟关系由于树的根结点没有兄弟, 所以变换后的二叉树的根结点的右孩子必为空事实上, 一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的 Data Structure & Algorithm Analysis 43

44 树森林与二叉树的转换 2. 森林转换为二叉树由森林的概念可知, 森林是若干棵树的集合, 只要将森林中各棵树的根视为兄弟, 每棵树又可以用二叉树表示, 这样, 森林也同样可以用二叉树表示森林转换为二叉树的方法如下 : (1) 将森林中的每棵树转换成相应的二叉树 (2) 第一棵二叉树不动, 从第二棵二叉树开始, 依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子, 当所有二叉树连起来后, 此时所得到的二叉树就是由森林转换得到的二叉树 Data Structure & Algorithm Analysis 44

45 树森林与二叉树的转换下图给出了森林及其转换为二叉树的过程 (a) 一个森林 (c) 所有二叉树连接后的二叉树 (b) 森林中每棵树转换为二叉树 Data Structure & Algorithm Analysis 45

46 树森林与二叉树的转换 Rotations Data Structure & Algorithm Analysis 46

47 树森林与二叉树的转换 3. 二叉树转换为树和森林树和森林都可以转换为二叉树, 二者不同的是树转换成的二叉树, 其根结点无右分支, 而森林转换后的二叉树, 其根结点有右分支显然这一转换过程是可逆的, 即可以依据二叉树的根结点有无右分支, 将一棵二叉树还原为树或森林, 具体方法如下 : (1) 若某结点是其双亲的左孩子, 则把该结点的右孩子右孩子的右孩子都与该结点的双亲结点用线连起来 ; (2) 删去原二叉树中所有的双亲结点与右孩子结点的连线 ; (3) 整理由 (1) (2) 两步所得到的树或森林, 使之结构层次分明 Data Structure & Algorithm Analysis 47

48 树森林与二叉树的转换图 6.31 给出了一棵二叉树还原为森林的过程示意 (a) 一棵二叉树 (b) 加连线 (c) 去掉与右孩子的连线 (d) 还原后的树图 6.31 二叉树还原为树的过程示意 Data Structure & Algorithm Analysis 48

49 树的应用树的应用十分广泛, 在后面介绍的查找和排序常用的两项技术中, 就有以树结构组织数据进行操作的本节仅讨论树在集合表示与运算方面的应用集合是一种常用的数据表示方法, 对集合可以作多种操作, 假设集合 S 由若干个元素组成, 可以按照某一规则把集合 S 划分成若干个互不相交的子集合, 例如, 集合 S={1,2,3,4,5,6,7,8,9,10}, 可以被分成如下三个互不相交的子集合 : S1={1,2,4,7} S2={3,5,8} S3={6,9,10} 集合 {S 1, S 2, S 3 } 就被称为集合 S 的一个划分在集合上还有最常用的一些运算, 比如集合的交并补差以及判定一个元素是否是集合中的元素, 等等 Data Structure & Algorithm Analysis 49

50 树的应用为了有效地对集合执行各种操作, 可以用树结构表示集合用树中的一个结点表示集合中的一个元素, 树结构采用双亲表示法存储例如, 集合 S 1 S 2 和 S 3 可分别表示为图 11.14(a) (b) (c) 所示的结构将它们作为集合 S 的一个划分, 存储在一维数组中 (a) 集合 S1 (b) 集合 S2 (c) 集合 S3 图集合的树结构表示 Data Structure & Algorithm Analysis 50

51 树的应用当集合采用这种存储表示方法时, 很容易实现集合的一些基本操作例如, 求两个集合的并集, 就可以简单地把一个集合的树根结点作为另一个集合的树根结点的孩子结点如求上述集合 S 1 和 S 2 的并集, 可以表示为 :S 1 S 2 ={1,2,3,4,5,7,8} 该结果用树结构表示如图所示图集合 S1 并集合 S2 后的树结构示意 Data Structure & Algorithm Analysis 51

52 课堂练习给定集合 {15, 3, 14, 2, 6, 9, 16, 17}, 解答如下问题 : (1) 构造相应的哈夫曼树 ; (2) 计算它的带权路径长度 ; (3) 写出它的 Huffman 编码 ; Data Structure & Algorithm Analysis 52

53 课堂练习构造相应的哈夫曼树给出构造过程续 Data Structure & Algorithm Analysis 53

54 课堂练习计算它的带权路径长度 ; WPL = (2 + 3) x x 4 + ( ) x ( ) x 2 = Huffman 编码 :110 6: : :101 14:111 16:00 2: :01 Data Structure & Algorithm Analysis 54

55 谢谢! Data Structure & Algorithm Analysis 55

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用