《数据结构课件：08 第四章 树2》由会员分享，可在线阅读，更多相关《数据结构课件：08 第四章 树2（53页珍藏版）》请在金锄头文库上搜索。
1、4.1树的基本概念树的基本概念4.2二叉树二叉树4.3线索二叉树线索二叉树4.4树和森林树和森林4.5压缩与哈夫曼树压缩与哈夫曼树4.6应用应用第四章 树在在二二叉叉树树的的应应用用中中，我我们们经经常常根根据据需需要要，而而附附加加或或改改造造成成另另一一种种形形式式，从从而而更更加加便便于于解解决决相相应应的的实实际际问问题题，或或提提高高程程序序的的空空间间和和时时间间效效率率。线线索索二二叉叉树树就就是是二二叉叉树的一种重要的改进。树的一种重要的改进。4.3线索二叉树线索二叉树n n以以Left/Right链链接接表表示示的的二二叉叉树树结结构构，可可看看作作是是有有很很多多从从根根结
2、结点点一一直直到到叶叶结结点点的的单单链链表表组组成成的的，一一个个结结点点的的前前驱驱结结点点是是其其父父结结点点，一个结点的后继结点是它的儿子结点。一个结点的后继结点是它的儿子结点。n n这这种种结结构构有有两两方方面面不不足足：其其一一是是从从一一个个结结点点只只能能访访问问它它的的儿儿子子结结点点，而而不不能能访访问问它它的的父父结结点点；其其二二是是这这种种结结构构通通常常包包含含很很多多未未被被有有效效使使用用的的指指针针字字段段，譬譬如如包包含含i个个结结点点的的二二叉树，在其叉树，在其2i个指针域中仅有个指针域中仅有i-1个被使用个被使用.通过遍历二叉树可得到结点的一个线性通过
3、遍历二叉树可得到结点的一个线性序列，在线性序列中，除第一个结点外，每序列，在线性序列中，除第一个结点外，每个结点有且仅有一个前趋，除最后一个结点个结点有且仅有一个前趋，除最后一个结点外，每个结点有且仅有一个后继，但是外，每个结点有且仅有一个后继，但是在二在二叉树上只能找到结点的左孩子、右孩子，结叉树上只能找到结点的左孩子、右孩子，结点在线性序列中的前趋和后继只有在遍历过点在线性序列中的前趋和后继只有在遍历过程中才能得到程中才能得到。 如何快速找到给定结点在前（中、后）如何快速找到给定结点在前（中、后）根下的前驱和后继？根下的前驱和后继？ 通过前（中、后）根遍历？通过前（中、后）根遍历？ 加入新
4、的指针。加入新的指针。4.3线索二叉树线索二叉树4.3.1线索二叉树的定义线索二叉树的定义4.3.2线索二叉树基本算法线索二叉树基本算法n n为为使使二二叉叉树树之之结结点点的的访访问问更更方方便便，其其空空间间的的利利用用更更高高效效.1960年年，A.J.Perlis和和C.Thornton提提出出了了巧巧妙妙的的线线索索二二叉叉树树表表示示，并并给给出出了了以以各各种种顺顺序序遍遍历历线线索索二二叉叉树树的的重重要要思思想想。但但是是A.J.Perlis和和C.Thornton提提出出的的只只是是单单向向的的线线索索二二叉叉树树.1963年年，A.W.Holt提提出出了了双双向向线线索索
5、二二叉树。叉树。为了同结点在二叉树中所具有的前驱（即为了同结点在二叉树中所具有的前驱（即父结点）和后继（即子结点）区别开来，父结点）和后继（即子结点）区别开来，通常把序列中的结点的前驱或后继通常把序列中的结点的前驱或后继冠以某冠以某种遍历的名称种遍历的名称，如把中根序列中结点的前，如把中根序列中结点的前驱称作驱称作中根前驱中根前驱，结点的后继称作，结点的后继称作中根后中根后继继。定义定义4.6设设T*是由增加某种遍历顺是由增加某种遍历顺序之线索域的结点所构成的一棵二序之线索域的结点所构成的一棵二叉树，在叉树，在T*中可直接查找任一结点中可直接查找任一结点在这种遍历顺序下的前驱和后继结在这种遍历
6、顺序下的前驱和后继结点，则称点，则称T*为为线索二叉树线索二叉树(ThreadedBinaryTree).v 指向指向指向指向某种遍历次序下的前驱和后继的某种遍历次序下的前驱和后继的指针指针指针指针称为称为线索线索线索线索；vv 为二叉树的每个结点为二叉树的每个结点为二叉树的每个结点为二叉树的每个结点加上线索，所得的二叉树称为加上线索，所得的二叉树称为线索二叉树线索二叉树；线索二叉树的线索二叉树的线索二叉树的线索二叉树的结点结构结点结构结点结构结点结构： 按中序遍历得到的线索二叉树称为按中序遍历得到的线索二叉树称为中序线索二叉树中序线索二叉树中序线索二叉树中序线索二叉树；按先序遍历得到的线索二
7、叉树称为按先序遍历得到的线索二叉树称为先序线索二叉树先序线索二叉树先序线索二叉树先序线索二叉树；按后序遍历得到的线索二叉树称为按后序遍历得到的线索二叉树称为后序线索二叉树后序线索二叉树后序线索二叉树后序线索二叉树。leftrightdatapredsucc例：中序线索二叉树例：中序线索二叉树中根遍历序列：中根遍历序列：BCAED例：后序线索二叉树例：后序线索二叉树后根遍历序列：后根遍历序列：CBEDA线索二叉树中有许多空指针，存储空间浪费问题未线索二叉树中有许多空指针，存储空间浪费问题未线索二叉树中有许多空指针，存储空间浪费问题未线索二叉树中有许多空指针，存储空间浪费问题未得到有效解决，由此得
8、到改进方案：得到有效解决，由此得到改进方案：得到有效解决，由此得到改进方案：得到有效解决，由此得到改进方案：leftrightdataLThreadRThreadLThread=0,left域指向结点域指向结点t的左孩子的左孩子1,left域指向结点域指向结点t的的中根前驱中根前驱RThread=0,right域指域指向向结点结点t的右孩子的右孩子1,right域指域指向向结点结点t的的中根后继中根后继A00B10C11D01E11中序线索二叉树的存储结构中序线索二叉树的存储结构ACBED例例改进的中序线索二叉树改进的中序线索二叉树中根遍历序列：中根遍历序列：BCAED例：改进的后序线索二叉树
9、例：改进的后序线索二叉树后根遍历序列：后根遍历序列：CBEDA 线索二叉树的目的线索二叉树的目的：在在中序线索二叉树中序线索二叉树中不需要对二叉树进行遍中不需要对二叉树进行遍历可以方便的找到给定结点的中序前趋和中历可以方便的找到给定结点的中序前趋和中序后继结点，并且不需要太多额外的空间。序后继结点，并且不需要太多额外的空间。v线索二叉树中，一个结点是叶结点的充要线索二叉树中，一个结点是叶结点的充要条件为：左、右标志条件为：左、右标志(LThread、RThread)均是均是1。 4.3线索二叉树线索二叉树4.3.1线索二叉树的定义线索二叉树的定义4.3.2线索二叉树基本算法线索二叉树基本算法n
10、 n给定一棵关于先根（中根、后根）遍历顺序的线索二叉给定一棵关于先根（中根、后根）遍历顺序的线索二叉给定一棵关于先根（中根、后根）遍历顺序的线索二叉给定一棵关于先根（中根、后根）遍历顺序的线索二叉树，可作如下操作：树，可作如下操作：树，可作如下操作：树，可作如下操作：求该二叉树在先根（中根、后根）遍历顺序下的第一求该二叉树在先根（中根、后根）遍历顺序下的第一求该二叉树在先根（中根、后根）遍历顺序下的第一求该二叉树在先根（中根、后根）遍历顺序下的第一个和最后一个结点；个和最后一个结点；个和最后一个结点；个和最后一个结点；求任一结点在先根（中根、后根）遍历顺序下的前驱求任一结点在先根（中根、后根）
11、遍历顺序下的前驱求任一结点在先根（中根、后根）遍历顺序下的前驱求任一结点在先根（中根、后根）遍历顺序下的前驱和后继结点和后继结点和后继结点和后继结点遍历线索二叉树遍历线索二叉树遍历线索二叉树遍历线索二叉树插入一个新结点插入一个新结点插入一个新结点插入一个新结点删除一个结点删除一个结点删除一个结点删除一个结点线索二叉树基本算法线索二叉树基本算法1) 搜索以搜索以t为根的线索二叉树的中根序列的第一为根的线索二叉树的中根序列的第一个结点个结点算法思想：算法思想：从从二二叉叉树树根根结结点点出出发发，沿沿左左指指针针链链往往下下查查找找，直直至至找找到到一一个个没没有有左左孩孩子子的的结结点点为为止止
12、，它它是是中中根遍历顺序下二叉树中第一个被访问的结点；根遍历顺序下二叉树中第一个被访问的结点； 1、查找、查找中根序列的第一个和最后一个结点中根序列的第一个和最后一个结点搜索以搜索以t为根的线索二叉树的中根序列的第一个结点为根的线索二叉树的中根序列的第一个结点算法算法FIO( t.q)/*t指向中序线索二叉树指向中序线索二叉树T*之根，本算法返回之根，本算法返回T*的中根序列的中根序列的首结点，并用的首结点，并用q指向它指向它*/FIO1.初始化初始化 qt .FIO2.找中根遍历顺序下二叉树中第一个被访问的结点找中根遍历顺序下二叉树中第一个被访问的结点WHILELThread (q) 0DO
13、qLeft (q).RETURNq .while（q - LThread = = 0）q = q - Left ;A00B10C11D01E11中序线索二叉树的存储结构中序线索二叉树的存储结构while（q - LThread = = 0）q = q - Left ;A10D01E112)搜索以搜索以t为根的线索二叉树的中根序列的为根的线索二叉树的中根序列的最后一个结点最后一个结点算法思想：算法思想：即即从从二二叉叉树树根根结结点点出出发发，沿沿右右指指针针链链往往下下查查找找，直直至至找找到到一一个个没没有有右右孩孩子子的的结结点点为为止止，它它是是中中根根遍遍历历顺顺序序下下二二叉叉树树中
14、中最最后后被被访问的结点。访问的结点。 算法算法LIO(t .q)/*给定中序线索二叉树给定中序线索二叉树T*，t指向指向T*之根，本算法返回之根，本算法返回T*的中根序列末结点，并用的中根序列末结点，并用q指向它指向它*/LIO1.初始化初始化qt.LIO2.找中根遍历顺序下二叉树中最后被访问的结点找中根遍历顺序下二叉树中最后被访问的结点WHILERThread (q ) 0DOqRight (q).RETURNq.while（q - RThread = = 0）q = q - Right;A00B10C11D01E11中序线索二叉树的存储结构中序线索二叉树的存储结构n n二二叉叉树树T*先
15、先根根序序列列第第一一个个结结点点和和后后根根序序列最后一个结点列最后一个结点都是树的根结点。都是树的根结点。n n先先根根序序列列的的最最后后一一个个结结点点则则分分两两种种情情况况：若若T*根根结结点点存存在在右右子子树树，则则其其右右子子树树先先根根序序列列的的最最后后一一个个结结点点就就是是整整棵棵二二叉叉树树先先根根序序列列的的最最后后一一个个结结点点；若若T*之之根根结结点点不不存存在在右右子子树树，但但T*之之根根结结点点存存在在左左子子树树，则则其其左左子子树树先先根根序序列列最最后后一一个结点就是个结点就是T*先根序列的最后一个结点。先根序列的最后一个结点。n n二二叉叉树树
16、T*后后根根序序列列第第一一个个结结点点也也存存在在两两种种情情况况：若若T*之之根根结结点点存存在在左左子子树树，则则其其左左子子树树后后根根序序列列第第一一个个结结点点就就是是T*之之后后根根序序列列的的第第一一个个结结点点；若若T*无无左左子子树树，但但T*之之根根结结点点存存在在右右子子树树，则则其其右右子子树树后后根根序序列列第第一一个个结结点点就就是是T*之之后后根序列的第一个结点。根序列的第一个结点。1)在中序线索二叉树中，查找结点在中序线索二叉树中，查找结点p的中序的中序前驱结点的主要思想如下：前驱结点的主要思想如下：n n若结点若结点p是中根序列的第一个结点，则是中根序列的第
17、一个结点，则p无无中序前驱结点；中序前驱结点；/*情况情况1*/n n若结点若结点p非中根序列的第一个结点：非中根序列的第一个结点：若若若若LThreadLThread( (p p) ) 1 1，则，则，则，则LeftLeft( (p p) )为左线索，直接指为左线索，直接指为左线索，直接指为左线索，直接指向向向向p p的中序前驱结点；的中序前驱结点；的中序前驱结点；的中序前驱结点；/*/*情况情况情况情况2*/2*/若若若若LThreadLThread( (p p) ) 0 0，p p的中序前驱结点是的中序前驱结点是的中序前驱结点是的中序前驱结点是p p之左子之左子之左子之左子树中根序列的末
18、结点树中根序列的末结点树中根序列的末结点树中根序列的末结点./*./*情况情况情况情况3*/3*/2、查找中序前驱结点查找中序前驱结点和中序后继结点和中序后继结点算法算法算法算法PIO(PIO(t t , ,p p. .q q) )PIO1.PIO1.求求求求T T* *之中根序列首结点之中根序列首结点之中根序列首结点之中根序列首结点 FIO(FIO(t t. .firstfirst).).PIO2.PIO2.p p firstfirst？ IFIFp p firstfirstTHEN(THEN(q q .RETURN.RETURNq q.).)PIO3.PIO3.取取取取p p之左指针之左指
19、针之左指针之左指针 lplp LeftLeft( (p p).).PIO4.PIO4.LThreadLThread( (p p) ) 1?1?IFIFLThreadLThread( (p p) ) 1 1THEN(THEN(q q lplp.RETURN.RETURNq q.).)ELSE(ELSE(LIO(LIO(lplp. .q q).).RETURNRETURNq q.).)PIO1.PIO1.求求求求T T* *之中根序列首结点之中根序列首结点之中根序列首结点之中根序列首结点 FIO(FIO(t t. .firstfirst).).PIO2.PIO2.p p firstfirst？ I
20、FIFp p firstfirstTHEN(THEN(q q . .RETURNRETURNq q.).)PIO3.PIO3.取取取取p p之左指针之左指针之左指针之左指针 lplp LeftLeft( (p p).).PIO4.PIO4.LThreadLThread( (p p) ) 1?1?IFIFLThreadLThread( (p p) ) 1THEN(1THEN(q q lplp.RETURN.RETURNq q.)ELSE(LIO(.)ELSE(LIO(lplp . .q q).RETURN).RETURNq q.).)ABDECFHIKGJLABDECFHIKGJLPIO1.PI
21、O1.求求求求T T* *之中根序列首结点之中根序列首结点之中根序列首结点之中根序列首结点 FIO(FIO(t t. .firstfirst).).PIO2.PIO2.p p firstfirst？ IFIFp p firstfirstTHEN(THEN(q q . .RETURNRETURNq q.).)PIO3.PIO3.取取取取p p之左指针之左指针之左指针之左指针 lplp LeftLeft( (p p).).PIO4.PIO4.LThreadLThread( (p p) ) 1?1?IFIFLThreadLThread( (p p) ) 1THEN(1THEN(q q lplp.RE
22、TURN.RETURNq q.).)ELSE(LIO(ELSE(LIO(lplp. .q q).).RETURNRETURNq q.).)ABDECFHIKGJLPIO1.PIO1.求求求求T T* *之中根序列首结点之中根序列首结点之中根序列首结点之中根序列首结点 FIO(FIO(t t. .firstfirst).).PIO2.PIO2.p p firstfirst？ IFIFp p firstfirstTHEN(THEN(q q . .RETURNRETURNq q.).)PIO3.PIO3.取取取取p p之左指针之左指针之左指针之左指针 lplp LeftLeft( (p p).).P
23、IO4.PIO4.LThreadLThread( (p p) ) 1?1?IFIFLThreadLThread( (p p) ) 1THEN(1THEN( q q lplp.RETURN.RETURNq q.).)ELSE(LIO(ELSE(LIO(lplp. .q q).).RETURNRETURNq q.).)2)2)在中序线索二叉树中，找结点在中序线索二叉树中，找结点在中序线索二叉树中，找结点在中序线索二叉树中，找结点p p的中序后继结的中序后继结的中序后继结的中序后继结点的主要思想如下：点的主要思想如下：点的主要思想如下：点的主要思想如下：n n若结点若结点若结点若结点p p是中序序列
24、的末结点，则其无后继结是中序序列的末结点，则其无后继结是中序序列的末结点，则其无后继结是中序序列的末结点，则其无后继结点；点；点；点；/*/*情况情况情况情况1*/1*/n n若结点若结点若结点若结点p p非中序序列的末结点：非中序序列的末结点：非中序序列的末结点：非中序序列的末结点：若若若若RThreadRThread( (p p) ) 1 1，则，则，则，则RightRight( (p p) )指向指向指向指向p p之中序后之中序后之中序后之中序后继继继继 /*/*情况情况情况情况2 2，RightRight( (p p) )为右线索为右线索为右线索为右线索* */ /若若若若RThrea
25、dRThread( (p p) ) 0 0，则，则，则，则p p之中序后继为之中序后继为之中序后继为之中序后继为p p的右子的右子的右子的右子树的中根序列的首结点。树的中根序列的首结点。树的中根序列的首结点。树的中根序列的首结点。/*/*情况情况情况情况3*/3*/算法算法NIO*(t ,p .q)NIO*1.求中根序列末结点求中根序列末结点LIO(t.last).NIO*2.p last?IFp lastTHEN(q.RETURNq.)NIO*3.取取p之右指针之右指针 rpRight(p).NIO*4.RThread(p) 1?IFRThread(p) 1THEN(qrp.RETURNq.
26、)ELSE(FIO(rp.q).RETURNq.)ABDECFHIKGJL算法算法NIO*(t ,p .q)NIO*1.求中根序列末结点求中根序列末结点LIO(t.last).NIO*2.p last?IFp lastTHEN(q.RETURNq.)NIO*3.取取p之右指针之右指针 rpRight(p).NIO*4.RThread(p) 1?IFRThread(p) 1THEN(qrp.RETURNq.)ELSE(FIO(rp.q).RETURNq.)ABDECFHIKGJL算法算法NIO*(t ,p .q)NIO*1.求中根序列末结点求中根序列末结点LIO(t.last).NIO*2.p
27、last?IFp lastTHEN(q.RETURNq.)NIO*3.取取p之右指针之右指针 rpRight(p).NIO*4.RThread(p) 1?IFRThread(p) 1THEN(qrp.RETURNq.)ELSE(FIO(rp.q).RETURNq.)ABDECFHIKGJL算法算法NIO*(t ,p .q)NIO*1.求中根序列末结点求中根序列末结点LIO(t.last).NIO*2.p last?IFp lastTHEN(q.RETURNq.)NIO*3.取取p之右指针之右指针 rpRight(p).NIO*4.RThread(p) 1?IFRThread(p) 1THEN(
28、qrp.RETURNq.)ELSE(FIO(rp.q).RETURNq.)在后序线索二叉树中，在后序线索二叉树中，查找结点查找结点p之后序前驱结点之后序前驱结点的主的主要思想如下：要思想如下：若结点若结点p是后序序列首结点，则是后序序列首结点，则p无后序前驱；无后序前驱；/*情况情况1*/若结点若结点p非后序序列首结点：非后序序列首结点：若若LThread(p) 1，则，则Left(p)指向指向p的后序前驱结点；的后序前驱结点；/*情况情况2，Left(p)为左线索为左线索*/若若LThread(p) 0，则：，则：/*此时此时p有左子树有左子树.后序遍历，后序遍历，p之后序前驱必是两子之后序
29、前驱必是两子树中最后被遍历的结点，情况树中最后被遍历的结点，情况3*/若若p有右子树有右子树，则，则p之右孩子是其后序前驱；之右孩子是其后序前驱；若若p无右子树无右子树，则，则p之后序前驱是其左孩子之后序前驱是其左孩子.3、查找后序前驱和后继结点、查找后序前驱和后继结点算法算法算法算法PPOPPO( (t t , ,p p. .q q) )PPO1.PPO1.求后序序列首结点求后序序列首结点求后序序列首结点求后序序列首结点 FPO(FPO(t t. .firstfirst)./*)./*算法算法算法算法FPOFPO求后序线索二叉树之后序序列首求后序线索二叉树之后序序列首求后序线索二叉树之后序序
30、列首求后序线索二叉树之后序序列首结点，请读者自行给出结点，请读者自行给出结点，请读者自行给出结点，请读者自行给出* */ /PPO2.PPO2.p p firstfirst?IFIFp p firstfirstTHEN(THEN(q q.RETURN.RETURNq q.)/*.)/*p p是后序序列的是后序序列的是后序序列的是后序序列的首结点，故首结点，故首结点，故首结点，故p p无前驱无前驱无前驱无前驱* */ /PPO3.PPO3.取取取取LeftLeft( (p p) ) lplpLeftLeft( (p p). ).PPO4.PPO4.LThreadLThread( (p p) )
31、1?1?IFIFLThreadLThread( (p p) ) 1THEN(1THEN(q qlplp.RETURN.RETURNq q.)/*.)/* lplp是左线索，是左线索，是左线索，是左线索，lplp指向指向指向指向p p之前驱之前驱之前驱之前驱* */ /PPO5.PPO5.RThreadRThread( (p p) ) 0?0?IFIFRThreadRThread( (p p) ) 0THEN(0THEN(rprpRightRight( (p p).).q qrprp.RETURN.RETURNq q .) .) ELSE(ELSE(q qlplp.RETURN.RETURNq
32、q.).)在后序线索二叉树在后序线索二叉树在后序线索二叉树在后序线索二叉树T T* *中，中，中，中，查找结点查找结点查找结点查找结点p p之后序后继之后序后继之后序后继之后序后继的主要思想如下：的主要思想如下：的主要思想如下：的主要思想如下：若若若若p p是根是根是根是根，则，则，则，则p p无后序后继无后序后继无后序后继无后序后继 /*/*情况情况情况情况1 1；对；对；对；对T T* *作后序遍历，作后序遍历，作后序遍历，作后序遍历，p p是最后被访是最后被访是最后被访是最后被访问的结点问的结点问的结点问的结点* */ /若若若若p p非根非根非根非根，则：，则：，则：，则：若若若若RT
33、hreadRThread( (p p) ) 1 1，则，则，则，则RightRight( (p p) )指向指向指向指向p p之后序后继结点之后序后继结点之后序后继结点之后序后继结点 /*/*情况情况情况情况2*/2*/若若若若RThreadRThread( (p p) ) 0 0，则：，则：，则：，则：/*/*此时此时此时此时p p之右子树非空，故需考虑之右子树非空，故需考虑之右子树非空，故需考虑之右子树非空，故需考虑p p之父结点；之父结点；之父结点；之父结点；情况情况情况情况3*/3*/若若若若p p是其父结点的右孩子是其父结点的右孩子是其父结点的右孩子是其父结点的右孩子，则，则，则，则
34、p p之后序后继就是其父结点；之后序后继就是其父结点；之后序后继就是其父结点；之后序后继就是其父结点；若若若若p p是其父结点的左孩子且是其父结点的左孩子且是其父结点的左孩子且是其父结点的左孩子且p p有右兄弟有右兄弟有右兄弟有右兄弟，则，则，则，则p p的后序后继是其父结点的后序后继是其父结点的后序后继是其父结点的后序后继是其父结点之右子树中后序遍历到的首结点；之右子树中后序遍历到的首结点；之右子树中后序遍历到的首结点；之右子树中后序遍历到的首结点；若若若若p p是其父结点的左孩子且是其父结点的左孩子且是其父结点的左孩子且是其父结点的左孩子且p p无右兄弟无右兄弟无右兄弟无右兄弟，则，则，则
35、，则p p的后序后继是其父结点的后序后继是其父结点的后序后继是其父结点的后序后继是其父结点. .T*为后序线索树，为后序线索树，p为为T*中之结点：中之结点：欲欲求求p之之后后序序前前驱驱，则则仅仅从从p出出发发就就能能找到。找到。若若要要找找p之之后后序序后后继继，则则仅仅当当p的的右右子子树树为为空空时时，才才能能由由p的的右右线线索索Right(p)得得到到；否否则则必必须须知知道道p的的父父结结点点，若若父父结结点点未知，则可能要从根开始遍历。未知，则可能要从根开始遍历。4、遍历线索二叉树、遍历线索二叉树算法思想：算法思想：算法思想：算法思想：欲欲欲欲对对对对X X序序序序（先先先先序
36、序序序、中中中中序序序序或或或或后后后后序序序序）线线线线索索索索二二二二叉叉叉叉树树树树进进进进行行行行X X序序序序遍遍遍遍历历历历，只只只只需需需需从从从从X X序序序序遍遍遍遍历历历历序序序序列列列列之之之之首首首首结结结结点点点点p p出出出出发发发发，找找找找p p的的的的X X序序序序后后后后继继继继q q，再再再再找找找找q q的的的的X X序序序序后后后后继继继继r r，如如如如此下去直至找到此下去直至找到此下去直至找到此下去直至找到X X序之末结点为止。序之末结点为止。序之末结点为止。序之末结点为止。 算法算法InOrder(t )/*t指向中序线索二叉树指向中序线索二叉树
37、T*之根，本算法中根遍之根，本算法中根遍历历T*/InOrder1.求中根序列首结点求中根序列首结点FIO(t.q).InOrder2.用用NIO*求求q之中序后继之中序后继WHILEq DO(PRINT(Data(q).NIO*(t,q.q).)该算法的时间复杂性为该算法的时间复杂性为O(n). 5、插插入入在在线线索索二二叉叉树树中中插插入入结结点点p作作为为结结点点s的右子结点的右子结点若若s无无右右子子树树:则则直直接接令令p成成为为s的的右右子子结结点点，并并修修改改s和和p的相关指针。的相关指针。p-Right=s-Right;p-RThread=s-RThread;p-Left=
38、s;p-LThread=1;s-Right=p;s-RThread=0;插入前插入前rightsprootrightlefts插入后插入后rootp若若s有右子树有右子树:将该右子树变成将该右子树变成p的右子树，的右子树，p成为成为s的右子结点，并修改的右子结点，并修改s和和p的相关指针以及该右的相关指针以及该右子树的最左下结点的前趋指针。子树的最左下结点的前趋指针。插入前插入前rootrightleftspright插入后插入后leftleftsprootp-Right=s-Right;p-RThread=s-RThread;p-Left=s;p-LThread=1;s-Right=p;q=
39、p-Right;FIO(q,p);q-Left=p;算法算法算法算法IR(IR(p p, ,s s) )/*/*插入结点插入结点插入结点插入结点p p作为中序线索二叉树作为中序线索二叉树作为中序线索二叉树作为中序线索二叉树T T* *之结点之结点之结点之结点s s的右子结点的右子结点的右子结点的右子结点* */ /IR1.IR1.p p之右指针指向之右指针指向之右指针指向之右指针指向s s右指针所指结点右指针所指结点右指针所指结点右指针所指结点 Right Right ( (p p) Right Right ( (s s).).RThreadRThread(p p ) ) RThreadRTh
40、read(s s).).IR2.IR2.p p的左指针指向的左指针指向的左指针指向的左指针指向s s LeftLeft( (p p) ) s s.LThreadLThread( (p p) )1.1.IR3.IR3.s s 无右子树？无右子树？无右子树？无右子树？ IFIFRThreadRThread(s s)=1THEN()=1THEN(RightRight( (s s) ) p p. .RThreadRThread( (s s) )0.0.RETURN.)/*RETURN.)/*p p成为成为成为成为s s的右子结点的右子结点的右子结点的右子结点* */ /ELSE(ELSE(q q Ri
41、ghtRight( (p p).).FIO(FIO(q q. .q q).).)IR4.IR4.p p分别送分别送分别送分别送q q的的的的LeftLeft和和和和s s的的的的RightRight域域域域 LeftLeft( (q q) ) p p. . RightRight( (s s) ) p p.6、删除结点s的右子结点p（假定p存在） 若若若若p p为叶子结点为叶子结点为叶子结点为叶子结点；若若若若p p无左子树，有右子树无左子树，有右子树无左子树，有右子树无左子树，有右子树若若若若p p无右子树，有左子树无右子树，有左子树无右子树，有左子树无右子树，有左子树若若若若p p既有左子树
42、，又有右子树既有左子树，又有右子树既有左子树，又有右子树既有左子树，又有右子树6、删除结点s的右子结点p（假定p存在）若若若若p p为叶子结点为叶子结点为叶子结点为叶子结点，只须修改只须修改只须修改只须修改s s的的的的RThreadRThread的值和的值和的值和的值和RightRight指针指针指针指针图图4.24删除结点删除结点s的右子结点的右子结点p（情形（情形1）rights删除后删除后rootrightlefts删除前删除前rootps-Right=p-Right;s-RThread=1;若若若若p p无左子树，有右子树无左子树，有右子树无左子树，有右子树无左子树，有右子树，且右子
43、树的中根序列的第一个结且右子树的中根序列的第一个结且右子树的中根序列的第一个结且右子树的中根序列的第一个结点为点为点为点为temptemp，则把，则把，则把，则把p p的右子树变成的右子树变成的右子树变成的右子树变成s s的右子树，并修改的右子树，并修改的右子树，并修改的右子树，并修改temptemp的的的的前趋指针前趋指针前趋指针前趋指针 s-Right=p-Right;temp-left=s;若若若若p p无无无无右右右右子子子子树树树树，有有有有左左左左子子子子树树树树，且且且且左左左左子子子子树树树树的的的的中中中中根根根根序序序序列列列列的的的的最最最最后后后后一一一一个个个个结结结
44、结点点点点为为为为temptemp，则则则则把把把把p p的的的的左左左左子子子子树树树树变变变变成成成成s s的的的的右右右右子子子子树树树树，并并并并修修修修改改改改temptemp的后继指针的后继指针的后继指针的后继指针. .图图4.26删除结点删除结点s的右子结点的右子结点p（情形（情形3）right删除前删除前rightleftprootstemprightleftrootstemp删除后删除后s-Right=p-Left;temp-Right=p-Right;若若若若p p既既既既有有有有左左左左子子子子树树树树，又又又又有有有有右右右右子子子子树树树树，temp1temp1为为为
45、为p p的的的的右右右右子子子子树树树树的的的的中中中中根根根根序序序序列列列列中中中中第第第第一一一一个个个个结结结结点点点点， temptemp为为为为p p的的的的左左左左子子子子树树树树的的的的中中中中根根根根序序序序列列列列中中中中最最最最后后后后一一一一个个个个结结结结点点点点，则把则把则把则把p p的左子树变成的左子树变成的左子树变成的左子树变成s s的右子树，的右子树，的右子树，的右子树，p p的右子树变成的右子树变成的右子树变成的右子树变成temptemp的右子树。的右子树。的右子树。的右子树。图图4.27删除结点删除结点s的右子结点的右子结点p（情形（情形4）prepretempsuccsucc删除前rootsptemp1presuccroots删除后temptemp1pretemp-Right=p-Right;temp-RThread=0;s-Right=p-Left;temp1-Left=temp;
