数据结构课件：第4章 树2

1、4.1树的基本概念4.2二叉树4.3线索二叉树4.4树和森林4.5压缩与哈夫曼树4.6 应用第四章 树4.3 线索二叉树4.3.1 线索二叉树的定义4.3.2 线索二叉树基本算法 定义4.6 设T*是由增加某种遍历顺序之线索域的结点所构成的一棵二叉树，在T*中可直接查找任一结点在这种遍历顺序下的前驱和后继结点，则称T*为线索二叉树 (ThreadedBinary Tree) . 指向某种遍历次序下的前驱和后继的指针称为线索； 为二叉树的每个结点加上线索，所得的二叉树称为线索二叉树；线索二叉树的结点结构： 按中序遍历得到的线索二叉树称为中序线索二叉树；按先序遍历得到的线索二叉树称为先序线索二叉树

2、；按后序遍历得到的线索二叉树称为后序线索二叉树。leftright datapredsucc 线索二叉树中有许多空指针，存储空间浪费问题未得到有效解决，由此得到改进方案：leftright dataLThreadRThread LThread=0, left域指向结点t的左孩子1, left域指向结点t的中根前驱 RThread=0, right域指向结点t的右孩子1, right域指向结点t的中根后继A00B10C11D01E11改进的中序线索二叉树的存储结构ACBED例改进的中序线索二叉树中根遍历序列： B C A E D例：改进的后序线索二叉树后根遍历序列： C B E D AA00B1

3、0C11D01E11（b）改进的后序线索二叉树rootACBED（a）二叉树 线索二叉树的目的：在中序线索二叉树中不需要对二叉树进行遍历可以方便的找到给定结点的中序前趋和中序后继结点，并且不需要太多额外的空间。 线索二叉树中，一个结点是叶结点的充要条件为：左、右标志 (LThread、RThread) 均是1。 注意：在先序线索二叉树中找给定结点的先序前驱并非有效。在后序线索二叉树中找给定结点的后序后继并非有效。4.3 线索二叉树4.3.1 线索二叉树的定义4.3.2 线索二叉树基本算法给定一棵关于先根（中根、后根）遍历顺序的线索二叉树，可作如下操作：求该二叉树在先根（中根、后根）遍历顺序 下

4、的第一个和最后一个结点；求任一结点在先根（中根、后根）遍历顺序下的前驱和后继结点遍历线索二叉树插入一个新结点删除一个结点线索二叉树基本算法1) 搜索以t为根的线索二叉树的中根序列的第一个结点算法思想：从二叉树根结点出发，沿左指针链往下查找，直至找到一个没有左孩子的结点为止，它是中根遍历顺序下二叉树中第一个被访问的结点； 1、查找中根序列的第一个和最后一个结点搜索以t为根的线索二叉树的中根序列的第一个结点算法FIO( t . q )/* t指向中序线索二叉树T*之根，本算法返回T*的中根序列的首结点，并用q指向它 */FIO1. 初始化 q t . FIO2. 找中根遍历顺序下二叉树中第一个被访

5、问的结点 WHILE LThread (q) 0 DO q Left (q). RETURN q .while（q - LThread = = 0）q = q - Left ;A00B10C11D01E11中序线索二叉树的存储结构2)搜索以t为根的线索二叉树的中根序列的最后一个结点算法思想：即从二叉树根结点出发，沿右指针链往下查找，直至找到一个没有右孩子的结点为止，它是中根遍历顺序下二叉树中最后被访问的结点。 算法LIO( t . q )/* 给定中序线索二叉树T*，t指向T*之根，本算法返回T*的中根序列末结点，并用q指向它 */LIO1. 初始化q t .LIO2. 找中根遍历顺序下二叉树

6、中最后被访问的结点WHILE RThread (q ) 0 DO q Right (q) .RETURN q .while（q - RThread = = 0）q = q - Right;A00B10C11D01E11中序线索二叉树的存储结构 1) 在中序线索二叉树中，查找结点p的中序前驱结点的主要思想如下：若结点p是中根序列的第一个结点，则p无中序前驱结点；/* 情况1 */若结点p非中根序列的第一个结点：若LThread(p) 1，则Left(p)为左线索，直接指向p的中序前驱结点；/* 情况2 */若LThread(p) 0，p的中序前驱结点是p之左子树中根序列的末结点. /* 情况3

7、*/2、 查找中序前驱结点和中序后继结点算法PIO( t , p . q )PIO1. 求T*之中根序列首结点 FIO( t . first ).PIO2. p first？ IF p first THEN (q . RETURN q .)PIO3. 取p之左指针 lp Left (p) .PIO4. LThread(p) 1? IF LThread(p) 1 THEN (q lp . RETURN q .) ELSE (LIO( lp . q ). RETURN q .) 算法PIO( t , p . q )PIO1. 求T*之中根序列首结点 FIO( t . first ).PIO2. p

8、 first？ IF p first THEN (q . RETURN q .)PIO3. 取p之左指针 lp Left (p) .PIO4. LThread(p) 1? IF LThread(p) 1 THEN (q lp . RETURN q .) ELSE (LIO( lp . q ). RETURN q .) ABDECFHIKGJLABDECFHIKGJLPIO1. 求T*之中根序列首结点 FIO( t . first ).PIO2. p first？ IF p first THEN (q . RETURN q .)PIO3. 取p之左指针 lp Left (p) .PIO4. LT

9、hread(p) 1? IF LThread(p) 1 THEN ( q lp . RETURN q .) ELSE (LIO( lp . q ). RETURN q .) ABDECFHIKGJLPIO1. 求T*之中根序列首结点 FIO( t . first ).PIO2. p first？ IF p first THEN (q . RETURN q .)PIO3. 取p之左指针 lp Left (p) .PIO4. LThread(p) 1? IF LThread(p) 1 THEN ( q lp . RETURN q .) ELSE (LIO( lp . q ). RETURN q .

10、) 2) 在中序线索二叉树中，找结点p的中序后继结点的主要思想如下：若结点p是中序序列的末结点，则其无后继结点；/* 情况1 */若结点p非中序序列的末结点：若RThread(p) 1，则Right(p) 指向p之中序后继 /* 情况2，Right(p)为右线索 */若RThread(p) 0，则p之中序后继为p的右子树的中根序列的首结点。/* 情况3 */算法NIO* ( t , p . q)NIO*1. 求中根序列末结点 LIO ( t . last ).NIO*2. p last ? IF p last THEN (q . RETURN q . ) NIO*3. 取p之右指针 rp Ri

11、ght (p) .NIO*4. RThread(p) 1? IF RThread(p) 1 THEN ( qrp . RETURN q .) ELSE ( FIO(rp . q). RETURN q .) ABDECFHIKGJL算法NIO* ( t , p . q)NIO*1. 求中根序列末结点 LIO ( t . last ).NIO*2. p last ? IF p last THEN (q . RETURN q . ) NIO*3. 取p之右指针 rp Right (p) .NIO*4. RThread(p) 1? IF RThread(p) 1 THEN ( qrp . RETURN

12、 q .) ELSE ( FIO(rp . q). RETURN q .) ABDECFHIKGJL算法NIO* ( t , p . q)NIO*1. 求中根序列末结点 LIO ( t . last ).NIO*2. p last ? IF p last THEN (q . RETURN q . ) NIO*3. 取p之右指针 rp Right (p) .NIO*4. RThread(p) 1? IF RThread(p) 1 THEN ( qrp . RETURN q .) ELSE ( FIO(rp . q). RETURN q .) ABDECFHIKGJL算法NIO* ( t , p

13、. q)NIO*1. 求中根序列末结点 LIO ( t . last ).NIO*2. p last ? IF p last THEN (q . RETURN q . ) NIO*3. 取p之右指针 rp Right (p) .NIO*4. RThread(p) 1? IF RThread(p) 1 THEN ( qrp . RETURN q .) ELSE ( FIO(rp . q). RETURN q .) 在后序线索二叉树中，查找结点p之后序前驱结点的主要思想如下： 若结点p是后序序列首结点，则p无后序前驱；/* 情况1 */若结点p非后序序列首结点： 若 LThread(p) 1，则L

14、eft (p)指向p的后序前驱结点；/* 情况2，Left (p)为左线索 */若 LThread(p) 0，则：/* 此时p有左子树. 后序遍历，p之后序前驱必是两子树中最后被遍历的结点，情况3 */若p有右子树，则p之右孩子是其后序前驱；若p无右子树，则p之后序前驱是其左孩子. 3、查找后序前驱和后继结点算法PPO( t , p . q )PPO1. 求后序序列首结点 FPO(t . first ). /* 算法FPO求后序线索二叉树之后序序列首结点，请读者自行给出*/PPO2. pfirst ? IF pfirst THEN (q . RETURN q .) /* p是后序序列的首结点，

15、故p无前驱 */ PPO3. 取Left(p) lpLeft(p).PPO4. LThread(p)1? IF LThread(p)1 THEN (qlp . RETURN q .) /* lp是左线索，lp指向p之前驱 */PPO5. RThread(p)0 ? IF RThread(p)0 THEN (rpRight(p) . qrp . RETURN q .) ELSE (qlp . RETURN q .)在后序线索二叉树T*中，查找结点p之后序后继的主要思想如下：若p是根，则p无后序后继 /* 情况1；对T*作后序遍历，p是最后被访问的结点 */若p非根，则：若RThread(p) 1

16、，则Right(p)指向p之后序后继结点 /* 情况2 */若RThread(p) 0，则：/* 此时p之右子树非空，故需考虑p之父结点；情况3 */若p是其父结点的右孩子，则p之后序后继就是其父结点；若p是其父结点的左孩子且p有右兄弟，则p的后序后继是其父结点之右子树中后序遍历到的首结点；若p是其父结点的左孩子且p无右兄弟，则p的后序后继是其父结点.T*为后序线索树，p为T*中之结点：欲求p之后序前驱，则仅从p出发就能找到。若要找p之后序后继，则仅当p的右子树为空时，才能由p的右线索Right(p)得到；否则必须知道p的父结点，若父结点未知，则可能要从根开始遍历；由此，在后序线索二叉树中查找

17、给定结点之后序后继并不总是有效的。4、遍历线索二叉树算法思想：欲对X序（先序、中序或后序）线索二叉树进行X序遍历，只需从X序遍历序列之首结点p出发，找p的X序后继q，再找q的X序后继r，如此下去直至找到X序之末结点为止。 算法InOrder( t )/* t指向中序线索二叉树T*之根，本算法中根遍历T */InOrder1. 求中根序列首结点 FIO( t . q ) . InOrder2. 用NIO*求q之中序后继 WHILE q DO ( PRINT(Data(q) . NIO*(t , q . q) . )该算法的时间复杂性为O(n). 5、插入在线索二叉树中插入结点p作为结点s的右子结

18、点 若s无右子树:则直接令p成为s的右子结点，并修改s和p的相关指针。p - Right = s - Right ;p - RThread=s - RThread; p - Left = s ;p - LThread = 1 ; s - Right = p ;s - RThread = 0 ;插入前rightsprootrightlefts插入后rootp若s有右子树:将该右子树变成p的右子树，p成为s的右子结点，并修改s和p的相关指针以及该右子树的最左下结点的前趋指针。插入前rootrightleftspright插入后leftleftsprootp - Right = s - Right

19、; p - RThread = s - RThread ; p - Left = s ;p - LThread = 1 ; s - Right = p ; q = p - Right ; FIO(q, p); q - Left = p ;算法IR( p , s )/* 插入结点p作为中序线索二叉树T*之结点s的右子结点 */IR1. p之右指针指向s右指针所指结点 Right ( p ) Right ( s ) . RThread ( p ) RThread ( s ) .IR2. p的左指针指向s Left(p) s . LThread (p) 1 . IR3. s 无右子树？ IF RTh

20、read ( s ) = 1 THEN ( Right(s) p . RThread (s) 0. RETURN . ) /* p成为s的右子结点 */ ELSE ( q Right( p) . FIO(q . q) .)IR4. p分别送q的Left和s的Right域 Left(q) p . Right(s) p . 6、删除结点s的右子结点p（假定p存在） 若p为叶子结点；若p无左子树，有右子树若p无右子树，有左子树若p既有左子树，又有右子树6、删除结点s的右子结点p（假定p存在）若p为叶子结点，只须修改s的RThread的值和Right指针图4.24 删除结点s的右子结点p（情形1）ri

21、ghts删除后rootrightlefts删除前rootps - Right = p - Right ;s - RThread = 1;若p无左子树，有右子树，且右子树的中根序列的第一个结点为temp，则把p的右子树变成s的右子树，并修改temp的前趋指针 s - Right = p - Right ; temp-left = s;若p无右子树，有左子树，且左子树的中根序列的最后一个结点为temp，则把p的左子树变成s的右子树，并修改temp的后继指针.图4.26 删除结点s的右子结点p（情形3）right删除前rightleftprootstemprightleftrootstemp删除后s

22、 - Right =p - Left ; temp-Right=p -Right;若p既有左子树，又有右子树，temp1为p的右子树的中根序列中第一个结点， temp为p的左子树的中根序列中最后一个结点，则把p的左子树变成s的右子树，p的右子树变成temp的右子树。图4.27 删除结点s的右子结点p（情形4）prepretempsuccsucc删除前rootsptemp1presuccroots删除后temptemp1pretemp-Right=p- Right ; temp-RThread=0;s-Right=p - Left ;temp1-Left=temp;4.1树的基本概念4.2二叉树

23、4.3线索二叉树4.4树和森林4.5压缩与哈夫曼树4.6 应用第四章 树4.4.1树与二叉树的转换4.4.2树的顺序存储4.4.3树的链接存储4.4.4树和森林的遍历4.4 树和森林4.4.1树与二叉树的转换 1) 树转换成二叉树 2) 森林转换成二叉树 3) 二叉树转换成树 4) 二叉树转换成森林1）树转换成二叉树 所有兄弟结点之间加一线； 对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线。 按顺时针方向将它旋转45。 ACBFDEACBFDE树由树转换的二叉树 把森林中第一棵树T1的根作为整个森林的根； 把森林中其它树的根依次作为T1的兄弟结点。2）森林转换成二叉树 二叉树

24、GJHIFEACBDACBDFEGJHI森 林3)二叉树转换成树ACBFDEACBFDE二叉树由二叉树转换成树 GJHIFEACBDACBDFEGJHI4）二叉树转成森林4.4.1树与二叉树的转换4.4.2树的顺序存储4.4.3树的链接存储4.4.4树和森林的遍历4.4 树和森林树的顺序存储结构1)先根序列及结点次数表示法2)后根序列及结点次数表示法3)层次序列及结点次数表示法4)层次序列及Father数组表示法1) 树的先根序列及结点次数表示法树的先根遍历的定义（1）访问根结点（2）从左到右依次先根次序遍历树的诸子树RADEFCBGKH先根序列RADEBCFGHK定理4.2 如果已知一个树的

25、先根序列和每个结点相应的次数，则能唯一确定该树的结构。证明：用数学归纳法1. 若树中只有一个结点，定理显然成立。2. 假设树中结点个数小于n(n2)时定理成立。3. 当树中有n个结点时，由树的先根序列可知，第一个结点是根结点，设该结点的次数为k, k1，因此根结点有k个子树。第一个子树排在最前面，第k个子树排在最后面，并且每个子树的结点个数小于n，由归纳假设可知，每个子树可以唯一确定，从而整棵树的树形可以唯一确定。证毕。 例：先根序列： A B C D E F G H I J K L 结点的次数: 4 0 3 0 0 0 0 2 2 0 0 0 ACEDBGHJIFLK2) 后根序列和结点次数

26、表示法后根序列 B D E F C G J K I L H A结点的次数 0 0 0 0 3 0 0 0 2 0 2 4ACEDBGHJIFLK3) 层次序列和结点次数表示法已知一个树的层次序列和每个结点次数，则能唯一确定该树的结构。层次序列 A B C D E F结点的次数 3 0 2 0 0 0ACBFDE4) 层次序列和Father数组表示法便于涉及祖先的操作，求结点的孩子时需要遍历整棵树。A0BCDEF11133135426数组下标ACBFDE树Father数组表示4.4.1树与二叉树的转换4.4.2树的顺序存储4.4.3树的链接存储4.4.4树和森林的遍历4.4 树和森林 1) Fa

27、ther链接结构:ACBDFEFather链接提供了“向上”访问的能力，但很难确定一个结点是否为叶结点，也很难求结点的子结点，且不易实现遍历操作。ACBFDE2) 孩子链接结构*会出现大量指针为空的情况，浪费空间。 A结点大小固定的连接结构BCDFE2) 孩子链接结构*节省了空间，但给操作和管理带来不便。3ABFEDC2结点大小不固定的连接结构3) 孩子链表表示法ABCDECBFDE3) 孩子链表表示法*孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个数组中。孩子结点的数据域仅存放了它们在数组空间的下标。*与Father链

28、接表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与父结点有关的操作。 4) 父亲孩子链表表示*将Father数组表示法和孩子链表表示法结合起来，可形成父亲孩子链表表示法。 ABCDEF13542624356011133 Data Firstchild 父亲孩子链表表示结点结构firstChildnextBrotherData5)左孩子-右兄弟链接结构（二叉树表示法）*这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。RADEFCBGKHRADECHFGBK左孩子-右兄弟表示法示例：树的左孩子右兄弟表示法的实现结点类TreeNo

29、detemplate class TreeNode friend class Tree ; private: T data ; TreeNode *firstChild，*nextBrother ; pulic: TreeNode(T value , TreeNode*L, TreeNode *R ) / 构造函数 TreeNode( ) ；树类Tree的声明templateclass Tree private : TreeNode *root ;/ 根结点 public : Tree ( ); / 构造函数 Tree ( ); / 析构函数 TreeNode * FirstChild (Tr

30、eeNode *p); /返回结点p的大儿子结点 TreeNode * NextBrother ( TreeNode *p); /返回结点p的下一个兄弟结点 TreeNode * FindFather ( TreeNode *t , TreeNode *p ); /在树t中搜索p的父结点TreeNode * FindTarget ( TreeNode *t , T target ); /在树t中搜索值为target的结点 void DelSubtree ( TreeNode *t ,TreeNode *p ); /在树t中删除以p为根的子树 void Del ( TreeNode *p );

31、void PreOrder (TreeNode * t); /先根遍历以t为根结点的树 void NorecPreOrder (TreeNode * t ); /非递归先根遍历以t为根结点的树 void LevelOrder ( TreeNode * t ); /层次遍历以t为根结点的树 ;FindFather(t, p)算法思想：令q指向t的大儿子结点，若q=p，t就是p的父结点；否则，在以q为根的子树中找p的父结点，即 FindFather(q,p);若未找到，令q指向t的下一个儿子结点，即q的右兄弟结点，重复上述步骤，直至找到p的父结点或找完t的所有儿子结点。 搜索父结点 算法FindF

32、ather( t, p. result)FF1寻找t的第一棵子树 IF t OR p THEN RETURN result ELSE qFirstChild (t).FF2从t的第一棵子树开始搜索，若搜索到，则返回；否则，搜索t的下一棵子树 WHILE q AND qp DO ( FindFather( q , p. result) IF result THEN qNextBrother(q) ELSE RETURN result . )FF3递归出口：若p是t的一个子结点，令指针 result 指向t IF q p THEN RETURN result t . ELSE RETURN res

33、ult . ACBFDEACBFDEFindTarget (t , target )算法思想：若t的数据域为target，则指针result指向t；否则，p指向t的大儿子结点，在以p为根的树中进行搜索(递归调用)若在以p为根的树中搜索失败，p指向其右兄弟结点，继续进行上述搜索，直到找到数据域等于target的结点或p为空。 搜索指定数据域的结点算法FindTarget(t, target. result)FT1t不存在或为所求 IF t THEN RETURN result . IF Data (t) target THEN ( RETURN result t . )FT2从t的第一棵子树开始

34、搜索 p FistChild ( t ) . WHILE p DO ( FindTarget (p , target. result). IF result THEN pNextBrother( p ) ELSE RETURN result . )FT3在以t为根的树中，没有搜索到数据成员等于target的结点 RETURN result . 搜索大儿子结点和大兄弟结点算法GFC(p. q)GFC1. 指针p所指结点存在，并且存在大儿子结点 IF p AND FistChild (p ) THEN RETURN q FistChild (p ) . ELSE RETURN q . 算法GNB

35、( p . q )GNB1. 指针p所指结点存在，并且存在下一个兄弟结点 IF p AND NextBrother (p ) THEN RETURN q NextBrother (p ). ELSE RETRUN q . 三种情况：1、删除以根结点R为根的树2、删除以大儿子结点A为根的子树3、删除以结点B或C(非大儿子)为根的子树RADEFCBGKH 删除子树 删除子树算法DS (t, p ) /修改p的父结点指针域DS1. t或p不存在 IF t OR p THEN RETURN.DS2. 确定p所指结点的父结点是否存在 FindFather( t , p . result). IF res

36、ult THEN（ Del(p) RETURN.）DS3. 若p所指结点的父结点存在，并且p是其父结点的大儿子结点 IF FistChild ( result ) p THEN (FistChild ( result ) NextBrother ( p ). Del ( p ). RETURN. )DS4. 若p所指结点的父结点存在，并且p不是其父结点的大儿子结点，则搜索p的前一个兄弟结点q q FistChild ( result ). WHILE NextBrother ( q ) p DO q NextBrother ( q ). NextBrother ( q ) NextBrothe

37、r ( p ). Del ( p ). RETURN. 算法Del ( p )/*释放根为p的子树所占用的空间 */ Del1. 指针p所指结点不存在，则返回 IF p THEN RETURN.Del2. 从左到右删除p的子树 q FistChild ( p ). WHILE q DO ( next NextBrother ( q ) . Del ( q ) . q next . ) AVAIL p . ACBDACBD4.4.1树与二叉树的转换4.4.2树的顺序存储4.4.3树的链接存储4.4.4树和森林的遍历4.4 树和森林1、树的遍历 先根遍历：先访问树的根结点，然后依次先根遍历每棵子树

38、。先根遍历序列：A B C E F DACBFDE后根遍历：先依次后根遍历每棵子树，然后访问树的根结点。 后根遍历序列：B E F C D AACBFDE 2、森林的遍历先根遍历 访问森林中第一棵树的根结点； 先序遍历第一棵树中的诸子树； 先序遍历其余的诸树。森林的先根遍历序列：A B C D E F G H I J 二叉树的先根序列：A B C D E F G H I J GJHIFEACBDACBDFEGJHI 后根遍历森林： 后序遍历第一棵树的诸子树； 访问森林中第一棵树的根结点； 后序遍历其余的诸树。 森林的后根遍历序列： B C D A F E H J I G二叉树的中根序列： B

39、C D A F E H J I GGJHIFEACBDACBDFEGJHI递归算法先根遍历以t为根的树算法PreOrder( t )PreOrder1. 若t为空返回 IF t = THEN RETURN.PreOrder2. 访问t所指结点 PRINT(Data ( t ) ).PreOrder3. 将指针 t 定位到它所指结点的第一个子结点 GFC( t . child );PreOrder4. 先根遍历t所指结点的诸子树 WHILE child DO ( PreOrder (child). GNB(child . child). ) ACBFDE首先，将结点p设为根结点。(1)若结点p不

40、为空，访问结点p，将结点p压入栈，并将其大儿子结点设为结点p；反复执行(1)，直至结点p为空。(2)从栈中弹出一个结点，若它有大兄弟结点，则将其大兄弟结点压入栈；否则，反复执行(2)，直至弹出的结点有大兄弟结点或栈空。(3)反复执行(1)(2)，直至栈为空。 迭代算法先根遍历以t为根的树算法NPO( t )NPO1. 初始化堆栈S S AVAILNPO2. 保存根指针 p t . 迭代算法先根遍历以t为根的树NPO3. 若p所指结点不为空，访问p所指结点，将p压入栈，并将其FistChild指针设为p. WHILE p DO (PRINT ( Data ( p ) ). Push (S , p

41、 ). p FistChild (p ). )NPO4. 从栈中弹出指针，直至弹出的指针所指结点有大兄弟结点或栈空以至无结点可弹出。 WHILE p = AND S非空 DO ( Pop ( S . p ). p NextBrother ( p ). )NPO5. 重复上述过程 IF S非空 THEN GOTO NPO3. 树和森林的层次遍历例 森林的层次遍历序列： A E G B C D F H I JACBDFEGJHI4.1树的基本概念4.2二叉树4.3线索二叉树4.4树和森林4.5压缩与哈夫曼树4.6 应用第四章 树4.5.1文件编码4.5.2扩充二叉树4.5.3哈夫曼树与哈夫曼编码4

42、.5 压缩与哈夫曼树 数据压缩是计算机科学中的重要技术。数据压缩过程称为编码，即将文件中的每个字符均转换为一个唯一的二进制位串。 数据解压过程称为解码，即将二进制位串转换为对应的字符。压缩的关键在于编码的方法，哈夫曼编码是一种最常用无损压缩编码方法。4.5.1 文件编码 假设有一个文件仅包含7个字符：a、e、i、s、t、sp（空格）和nl（换行），且文件中有10个a，15个e，12个i，3个s，4个t，13个sp，1个nl。 因为log27 = 3，所以，每个字符都至少由一个3位的二进制串表示。于是文件的总位数至少应该是： 103 + 153 + 123 + 33 + 43 + 133 + 1

43、3 = 174 . 在实际应用的一些大文件中，字符被使用的比率是非平均的，即有些字符出现的次数多，而有些字符出现的次数却非常少。如果所有字符都由等长的二进制码表示，那么将造成空间浪费。 如何才能减少不必要的空间浪费呢？文件压缩的通常策略是：采用不等长的二进制码，令文件中出现频率高的字符的编码尽可能短。但是，采用不等长编码又可能会产生多义性。例如：如果用01表示a，10表示b，1001表示c，那么对于编码1001，我们无法确定它表示字符c ，还是表示字符串ba ，其原因是b的编码与c的编码的开始（前缀）部分相同。为了避免出现多义性，就必须要求字符集中任何字符的编码都不是其它字符的编码的前缀，满足

44、这个条件的编码被称为前缀码。显然，等长编码是前缀码。怎样的前缀码才能使文件的总编码长度最短？设组成文件的字符集A=a1,a2,an，其中，ai的编码长度为li；ai出现的次数为ci 。要使文件的总编码最短，就必须要确定li，使 ci li 取最小值.如何设计出使上式最小的前缀码？Huffman于1952年提出了哈夫曼算法。i =1n4.5.1文件编码4.5.2扩充二叉树4.5.3哈夫曼树与哈夫曼编码4.5 压缩与哈夫曼树4.5.2 扩充二叉树定义4.9 为了使问题的处理更为方便，每当原二叉树中出现空子树时，就增加特殊的结点空树叶，由此生成的二叉树称为扩充二叉树。 (a) (b) 二叉树和它的扩

45、充二叉树 扩充二叉树每一个圆形结点都有两个儿子，每一个方形结点没有儿子。 规定空二叉树的扩充二叉树只有一个方形结点。圆形结点称为内结点，方形结点称为外结点。 定义4.10 扩充二叉树的外通路长度定义为从根到每个外结点的路径长度之和，内通路长度定义为从根到每个内结点的路径长度之和。外通路长度为 3 3 2 3 4 4 3 3=25内通路长度为 2 1 0 2 3 12=11.定义4.11 给扩充二叉树中n个外结点赋上一个实数，称为该结点的权。树的加权外通路长度定义为WPL： 其中，n表示外结点的个数，wi和Li分别表示外结点ki的权值和根到ki之间的路径长度。 加权外通路长度分别是 4*2+2*

46、3+3*3+11*1=34 3*2+4*3+11*3+2*1=53 2*2+11*2+3*2+4*2=40423113411223411 （a） （b） （c） 定义4.12 在外结点权值分别为w0,w1,wn-1的扩充二叉树中，加权外通路长度最小的扩充二叉树称为最优二叉树 。4.5.1文件编码4.5.2扩充二叉树4.5.3哈夫曼树与哈夫曼编码4.5 压缩与哈夫曼树文件编码问题就变成构造最优二叉树问题，每个外结点代表一个字符，其权值代表该字符的频率，从根到外结点的路径长度就是该字符的编码长度 .为求得最优二叉树，哈夫曼巧妙的设计了哈夫曼算法，通过哈夫曼算法可以建立一棵哈夫曼树，从而为压缩文本文

47、件建立哈夫曼编码。哈夫曼算法基本思想： 把每个结点都作为一棵二叉树的根结点，这n个根结点就组成了一个森林。我们把结点在文件中出现的次数定义为该结点的权值。 (1) 在森林中取权值最小的两个根结点s和nl，合并成一棵二叉树，并生成一个新结点T1，作为这两个结点的父结点，T1的权值是它的两个子结点的权值之和。显然，T1成为新的根结点，而s和nl成为T1的子结点，同时，森林中减少了一棵树。 (2) 对新森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。 由上述方法构造出的二叉树，被称为“哈夫曼树”。 例: F=7,5,2,4 2475116187524752647524116定理4.3 在

48、外结点权值分别为w0,w1,wn-1的扩充二叉树中，由哈夫曼算法构造出的哈夫曼树的带权路径长度最小，因此哈夫曼树为最优二叉树。由观察可知，字符集中的字符所在的结点均是哈夫曼树中的外结点。哈夫曼树中没有度为1的结点。哈夫曼编码：将哈夫曼树每个分支结点的左分支标上0，右分支标上1，把从根结点到每个叶结点的路径上的标号连接起来，作为该叶结点所代表的字符的编码，这样得到的编码称为哈夫曼编码。根据定理4.3知道，对于所有的编码，哈夫曼编码使文件的总编码长度最短。实际上，哈夫曼算法的应用很广，这里只是以哈夫曼编码为例来说明哈夫曼算法。哈夫曼编码 哈夫曼编码的主要用途是实现数据压缩。 设给出一段报文： CA

49、ST CAST SAT AT A TASA 字符集合是 C, A, S, T 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 01001110 01001110 110010 0010 00 10001100 则总编码长度为 18 * 2 = 36.例 哈夫曼编码报文：CAST CAST SAT AT A TASA字符集合是 C, A, S, T ，各个字符出现的频度(次数)是 W 2, 7, 4, 5 编码 A (0) T (10) C (110) S (111)7542011100TACS61118总编码长度：1*7+2*5+3*2+3*4=35在构造哈夫曼

50、树的过程中，没有一片树叶是其他树叶的祖先，所以每个叶结点对应的编码不可能是其他叶结点对应的编码的前缀，由此可知哈夫曼编码是二进制的前缀码。哈夫曼编码是否唯一？哈夫曼树中每个结点的结构为：其中，LLINK和RLINK为链接域，INFO为信息域，Weight为该结点的权值。INFORLINK WEIGHTLLINKsucc编码：依次将数据文件中的字符按哈夫曼树转换成哈夫曼编码。解码：依次读入文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向其左孩子，否则走向其右孩子，到达某一叶结点时，便可以译出相应的字符。 4.1树的基本概念4.2二叉树4.3线索二叉树4.4树和森林4.5压缩与哈夫曼树

51、4.6 应用第四章 树4.6.1 表达式求值问题1、表达式树的建立 表达式求值是程序设计语言编译的一个基本问题。 表达式有一个内在二叉树结构，表达式(ab)(cd)e对应的二叉树如下图所示，二叉树中叶结点是表达式中的变量或常数（如：a, b），非叶结点是操作符。eabcd对表达式树做后根遍历可以得到后缀表达式：ab+cd-*e- 如果不考虑一元操作符负号，可以用后缀表达式构造表达式对应的二叉树。二叉树的建立过程如下： 从左向右依次扫描后缀表达式中各个符号，1）如果当前被扫描的符号是操作数，则生成一个新结点，以此操作数作为该结点的数据域，将此结点作为新二叉树的根结点压入堆栈中。2）如果当前被扫描

52、的符号为二元操作符，则生成一个新结点，并以此操作符作为该结点的数据域，从栈顶弹出两个结点，创造一棵以新生成结点为根、以弹出的两个结点为其右子结点和左子结点的新二叉树，将新树根压入堆栈。 按照上述方法处理完表达式中所有符号后，堆栈中仅包含一个结点，即所求二叉树的根结点。例：根据后缀表达式ab+cde+*的值。构造一棵表达式树 例：根据后缀表达式ab+cde+*的值。构造一棵表达式树 算法 CET(expr . t)/*算法CET利用辅助堆栈S构造表达式expr对应的二叉树, 算法结束时指针t 指向二叉树根结点；CET是CreatExpressTree之缩写*/CET1. 创建一个辅助堆栈 CREATE ( S ). Read ( op ). /读入表达式序列中的一个符号CET2. 扫描表达式 WHILE op # DO ( IF op= OR op= OR op= OR op= THEN ( rpr S. lpr S. pAVAIL. Data(p)op. Left(p)lpr. Right(p)rpr. Sp . ) ELSE ( pAVAIL. Data(p)op. Left(p). Right(p). Sp . ) Read ( op ). /读入表达式序列中