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

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*为为线索二叉树线索二叉树(ThreadedBinaryTree).v 指向指向指向指向某种遍历次序下的前驱和后继的某种遍历次序下的前驱和后继的指针指针指针指针称为称为线索线索线索线索；vv 为二叉树的每个结点为二叉树的每个结点为二叉树的每个结点为二叉树的每个结点加上线索，所得的二叉树称为加上线索，所得的二叉树称为线索二叉树线索二叉树；线索二叉树的线索二叉树的线索二叉树的线索二叉树的结点结构结点结构结点结构结点结构：按中序遍历得到的线索二叉树称为按中序遍历得到的线索二叉树称为中序线索二叉树中序线索二叉树中序线索二叉树中序线索二叉树；按先序遍历得到的线索二叉树称为按先序遍历得到的线索二叉树称为先序线索二叉树先序线索二叉树先序线索二叉树先序线索二叉树；按后序遍历得到的线索二叉树称为按后序遍历得到的线索二叉树称为后序线索二叉树后序线索二叉树后序线索二叉树后序线索二叉树。leftrightdatapredsucc 线索二叉树中有许多空指针，存储空间浪费问题未线索二叉树中有许多空指针，存储空间浪费问题未线索二叉树中有许多空指针，存储空间浪费问题未线索二叉树中有许多空指针，存储空间浪费问题未得到有效解决，由此得到改进方案：得到有效解决，由此得到改进方案：得到有效解决，由此得到改进方案：得到有效解决，由此得到改进方案：leftrightdataLThreadRThreadLThread=0,left域指向结点域指向结点t的左孩子的左孩子1,left域指向结点域指向结点t的中根前驱的中根前驱RThread=0,right域指域指向向结点结点t的右孩子的右孩子1,right域指域指向向结点结点t的中根后继的中根后继A00B10C11D01E11改进的中序线索二叉树的存储结构改进的中序线索二叉树的存储结构ACBED例例改进的中序线索二叉树改进的中序线索二叉树中根遍历序列：中根遍历序列：BCAED例：改进的后序线索二叉树例：改进的后序线索二叉树后根遍历序列：后根遍历序列：CBEDAA00B10C1 11D01E11（b b）改进的后序线索二叉树）改进的后序线索二叉树rootACBED（a a）二叉树）二叉树 线索二叉树的目的：线索二叉树的目的：在在中序线索二叉树中序线索二叉树中不需要对二叉树进行遍历可以方中不需要对二叉树进行遍历可以方便的找到给定结点的中序前趋和中序后继结点，并且便的找到给定结点的中序前趋和中序后继结点，并且不需要太多额外的空间。不需要太多额外的空间。线索二叉树中，一个结点是叶结点的充要条件为：左、线索二叉树中，一个结点是叶结点的充要条件为：左、右标志右标志(LThread、RThread)均是均是1。注意：注意：在在先序线索二叉树先序线索二叉树中找给定结点的中找给定结点的先序前驱先序前驱并非有效。并非有效。在在后序线索二叉树后序线索二叉树中找给定结点的中找给定结点的后序后继后序后继并非有效。并非有效。4.3线索二叉树线索二叉树4.3.1线索二叉树的定义线索二叉树的定义4.3.2线索二叉树基本算法线索二叉树基本算法n n给定一棵关于先根（中根、后根）遍历顺序的给定一棵关于先根（中根、后根）遍历顺序的给定一棵关于先根（中根、后根）遍历顺序的给定一棵关于先根（中根、后根）遍历顺序的线索二叉树，可作如下操作：线索二叉树，可作如下操作：线索二叉树，可作如下操作：线索二叉树，可作如下操作：求该二叉树在先根（中根、后根）遍历顺序求该二叉树在先根（中根、后根）遍历顺序求该二叉树在先根（中根、后根）遍历顺序求该二叉树在先根（中根、后根）遍历顺序 下的第一个和最后一个结点；下的第一个和最后一个结点；下的第一个和最后一个结点；下的第一个和最后一个结点；求任一结点在先根（中根、后根）遍历顺序求任一结点在先根（中根、后根）遍历顺序求任一结点在先根（中根、后根）遍历顺序求任一结点在先根（中根、后根）遍历顺序下的前驱和后继结点下的前驱和后继结点下的前驱和后继结点下的前驱和后继结点遍历线索二叉树遍历线索二叉树遍历线索二叉树遍历线索二叉树插入一个新结点插入一个新结点插入一个新结点插入一个新结点删除一个结点删除一个结点删除一个结点删除一个结点线索二叉树基本算法线索二叉树基本算法1)搜索以搜索以t为根的线索二叉树的中根序列的第一为根的线索二叉树的中根序列的第一个结点个结点算法思想：算法思想：从从二二叉叉树树根根结结点点出出发发，沿沿左左指指针针链链往往下下查查找找，直直至至找找到到一一个个没没有有左左孩孩子子的的结结点点为为止止，它它是是中中根遍历顺序下二叉树中第一个被访问的结点；根遍历顺序下二叉树中第一个被访问的结点；1、查找、查找中根序列的第一个和最后一个结点中根序列的第一个和最后一个结点搜索以搜索以t为根的线索二叉树的中根序列的第一个结点为根的线索二叉树的中根序列的第一个结点算法算法FIO(t.q)/*t指向中序线索二叉树指向中序线索二叉树T*之根，本算法返回之根，本算法返回T*的中根序列的中根序列的首结点，并用的首结点，并用q指向它指向它*/FIO1.初始化初始化 qt.FIO2.找中根遍历顺序下二叉树中第一个被访问的结点找中根遍历顺序下二叉树中第一个被访问的结点WHILELThread(q)0DOqLeft(q).RETURNq.while（q-LThread=0）q=q-Left;A00B10C11D01E11中序线索二叉树的存储结构中序线索二叉树的存储结构2)搜索以搜索以t为根的线索二叉树的中根序列的最为根的线索二叉树的中根序列的最后一个结点后一个结点算法思想：算法思想：即即从从二二叉叉树树根根结结点点出出发发，沿沿右右指指针针链链往往下下查查找找，直直至至找找到到一一个个没没有有右右孩孩子子的的结结点点为为止止，它它是是中中根根遍遍历历顺顺序序下下二二叉叉树树中中最最后后被被访访问问的的结点。结点。算法算法LIO(t.q)/*给定中序线索二叉树给定中序线索二叉树T*，t指向指向T*之根，本算法返回之根，本算法返回T*的中根序列末结点，并用的中根序列末结点，并用q指向它指向它*/LIO1.初始化初始化qt.LIO2.找中根遍历顺序下二叉树中最后被访问的结点找中根遍历顺序下二叉树中最后被访问的结点WHILERThread(q)0DOqRight(q).RETURNq.while（q-RThread=0）q=q-Right;A00B10C11D01E11中序线索二叉树的存储结构中序线索二叉树的存储结构1)在中序线索二叉树中，查找结点在中序线索二叉树中，查找结点p的中序的中序前驱结点的主要思想如下：前驱结点的主要思想如下：n n若结点若结点p是中根序列的第一个结点，则是中根序列的第一个结点，则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之左子之左子之左子之左子树中根序列的末结点树中根序列的末结点树中根序列的末结点树中根序列的末结点./*./*情况情况情况情况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之左指针之左指针之左指针之左指针 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.).)算法算法算法算法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 .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.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).).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).).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).).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).).RETURNRETURNq q.).)2)2)在中序线索二叉树中，找结点在中序线索二叉树中，找结点在中序线索二叉树中，找结点在中序线索二叉树中，找结点p p的中序后继结的中序后继结的中序后继结的中序后继