數(shù)據(jù)結(jié)構(gòu) 第6章 圖

1、16.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹一、遍歷二叉樹遍歷二叉樹（Traversing Binary Tree）遍歷定義遍歷定義指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游）。不重復(fù)（又稱周游）。遍歷用途遍歷用途它是樹結(jié)構(gòu)插入、刪除、修改、查它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。切運(yùn)算的基礎(chǔ)和核心。 遍歷方法遍歷方法牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看都是都是“先左后右先左后右” 。2遍歷規(guī)則遍歷規(guī)則v二叉樹由根、左子樹、右子樹構(gòu)成，定義為二叉樹

2、由根、左子樹、右子樹構(gòu)成，定義為D、 L、RvD、 L、R的組合定義了六種可能的遍歷方案：的組合定義了六種可能的遍歷方案： LDR, LRD, DLR, DRL, RDL, RLDv若限定先左后右若限定先左后右，則有三種實(shí)現(xiàn)方案：，則有三種實(shí)現(xiàn)方案： DLR LDR LRD先先 (根根)序遍歷序遍歷 中中 (根根)序遍歷序遍歷 后后(根根)序遍歷序遍歷 注：注：“先、中、后先、中、后”的意思是指訪問的結(jié)點(diǎn)的意思是指訪問的結(jié)點(diǎn)D是先于子樹是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。出現(xiàn)還是后于子樹出現(xiàn)。3例例1：先序遍歷的結(jié)果是：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：后序遍

3、歷的結(jié)果是： A B CD E口訣：口訣：DLR先序遍歷，即先序遍歷，即先根再左再右先根再左再右LDR中序遍歷，即先左再根再右中序遍歷，即先左再根再右LRD后序遍歷，即先左再右再根后序遍歷，即先左再右再根4+*A*/EDCB先序遍歷先序遍歷+ * * / A B C D E前綴表示前綴表示中序遍歷中序遍歷A / B * C * D + E中綴表示中綴表示后序遍歷后序遍歷A B / C * D * E +后綴表示后綴表示層序遍歷層序遍歷+ * E * D / C A B例例2：用二叉樹表示算術(shù)表達(dá)式用二叉樹表示算術(shù)表達(dá)式5遍歷的算法實(shí)現(xiàn)：遍歷的算法實(shí)現(xiàn)：用遞歸形式格外簡(jiǎn)單！用遞歸形式格外簡(jiǎn)單！回

4、憶回憶1 1：二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義：二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義：typedef struct node *tree_pointer;typedef struct node int data; tree_pointer left_child, right_child; node;則三種遍歷算法可寫出則三種遍歷算法可寫出: :回憶回憶2：第第1章自測(cè)卷章自測(cè)卷4.2題：題：long int fact(n) /求求n! int n; long f; if(n1)f=n*fact(n-1); else f=1; return(f); 6先序遍歷算法先序遍歷算法DLR( liuyu *root )if

5、 (root !=NULL) /非空二叉樹非空二叉樹 printf(“%d”,root-data); /訪問訪問D DDLR(root-lchild); /遞歸遍歷左子樹遞歸遍歷左子樹DLR(root-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 中序遍歷算法中序遍歷算法LDR(x*root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);后序遍歷算法后序遍歷算法LRD (x*root)if(root !=NULL) LRD(root-lchil

6、d); LRD(root-rchild); printf(“%d”,root-data); return(0);結(jié)點(diǎn)數(shù)據(jù)類型自定義結(jié)點(diǎn)數(shù)據(jù)類型自定義typedef struct liuyuint data; struct liuyu *lchild,*rchild； liuyu;liuyu *root; 7對(duì)遍歷的分析：對(duì)遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將print語句抹去，語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的

7、時(shí)機(jī)不同訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過上，每個(gè)結(jié)點(diǎn)經(jīng)過3次次。AFEDCBG第第1次次經(jīng)過時(shí)訪問經(jīng)過時(shí)訪問先序先序遍歷遍歷第第2次次經(jīng)過時(shí)訪問經(jīng)過時(shí)訪問中序中序遍歷遍歷第第3次次經(jīng)過時(shí)訪問經(jīng)過時(shí)訪問后序后序遍歷遍歷2. 2. 二叉樹遍歷的時(shí)間效率和空間效率二叉樹遍歷的時(shí)間效率和空間效率時(shí)間效率時(shí)間效率: : /每個(gè)結(jié)點(diǎn)只訪問一次每個(gè)結(jié)點(diǎn)只訪問一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間（精確值：樹深為（精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個(gè)輔助單元！）個(gè)輔助單元?。?/p>

8、8例：例：【嚴(yán)題集【嚴(yán)題集6.42】編寫遞歸算法，計(jì)算二叉樹編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。中葉子結(jié)點(diǎn)的數(shù)目。 思路：思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷算法，凡輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來。是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來。 DLR(liuyu *root) /采用中序遍歷的遞歸算法采用中序遍歷的遞歸算法 if ( root!=NULL ) /非空二叉樹條件，還可寫成非空二叉樹條件，還可寫成if(root)if(root) if(!root-lchild&!root-rchild) /是葉子結(jié)點(diǎn)則統(tǒng)計(jì)

9、并打印是葉子結(jié)點(diǎn)則統(tǒng)計(jì)并打印 sum+; printf(%dn,root-data); DLR(root-lchild); /遞歸遍歷左子樹，直到葉子處；遞歸遍歷左子樹，直到葉子處； DLR(root-rchild); /遞歸遍歷右子樹，直到葉子處；遞歸遍歷右子樹，直到葉子處； return(0); 9注：要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹存入機(jī)內(nèi)。注：要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹存入機(jī)內(nèi)。思路：思路：利用利用前序前序遍歷來建樹遍歷來建樹 （結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用（結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用DLR為宜為宜）Bintree createBTpre( ) Bintree T; char ch;scanf

10、(“%c”,&ch);if(ch=)T=NULL; elseT=( Bintree )malloc(sizeof(BinTNode);T-data=ch;T-lchild=createBTpre();T-rchild=createBTpre(); return T;怎樣建樹？見教材怎樣建樹？見教材P131P131程序。程序。10習(xí)題討論：習(xí)題討論： 算法思路：算法思路：只查各結(jié)點(diǎn)后繼鏈表指針，若左只查各結(jié)點(diǎn)后繼鏈表指針，若左( (右右) )孩子的左孩子的左( (右右) )指針非空，則層次數(shù)加指針非空，則層次數(shù)加1 1；否則函數(shù)返回。；否則函數(shù)返回。技巧：技巧：遞歸時(shí)應(yīng)當(dāng)遞歸時(shí)應(yīng)當(dāng)從葉子開始向上

11、計(jì)數(shù)，層深者保留。從葉子開始向上計(jì)數(shù)，層深者保留。否則否則不易確定層數(shù)。不易確定層數(shù)。 算法思路：算法思路：既然要求從上到下，從左到右，則既然要求從上到下，從左到右，則利用隊(duì)列利用隊(duì)列存放存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法，而不必拘泥于遞歸算法。各子樹結(jié)點(diǎn)的指針是個(gè)好辦法，而不必拘泥于遞歸算法。技巧：技巧：當(dāng)根結(jié)點(diǎn)入隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩當(dāng)根結(jié)點(diǎn)入隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì)，子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì)，由此便可產(chǎn)生按由此便可產(chǎn)生按層次輸出的效果。層次輸出的效果。 A B CD E11算法思路：算法思路：若不用遞歸，則要實(shí)現(xiàn)二叉樹遍歷的若

12、不用遞歸，則要實(shí)現(xiàn)二叉樹遍歷的“嵌套嵌套”規(guī)規(guī)則，必用堆棧?？芍苯佑脛t，必用堆棧?？芍苯佑脀hilewhile語句和語句和push/poppush/pop操作。操作。參見教參見教材材P130-131P130-131程序。程序。 算法思路：算法思路：完全二叉樹的特點(diǎn)是：沒有左子樹空而右子樹單完全二叉樹的特點(diǎn)是：沒有左子樹空而右子樹單獨(dú)存在的情況獨(dú)存在的情況( (前前k-1k-1層都是滿的，且第層都是滿的，且第k k層左邊也滿）層左邊也滿）。技巧技巧: :按層序遍歷方式，先把所有結(jié)點(diǎn)按層序遍歷方式，先把所有結(jié)點(diǎn)（不管當(dāng)前結(jié)點(diǎn)是否有（不管當(dāng)前結(jié)點(diǎn)是否有左右孩子）左右孩子）都入隊(duì)列都入隊(duì)列. .若為完

13、全二叉樹若為完全二叉樹, ,則層序遍歷時(shí)得到的則層序遍歷時(shí)得到的肯定是一個(gè)連續(xù)的不包含空指針的序列肯定是一個(gè)連續(xù)的不包含空指針的序列. .如果序列中出現(xiàn)了空如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。指針，則說明不是完全二叉樹。12【嚴(yán)題集【嚴(yán)題集6.31】 證明：由一棵二叉樹的先序序列和中序證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。序列可唯一確定這棵二叉樹。 例：例：已知一棵二叉樹的已知一棵二叉樹的中序序列中序序列和和后序序列后序序列分別是分別是BDCEAFHG 和和 DECBHGFA，請(qǐng)畫出這棵二叉樹。，請(qǐng)畫出這棵二叉樹。分析：分析：由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾

14、部由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即（即A A）；由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹子孫左子樹子孫（即（即BDCEBDCE），其右部必全部是右子樹子孫，其右部必全部是右子樹子孫（即（即FHGFHG）；繼而，根據(jù)后序中的繼而，根據(jù)后序中的DECBDECB子樹可確定子樹可確定B B為為A A的左孩子，根據(jù)的左孩子，根據(jù)HGFHGF子串可確定子串可確定F F為為A A的右孩子；以此類推。的右孩子；以此類推。13中序遍歷：中序遍歷：B D C E A F H G后序遍歷：后序遍歷：D E C B H G F A（B D

15、 C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF14問：?jiǎn)枺河枚骀湵矸ǎㄓ枚骀湵矸ǎ╨_child, r_child）存儲(chǔ)包含）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針？二叉樹，結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針？分析：分析：用二叉鏈表存儲(chǔ)包含用二叉鏈表存儲(chǔ)包含n n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有2n個(gè)鏈域個(gè)鏈域（見二叉鏈表數(shù)據(jù)類型說明）（見二叉鏈表數(shù)據(jù)類型說明）。除根結(jié)點(diǎn)外，二叉樹中每一個(gè)結(jié)點(diǎn)除根結(jié)點(diǎn)外，二叉樹中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親有且僅有一個(gè)雙親（直接前驅(qū)），所以只會(huì)有（直接前驅(qū)），所以只會(huì)有n n1

16、1個(gè)結(jié)點(diǎn)的鏈域存放指針，指?jìng)€(gè)結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)（即直接后繼）。向非空子女結(jié)點(diǎn)（即直接后繼）。思考：思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？有用的信息或線索？我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。以加快查找速度。所以，所以， 空指針數(shù)目空指針數(shù)目2n(n-1)=n+1個(gè)個(gè)。n+115二、線索二叉樹線索二叉樹（Threaded Binary Tree）普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，而

17、該結(jié)點(diǎn)的而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來，則從起來，則從第一第一個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)開始就能很快開始就能很快“順藤摸瓜順藤摸瓜”而遍歷整個(gè)樹了。而遍歷整個(gè)樹了。兩種解決方法兩種解決方法增加兩個(gè)域：增加兩個(gè)域：fwd和和bwd；利用空鏈域（利用空鏈域（n+1個(gè)空鏈域）個(gè)空鏈域）存放前驅(qū)指針存放前驅(qū)指針存放后繼指針存放后繼指針如何預(yù)存這類信息？如何預(yù)存這類信息？例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：B D C E A F H GB D C E A F H G，實(shí)際上，實(shí)際上已將二

18、叉已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！可能是根、或最左（右）葉子可能是根、或最左（右）葉子16規(guī)規(guī) 定：定：1）若結(jié)點(diǎn)有左子樹，則）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否則， lchild指向其直接前驅(qū)指向其直接前驅(qū)(即線索即線索)；2）若結(jié)點(diǎn)有右子樹，則）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則， rchild指向其直接后繼指向其直接后繼(即線索即線索) 。為了避免混淆，增加兩個(gè)標(biāo)志域?yàn)榱吮苊饣煜黾觾蓚€(gè)標(biāo)志域，如下圖所示：，如下圖所示：lchildLTagdataRTa

19、g rchild約定約定:當(dāng)當(dāng)Tag域?yàn)橛驗(yàn)?時(shí)時(shí),表示表示正常正常情況情況;當(dāng)當(dāng)Tag域?yàn)橛驗(yàn)?時(shí)時(shí),表示表示線索線索情況情況.17有關(guān)線索二叉樹的幾個(gè)術(shù)語：有關(guān)線索二叉樹的幾個(gè)術(shù)語： 線索鏈表：線索鏈表：用前頁結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表用前頁結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表 線線 索：索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹：線索二叉樹：加上線索的二叉樹加上線索的二叉樹（圖形式樣）（圖形式樣） 線線 索索 化：化：對(duì)二叉樹以對(duì)二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€使其變?yōu)榫€索二叉樹的過程索二叉樹的過程注：注：在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直在線索化二叉樹中，并不是每個(gè)

20、結(jié)點(diǎn)都能直接找到其后繼的，接找到其后繼的，當(dāng)標(biāo)志為當(dāng)標(biāo)志為0時(shí)，則需要通過一時(shí)，則需要通過一定運(yùn)算才能找到它的后繼定運(yùn)算才能找到它的后繼。18dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例例1：帶了帶了兩個(gè)標(biāo)志兩個(gè)標(biāo)志的某的某先序遍歷先序遍歷結(jié)果如表所示，請(qǐng)畫結(jié)果如表所示，請(qǐng)畫出對(duì)應(yīng)二叉樹。出對(duì)應(yīng)二叉樹。19ABCGEIDHFroot懸空？懸空？懸空？懸空？解：解：該二叉樹中序遍歷結(jié)果為該二叉樹中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：例例2

21、 2：畫出以下二叉樹對(duì)應(yīng)的畫出以下二叉樹對(duì)應(yīng)的中序中序線索二叉樹。線索二叉樹。為避免懸空為避免懸空態(tài)，應(yīng)增設(shè)態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)一個(gè)頭結(jié)點(diǎn)20對(duì)應(yīng)的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)如圖所示：對(duì)應(yīng)的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為注：此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G0-root0214.【 2000年計(jì)算機(jī)系考研題年計(jì)算機(jī)系考研題】給定如圖所示二叉給定如圖所示二叉樹樹T T，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。 2825405560330854解解: :因?yàn)橹行虮闅v序列是：因?yàn)橹行虮闅v序列是：5555 40 25 60 40 25 60 2828 08 33 08 33 5454對(duì)應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即對(duì)應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNILNILNIL22FTPFTP網(wǎng)址：網(wǎng)址：2/pub/dian/2/pub/dian/喻信星空喻信星空BBS BBS 網(wǎng)址：網(wǎng)址：2 2 端口端口: 2600: 2600劉玉老師的劉玉老師的E-mailE-mail信箱