數(shù)據(jù)結(jié)構(gòu)課件：第6章 樹(shù)和二叉樹(shù)2遍歷二叉樹(shù)和線索二叉樹(shù)

1、樹(shù)和森林第第6 6章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)的基本概念二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)赫夫曼樹(shù)及其應(yīng)用v提出提出問(wèn)題問(wèn)題6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 在二叉樹(shù)的一些應(yīng)用中，常要求在樹(shù)中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)樹(shù)中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。這就提出了遍歷二叉樹(shù)的問(wèn)題。v遍歷遍歷是是任何類(lèi)型均有的操作任何類(lèi)型均有的操作6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)； 而二叉樹(shù)是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷，即按什么樣的搜索路徑遍歷的問(wèn)題。v遍歷遍歷二叉樹(shù)二叉樹(shù)6.3 遍歷二叉樹(shù)和線索

2、二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 對(duì)二叉樹(shù)而言，是由三個(gè)基本單元組成：根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。 因此，若能遍歷這三部分，便是遍歷了整個(gè)二叉樹(shù)?？紤]：一共有多少種遍歷 二叉樹(shù)的方案？v遍歷遍歷二叉樹(shù)二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 假如以 L、D、R 分別表示遍歷二叉樹(shù)的左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)，則有 D L R 、L D R 、L R D D R L 、R D L 、R L D 先序 中序 后序 六種遍歷方案選擇v先先左后右的遍歷算法左后右的遍歷算法6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 先（根）序遍歷算法 DLR 中（根）序遍歷算法 LDR 后（根）

3、序遍歷算法 LRDv先先（根）序遍歷算法（根）序遍歷算法6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)若二叉樹(shù)為空樹(shù)，則空操作；否則(1) 訪問(wèn)根結(jié)點(diǎn)；(2) 先序遍歷左子樹(shù)；(3) 先序遍歷右子樹(shù)。void PreOrderTraverse(BiTree bt) if(bt) printf(%c , bt-data); /*輸出根結(jié)點(diǎn)數(shù)據(jù)域的值*/ PreOrderTraverse(bt-lchild); /*先序遍歷左子樹(shù)*/ PreOrderTraverse(bt-rchild); /*先序遍歷右子樹(shù)*/ v中中（根）序遍歷算法（根）序遍歷算法6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉

4、樹(shù)和線索二叉樹(shù)若二叉樹(shù)為空樹(shù)，則空操作；否則(1) 中序遍歷左子樹(shù)；(2) 訪問(wèn)根結(jié)點(diǎn)；(3) 中序遍歷右子樹(shù)。void InOrderTraverse(BiTree bt) if(bt) InOrderTraverse(bt-lchild); /*中序遍歷左子樹(shù)*/ printf(%c , bt-data); /*輸出根結(jié)點(diǎn)數(shù)據(jù)域的值*/ InOrderTraverse(bt-rchild); /*中序遍歷右子樹(shù)*/ v后后（根）序遍歷算法（根）序遍歷算法6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)若二叉樹(shù)為空樹(shù)，則空操作；否則(1) 后序遍歷左子樹(shù)；(2) 后序遍歷右子樹(shù)；(3)

5、訪問(wèn)根結(jié)點(diǎn)。void PostOrderTraverse(BiTree bt) if(bt) PostOrderTraverse(bt-lchild); /*后序遍歷左子樹(shù)*/ PostOrderTraverse(bt-rchild); /*后序遍歷右子樹(shù)*/ printf(%c , bt-data); /*輸出根結(jié)點(diǎn)數(shù)據(jù)域的值*/ v例例16.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是： A B CD EA B D E CD B E A CD E B C A口訣：DLR先序遍歷，即先根再左再右LDR中序遍歷，即先左再根再右LRD后序遍

6、歷，即先左再右再根v例例2：用二叉樹(shù)表示算術(shù)表達(dá)式：用二叉樹(shù)表示算術(shù)表達(dá)式6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)+*A*/EDCB先序遍歷+ * * / A B C D E前綴表示中序遍歷A / B * C * D + E中綴表示后序遍歷A B / C * D * E +后綴表示層序遍歷+ * E * D / C A Bv例例36.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 假設(shè)一棵二叉樹(shù)的先序序列為 E B A D C F H G I K J，中序序列為 A B C D E F G H I J K。畫(huà)出該二叉樹(shù)。v遍歷算法遍歷算法的的遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)6.3 遍歷二叉樹(shù)和線

7、索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)回憶1：二叉樹(shù)結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型定義：typedef struct node *tree_pointer;typedef struct node int data; tree_pointer left_child, right_child; node;回憶2：遞歸求解 n!long int fact(n) /求n! long s; if (n1) s=n*fact(n-1); else f=1; return(f); v先先序遍歷二叉樹(shù)的遞歸算法序遍歷二叉樹(shù)的遞歸算法6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)Status PreOrderTraverse(B

8、iTree T,Status(* Visit)(TElemType e)/二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/先序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用visit if(T) if (Visit(T-data) if ( PreOrderTraverse(T-lchild,Visit ) if (PreOrderTraverser(T-rchild,Visit) return OK; return ERROR; else return OK;PreOrderTraverseACBD主主程程序序Pre( T )Pre(T R);Pre(T R);TAVisit(A);Pr

9、e(T L);TDVisit(D);Pre(T L);TCVisit(C);Pre(T L);TBVisit(B);Pre(T L);返回返回TPre(T R);返回返回T返回返回T返回返回T返回返回TPre(T R);得到的遍歷次序?yàn)椋篈 B D CPreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)if(T) if (Visit(T-data) if ( PreOrderTraverse(T-lchild,Visit ) if (PreOrderTraverser(T-rchild,Visit) return OK; return E

10、RROR; else return OK;v中中序遍歷二叉樹(shù)的遞歸算法序遍歷二叉樹(shù)的遞歸算法6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if(T) if ( InOrderTraverse(T-lchild,Visit) ) if (Visit(T-data) if ( InOrderTraverse(T-rchild,Visit) ) return OK; return ERROR; else return OK; / InOrderTraversev后序后序遍

11、歷二叉樹(shù)的遞歸算法遍歷二叉樹(shù)的遞歸算法6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)Status PostOrderTraverse(BiTree T ,Status(* Visit)(TElemType e) if(T) if ( PostOrderTraverse(T-lchild ,Visit) ) if ( PostOrderTraverse(T-rchild ,Visit) ) if (Visit(T-data) return OK; return ERROR; else return OK; /PostOrderTraversev遍歷遍歷的分析的分析6.3 遍歷二叉樹(shù)和線索二

12、叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)1. 從前面的三種遍歷算法可以知道：如果將print語(yǔ)句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說(shuō)這三種遍歷算法的訪問(wèn)路徑是相同的，只是訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的起點(diǎn)到終點(diǎn)，每個(gè)結(jié)點(diǎn)經(jīng)過(guò)3次AFEDCBG第1次經(jīng)過(guò)時(shí)訪問(wèn)先序遍歷第2次經(jīng)過(guò)時(shí)訪問(wèn)中序遍歷第3次經(jīng)過(guò)時(shí)訪問(wèn)后序遍歷2. 二叉樹(shù)遍歷的時(shí)間效率和空間效率時(shí)間效率: /每個(gè)結(jié)點(diǎn)只訪問(wèn)一次空間效率: /棧占用的最大輔助空間v中中序遍歷二叉樹(shù)的非遞歸算法一序遍歷二叉樹(shù)的非遞歸算法一6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)Staus InOrderTrav(BiTree T,Status(* V

13、isit)(TElemType e)/中序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit.InitStack(S); Push(S,T); /根指針進(jìn)棧while(!StackEmpty(S) while(GetTop(S,p)&p) Push(S,p-lchild);/向左走到盡頭 Pop(S,p); /空指針退棧 if(!StackEmpty(S) /訪問(wèn)結(jié)點(diǎn)，向右一步 Pop(S,p); if(!Visit(p-data) return error; Push(S,p-rchild); /if /whileReturn ok; /InOrderTraverseACBEDv中中

14、序遍歷二叉樹(shù)的非遞歸序遍歷二叉樹(shù)的非遞歸算法二算法二6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)Status InOrderTrv( BiTree T,Status (*Visit)(TElemType e)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)/中序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。 InitStack(S); p=T; while(p | !StackEmpty(S) if (p) Push(&S,p); p=p-lchild; else Pop(&S,&p); if (!Visit(p-data) return ERROR； p=p

15、-rchild; /else /while return OK; /InOrderTrv/根指針進(jìn)棧，遍歷左子樹(shù)/根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù) ACBEDv遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) “遍歷”是二叉樹(shù)各種操作的基礎(chǔ)，可以在遍歷過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作，如：對(duì)于一棵已知樹(shù)求結(jié)點(diǎn)的雙親，求結(jié)點(diǎn)的孩子結(jié)點(diǎn)，判定結(jié)點(diǎn)所在的層次等。v例例1：統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)：統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)Status CountLeaf (BiTree T, int & count) if (

16、T ) if ( (T-lchild =NULL) & (T-rchild =NULL) count + +; return OK; CountLeaf( T - lchild, count); / 統(tǒng)計(jì)左子樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù) CountLeaf( T - rchild, count); / 統(tǒng)計(jì)右子樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù) else return ERROR; v例例2：求二叉樹(shù)的深度：求二叉樹(shù)的深度6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft = Depth( T-lchi

17、ld ); depthRight= Depth( T-rchild ); depthval = 1 + max(depthLeft,depthRight); return depthval;v例例3：按先序序列建立二叉樹(shù)的二叉鏈表：按先序序列建立二叉樹(shù)的二叉鏈表6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)已知先序序列：A B C 0 0 D E 0 G 0 0 F 0 0 0（其中0表示空格字符, 空指針）建立相應(yīng)的二叉鏈表ABCDEFGv例例3：按先序序列建立二叉樹(shù)的二叉鏈表：按先序序列建立二叉樹(shù)的二叉鏈表6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)Status Create

18、BiTree (BiTree &T) /按先序序列輸入二叉樹(shù)中結(jié)點(diǎn)的值，空格字符表示空樹(shù) Scanf(&ch) if (ch = = ) T=NULL; else if( !( T=(BiTNode*)malloc(sizeof(BiTNode) ) ) exit(OVERFLOW); T-data = ch; /構(gòu)造根結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子樹(shù) CreateBiTree(T-rchild); /構(gòu)造右子樹(shù) Return OKv線索二叉樹(shù)線索二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)AEBCDFGHKv線索二叉樹(shù)線索二叉樹(shù)6.3 遍歷二叉

19、樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)lchildDaterchildABECFDGHKv線索二叉樹(shù)線索二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)普通二叉樹(shù)只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過(guò)程中獲得。若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來(lái)，則從第一個(gè)結(jié)點(diǎn)開(kāi)始就能很快“順藤摸瓜”而遍歷整個(gè)樹(shù)了。v線索二叉樹(shù)線索二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)例如中序遍歷結(jié)果：B D C A E H G K F，實(shí)際上已將二叉樹(shù)轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼。v線索二叉樹(shù)線索二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉

20、樹(shù)ABECFDGHKv線索二叉樹(shù)線索二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)兩種解決方法：增加兩個(gè)域：fwd和bwd；存放前驅(qū)指針存放后繼指針如何預(yù)存這類(lèi)信息？(唯一前驅(qū)和唯一后繼)利用空鏈域（n+1個(gè)空鏈域）v線索二叉樹(shù)線索二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)問(wèn)：用二叉鏈表法（l_child, r_child）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針？分析：用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)必有2n個(gè)鏈域（見(jiàn)二叉鏈表數(shù)據(jù)類(lèi)型說(shuō)明）。 除根結(jié)點(diǎn)外，二叉樹(shù)中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親（直接前驅(qū)），所以只會(huì)有n1個(gè)結(jié)點(diǎn)的鏈域存放指針，

21、指向非空子女結(jié)點(diǎn)（即直接后繼）。所以，空指針數(shù)目2n(n1)n+1個(gè)v線索二叉樹(shù)線索二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？我們可以用它來(lái)存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。規(guī)定：1）若結(jié)點(diǎn)有左子樹(shù)，則lchild指向其左孩子； 否則， lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹(shù)，則rchild指向其右孩子； 否則， rchild指向其直接后繼(即線索) 。為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域（各1bit）lchilddatarchild約定:當(dāng)Tag域?yàn)?時(shí),表示正常情況;當(dāng)

22、Tag域?yàn)?時(shí),表示線索情況.右孩子或后繼左孩子或前驅(qū)LTagRTagv二叉樹(shù)二叉線索存儲(chǔ)表示二叉樹(shù)二叉線索存儲(chǔ)表示6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索typedef struct BiThrNode TElemType data; Struct BiThrNode *lchild, *rchild; / 左右孩子指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;v有關(guān)線索二叉樹(shù)的幾個(gè)術(shù)語(yǔ)有關(guān)線索二

23、叉樹(shù)的幾個(gè)術(shù)語(yǔ)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 線索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹(shù)：加上線索的二叉樹(shù) 線索鏈表：用含Tag的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表 線索化：對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程討論：增加了前驅(qū)和后繼等線索有什么好處？能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用堆棧也能遍歷整個(gè)樹(shù)。ABCGEIDHFNILNIL解：該二叉樹(shù)中序遍歷結(jié)果為: H, D, I, B, E, A, F, C, G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：例1：畫(huà)出以下二叉樹(shù)對(duì)應(yīng)的中序線索二叉樹(shù)。例2：【 2000年計(jì)算機(jī)系考研題】給定如圖所示二叉樹(shù)T，請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線索二叉樹(shù)。

24、 2825405560330854解:因?yàn)橹行虮闅v序列是：55 40 25 60 28 08 33 54對(duì)應(yīng)線索樹(shù)應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹(shù)中添加虛線NILNILAEBCDFGHK例3：畫(huà)出以下二叉樹(shù)對(duì)應(yīng)的中序線索二叉樹(shù)。解：該二叉樹(shù)中序遍歷結(jié)果為: B, D, C, A, E, H, G, K, F所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：NILNILv線索二叉樹(shù)的生成線索二叉樹(shù)的生成6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)線索化過(guò)程就是在遍歷過(guò)程中修改空指針的過(guò)程：將空的 lchild 改為結(jié)點(diǎn)的直接前驅(qū)；將空的 rchild 改為結(jié)點(diǎn)的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱(chēng)為“

25、正常情況”）AEBCDFGHK例3：畫(huà)出以下二叉樹(shù)對(duì)應(yīng)的中序線索二叉樹(shù)。解：該二叉樹(shù)中序遍歷結(jié)果為: B, D, C, A, E, H, G, K, F所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：NILNIL懸空？懸空？為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)01對(duì)應(yīng)的中序線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)如圖所示該二叉樹(shù)中序遍歷結(jié)果為: B, D, C, A, E, H, G, K, Froot0A01B01E00C10F11D10G01H11K1v如何在線索樹(shù)中找結(jié)點(diǎn)的后繼如何在線索樹(shù)中找結(jié)點(diǎn)的后繼6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)結(jié)合中序線索樹(shù) 若其右標(biāo)志為“1”，右鏈?zhǔn)蔷€索，右鏈直接指示結(jié)點(diǎn)后繼； 若其右

26、標(biāo)志為“0”，右鏈?zhǔn)侵羔?，其后繼為右子樹(shù)中最左下的結(jié)點(diǎn)。1234567v如何在線索樹(shù)中找結(jié)點(diǎn)的前驅(qū)如何在線索樹(shù)中找結(jié)點(diǎn)的前驅(qū)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)結(jié)合中序線索樹(shù) 若其左標(biāo)志為“1”，左鏈為線索，左鏈直接指示其前驅(qū)； 若其左標(biāo)志為“0”，左鏈?zhǔn)侵羔?，否則左子樹(shù)中最右下的結(jié)點(diǎn)為其前驅(qū)。1234567線索鏈表的中序遍歷算法Status IOTraver_T( BiThrTree T,Status (*Visit)(TElemType e) ) /T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，中序遍歷 /二叉線索樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。 p

27、 = T-lchild; /p指向根結(jié)點(diǎn) while (p != T) /空樹(shù)或遍歷結(jié)束時(shí)，p = = T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; /訪問(wèn)其左子樹(shù)為空的結(jié)點(diǎn) while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); /訪問(wèn)后繼結(jié)點(diǎn) p = p-rchild; return OK; / IOTraver_T線索二叉樹(shù)的生成算法（算法6.6, 見(jiàn)教材P134）目的：在依某種順序遍歷二叉樹(shù)時(shí)修改空指針，添加前驅(qū)或后繼注解：為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個(gè)指針： p指針當(dāng)前結(jié)點(diǎn)之指針； pre指針前驅(qū)結(jié)點(diǎn)之指針。技巧：當(dāng)結(jié)點(diǎn)p的左/右域?yàn)榭諘r(shí)，只改寫(xiě)它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點(diǎn)來(lái)填寫(xiě)。 或者說(shuō)，當(dāng)前結(jié)點(diǎn)的指針p應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。若p-lchildNULL,則p-Ltag=1; p-lchildpre; /p的前驅(qū)結(jié)點(diǎn)指針pre存入左空域若pre-rchildNULL, 則pre-Rtag1; pre-rchild=p; /p存入其前驅(qū)結(jié)點(diǎn)pre的右空域D0