页数：53页文件大小：255.6 KB来源： 数据结构ppt课件
本课件围绕线索二叉树展开，说明利用空指针域保存前驱与后继信息的动机与结点结构，详细给出中序线索二叉树的构造、搜索前驱与后继、遍历等基本操作的实现，并讨论线索二叉树的插入与删除，以及先序线索树与后序线索树中结点的搜索。
4.1树的基本概念4.2二叉树4.3线索二叉树4.4树和森林4.5压缩与哈夫曼树4.6应用第四章树
在二叉树的应用中，我们经常根据需要，而附加或改造成另一种形式，从而更加便于解决相应的实际问题，或提高程序的空间和时间效率。线索二叉树就是二叉树的一种重要的改进。4.3线索二叉树
以Left/Right链接表示的二叉树结构，可看作是有很多从根结点一直到叶结点的单链表组成的，一个结点的前驱结点是其父结点，一个结点的后继结点是它的儿子结点。这种结构有两方面不足：其一是从一个结点只能访问它的儿子结点，而不能访问它的父结点；其二是这种结构通常包含很多未被有效使用的指针字段，譬如包含i个结点的二叉树，在其2i个指针域中仅有i-1个被使用.
通过遍历二叉树可得到结点的一个线性序列，在线性序列中，除第一个结点外，每个结点有且仅有一个前趋，除最后一个结点外，每个结点有且仅有一个后继，但是在二叉树上只能找到结点的左孩子、右孩子，结点在线性序列中的前趋和后继只有在遍历过程中才能得到。
如何快速找到给定结点在前（中、后）根下的前驱和后继？通过前（中、后）根遍历？加入新的指针。
4.3线索二叉树4.3.1线索二叉树的定义4.3.2线索二叉树基本算法
为使二叉树之结点的访问更方便，其空间的利用更高效.1960年，A.J.Perlis和C.Thornton提出了巧妙的线索二叉树表示，并给出了以各种顺序遍历线索二叉树的重要思想。但是A.J.Perlis和C.Thornton提出的只是单向的线索二叉树.1963年，A.W.Holt提出了双向线索二叉树。
为了同结点在二叉树中所具有的前驱（即父结点）和后继（即子结点）区别开来，通常把序列中的结点的前驱或后继冠以某种遍历的名称，如把中根序列中结点的前驱称作中根前驱，结点的后继称作中根后继。
定义4.6设T*是由增加某种遍历顺序之线索域的结点所构成的一棵二叉树，在T*中可直接查找任一结点在这种遍历顺序下的前驱和后继结点，则称T*为线索二叉树(ThreadedBinary Tree) .
指向某种遍历次序下的前驱和后继的指针称为线索；为二叉树的每个结点加上线索，所得的二叉树称为线索二叉树；线索二叉树的结点结构：按中序遍历得到的线索二叉树称为中序线索二叉树；按先序遍历得到的线索二叉树称为先序线索二叉树；按后序遍历得到的线索二叉树称为后序线索二叉树。leftrightdatapredsucc
例：中序线索二叉树中根遍历序列：B C A E D
例：后序线索二叉树后根遍历序列：C B E D A
线索二叉树中有许多空指针，存储空间浪费问题未得到有效解决，由此得到改进方案：leftrightdataLThreadRThreadLThread=0, left域指向结点t的左孩子1, left域指向结点t的中根前驱RThread=0, right域指向结点t的右孩子1, right域指向结点t的中根后继
A00B10C11D01E11∧∧中序线索二叉树的存储结构ACBED[例]改进的中序线索二叉树中根遍历序列：BC A E D
例：改进的后序线索二叉树后根遍历序列：C B E D A
线索二叉树的目的：在中序线索二叉树中不需要对二叉树进行遍历可以方便的找到给定结点的中序前趋和中序后继结点，并且不需要太多额外的空间。线索二叉树中，一个结点是叶结点的充要条件为：左、右标志(LThread、RThread)均是1。
4.3线索二叉树4.3.1线索二叉树的定义4.3.2线索二叉树基本算法
给定一棵关于先根（中根、后根）遍历顺序的线索二叉树，可作如下操作：——求该二叉树在先根（中根、后根）遍历顺序下的第一个和最后一个结点；——求任一结点在先根（中根、后根）遍历顺序下的前驱和后继结点——遍历线索二叉树——插入一个新结点——删除一个结点…线索二叉树基本算法
1)搜索以t为根的线索二叉树的中根序列的第一个结点算法思想：从二叉树根结点出发，沿左指针链往下查找，直至找到一个没有左孩子的结点为止，它是中根遍历顺序下二叉树中第一个被访问的结点；1、查找中根序列的第一个和最后一个结点
搜索以t为根的线索二叉树的中根序列的第一个结点算法FIO(t.q)FIO1. [初始化]q←t.FIO2.[找中根遍历顺序下二叉树中第一个被访问的结点]WHILELThread(q)=0 DOq←Left(q).RETURNq.▐
while（q-> LThread = = 0）q = q-> Left ;A00B10C11D01E11∧∧中序线索二叉树的存储结构
while（q-> LThread = = 0）q = q-> Left ;A10D01E11∧∧
2)搜索以t为根的线索二叉树的中根序列的最后一个结点算法思想：即从二叉树根结点出发，沿右指针链往下查找，直至找到一个没有右孩子的结点为止，它是中根遍历顺序下二叉树中最后被访问的结点。
算法LIO(t.q)LIO1. [初始化]q←t.LIO2.[找中根遍历顺序下二叉树中最后被访问的结点]WHILERThread(q)=0 DOq←Right(q) .RETURNq.▐
while（q-> RThread = = 0）q = q-> Right;A00B10C11D01E11∧∧中序线索二叉树的存储结构
1)在中序线索二叉树中，查找结点p的中序前驱结点的主要思想如下：若结点p是中根序列的第一个结点，则p无中序前驱结点；若结点p非中根序列的第一个结点：–若LThread(p)=1，则Left(p)为左线索，直接指向p的中序前驱结点；–若LThread(p)=0，p的中序前驱结点是p之左子树中根序列的末结点. 2、查找中序前驱结点和中序后继结点
算法PIO(t,p.q)PIO1. [求T*之中根序列首结点]FIO(t.first).PIO2. [p=first？]IFp=firstTHEN (q← . RETURNq.)PIO3. [取p之左指针]lp←Left(p) .PIO4. [LThread(p)=1?]IFLThread(p)=1THEN (q←lp. RETURNq.)ELSE (LIO(lp.q).RETURNq.) ▐
PIO1. [求T*之中根序列首结点]FIO(t.first).PIO2. [p=first？]IFp=firstTHEN (q← .RETURNq.)PIO3. [取p之左指针]lp←Left(p) .PIO4. [LThread(p)=1?]IFLThread(p)=1 THEN (q←lp. RETURNq.) ELSE(LIO(lp.q). RETURNq.) ▐ABDECFHIKGJL
ABDECFHIKGJLPIO1. [求T*之中根序列首结点]FIO(t.first).PIO2. [p=first？]IFp=firstTHEN (q← .RETURNq.)PIO3. [取p之左指针]lp←Left(p) .PIO4. [LThread(p)=1?]IFLThread(p)=1 THEN (q←lp. RETURNq.)ELSE (LIO(lp.q).RETURNq.) ▐
ABDECFHIKGJLPIO1. [求T*之中根序列首结点]FIO(t.first).PIO2. [p=first？]IFp=firstTHEN (q← .RETURNq.)PIO3. [取p之左指针]lp←Left(p) .PIO4. [LThread(p)=1?]IFLThread(p)=1 THEN (q←lp. RETURNq.)ELSE (LIO(lp.q).RETURNq.)▐
2)在中序线索二叉树中，找结点p的中序后继结点的主要思想如下：若结点p是中序序列的末结点，则其无后继结点；若结点p非中序序列的末结点：—若RThread(p)=1，则Right(p)指向p之中序后继—若RThread(p)=0，则p之中序后继为p的右子树的中根序列的首结点。
算法NIO* (t,p.q)NIO*1. [求中根序列末结点]LIO (t.last).NIO*2. [p=last? ]IFp=lastTHEN (q← . RETURNq. )NIO*3. [取p之右指针]rp←Right(p) .NIO*4. [RThread(p)=1?]IFRThread(p)=1THEN (q←rp. 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之右指针]rp←Right(p) .NIO*4. [RThread(p)=1?]IFRThread(p)=1 THEN(q←rp. 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之右指针]rp←Right(p) .NIO*4. [RThread(p)=1?]IFRThread(p)=1 THEN(q←rp. 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之右指针]rp←Right(p) .NIO*4. [RThread(p)=1?]IFRThread(p)=1 THEN(q←rp. RETURNq.)ELSE ( FIO(rp.q).RETURNq.)▐
4、遍历线索二叉树算法思想：欲对X序（先序、中序或后序）线索二叉树进行X序遍历，只需从X序遍历序列之首结点p出发，找p的X序后继q，再找q的X序后继r，如此下去直至找到X序之末结点为止。
算法InOrder(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的相关指针。
若s有右子树:将该右子树变成p的右子树，p成为s的右子结点，并修改s和p的相关指针以及该右子树的最左下结点的前趋指针。
插入前rootrightleftspright插入后leftleftsproot①p->Right=s->Right;②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)IR1. [p之右指针指向s右指针所指结点]Right(p)←Right(s) .RThread(p)←RThread(s) .IR2. [p的左指针指向s]Left(p)←s.LThread(p)←1 .IR3. [s无右子树？]IFRThread(s) = 1 THEN (Right(s)←p.RThread(s)←0.RETURN . ) 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）rights删除后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->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;
二叉树T*先根序列第一个结点和后根序列最后一个结点都是树的根结点。先根序列的最后一个结点则分两种情况：⑴若T*根结点存在右子树，则其右子树先根序列的最后一个结点就是整棵二叉树先根序列的最后一个结点；⑵若T*之根结点不存在右子树，但T*之根结点存在左子树，则其左子树先根序列最后一个结点就是T*先根序列的最后一个结点。
二叉树T*后根序列第一个结点也存在两种情况：⑴若T*之根结点存在左子树，则其左子树后根序列第一个结点就是T*之后根序列的第一个结点；⑵若T*无左子树，但T*之根结点存在右子树，则其右子树后根序列第一个结点就是T*之后根序列的第一个结点。
在后序线索二叉树中，查找结点p之后序前驱结点的主要思想如下：若结点p是后序序列首结点，则p无后序前驱；若结点p非后序序列首结点：—若LThread(p)=1，则Left(p)指向p的后序前驱结点；—若LThread(p)=0，则：若p有右子树，则p之右孩子是其后序前驱；
若p无右子树，则p之后序前驱是其左孩子.3、查找后序前驱和后继结点
算法PPO(t,p.q)PPO1. [求后序序列首结点]FPO(t.first). PPO2. [p=first? ]IFp=firstTHEN (q← . RETURNq.) PPO3. [取Left(p)]lp←Left(p).PPO4. [LThread(p)=1?]IFLThread(p)=1 THEN (q←lp. RETURNq.) PPO5. [RThread(p)=0 ?]IFRThread(p)=0 THEN (rp←Right(p) .q←rp. RETURNq.)ELSE (q←lp. RETURNq.)▐
在后序线索二叉树T*中，查找结点p之后序后继的主要思想如下：若p是根，则p无后序后继若p非根，则：若RThread(p)=1，则Right(p)指向p之后序后继结点若RThread(p)=0，则：若p是其父结点的右孩子，则p之后序后继就是其父结点；若p是其父结点的左孩子且p有右兄弟，则p的后序后继是其父结点之右子树中后序遍历到的首结点；若p是其父结点的左孩子且p无右兄弟，则p的后序后继是其父结点.
T*为后序线索树，p为T*中之结点：——欲求p之后序前驱，则仅从p出发就能找到。——若要找p之后序后继，则仅当p的右子树为空时，才能由p的右线索Right(p)得到；否则必须知道p的父结点，若父结点未知，则可能要从根开始遍历；由此，在后序线索二叉树中查找给定结点之后序后继并不总是有效的。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}