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

上節(jié)回顧

7.3二叉樹的設(shè)計(jì)和實(shí)現(xiàn)

7.3.1二叉樹的存儲(chǔ)結(jié)構(gòu)

7.3.2二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹操作實(shí)現(xiàn)

17.4二叉樹遍歷7.4.1二叉樹遍歷1、遍歷定義——2、遍歷用途——3、遍歷方法——指按照某種順序訪問二叉樹中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。（或指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)）。它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。對(duì)每個(gè)結(jié)點(diǎn)的查看通常都是“先左后右”。24、遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、

L、R以根結(jié)點(diǎn)為參照系注：“先、中、后”的意思是指訪問的結(jié)點(diǎn)D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。

D、L、R的組合定義了六種可能的遍歷方案：LDR,LRD,DLR,DRL,RDL,RLD

若限定先左后右，則有三種實(shí)現(xiàn)方案：

DLRLDRLRD先序遍歷中序遍歷后序遍歷

35、二叉樹遍歷的基本方法有三種:先序遍歷(DLR)、中序遍歷(LDR)、后序遍歷(LRD)通常可以把二叉樹遍歷操作設(shè)計(jì)成遞歸算法。（一）先序遍歷二叉樹的遞歸算法為：若二叉樹為空，則算法結(jié)束；否則：（1）訪問根結(jié)點(diǎn)；（2）先序遍歷根結(jié)點(diǎn)的左子樹；（3）先序遍歷根結(jié)點(diǎn)的右子樹。（二）中序遍歷二叉樹的遞歸算法為：若二叉樹為空，則算法結(jié)束；否則：(1）中序遍歷根結(jié)點(diǎn)的左子樹；（2）訪問根結(jié)點(diǎn)；4（3）中序遍歷根結(jié)點(diǎn)的右子樹。（三）后序遍歷二叉樹的遞歸算法為：若二叉樹為空，則算法結(jié)束；否則：（1）后序遍歷根結(jié)點(diǎn)的左子樹；（2）后序遍歷根結(jié)點(diǎn)的右子樹；（3）訪問根結(jié)點(diǎn)。（四）二叉樹的層序遍歷算法：(1)初始化設(shè)置一個(gè)隊(duì)列；(2)把根結(jié)點(diǎn)指針入隊(duì)列；(3)當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行步驟(3.a)到步驟(3.c):5

(3.a)出隊(duì)列取得一個(gè)結(jié)點(diǎn)指針，訪問該結(jié)點(diǎn)；

(3.b)若該結(jié)點(diǎn)的左子樹非空，則將該結(jié)點(diǎn)的左子樹指針入隊(duì)列；

(3.c)若該結(jié)點(diǎn)的右子樹非空，則將該結(jié)點(diǎn)的右子樹指針入隊(duì)列；

（4）結(jié)束。

注意：一個(gè)二叉樹的遍歷序列不能決定一棵二叉樹，但先序（或后序）和中序遍歷序列的組合可以惟一確定一棵二叉樹。而先序和后序遍歷則不能。6例1：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：

ABCDEDBEACDEBCA口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根ABDEC7+*A*/EDCB先序遍歷結(jié)果+**/ABCDE—前綴表示法中序遍歷結(jié)果A/B*C*D+E—中綴表示法后序遍歷結(jié)果AB/C*D*E+—后綴表示法層次遍歷結(jié)果+*E*D/CAB例2：用二叉樹表示算術(shù)表達(dá)式8例3：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請(qǐng)畫出這棵二叉樹。分析：①由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即A）；②由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹的子孫（即BDCE），其右部必全部是右子樹的子孫（即FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。9已知中序遍歷：BDCEAFHG已知后序遍歷：DECBHGFA（BDCE）（FHG）（DCE）BFGHCDEA107.4.2二叉鏈存儲(chǔ)結(jié)構(gòu)下二叉樹遍歷的實(shí)現(xiàn)結(jié)點(diǎn)數(shù)據(jù)類型自定義typedefstructNode{DataType

data;structNode*leftchild；structNode*righthild；}BiTreeNnode;BiTreeNnode*root;

先序遍歷函數(shù)voidInOrder(BiTreeNode*t,voidvisit(DataTypeitem))//使用visit(item)函數(shù)中序遍歷二叉樹t{ if(t!=NULL) {InOrder(t->leftChild,visit);

visit(t->data); InOrder(t->rightChild,visit); }}思考：請(qǐng)同學(xué)們寫出中序和后序遍歷算法思想和函數(shù)。

11例4：編寫遞歸算法，打印二叉樹中所有葉子結(jié)點(diǎn)的值。

思路：若左右指針均空，必為葉子?？蛇x用任何一種遍歷算法查找葉子，將其統(tǒng)計(jì)并打印出來。

voidDLR(BiTreeNode*root,voidvisit(DataTypeitem))

//采用先序遍歷的遞歸算法{if(root!=NULL)//非空二叉樹條件，等效于if(root){if(!root->leftChild&&!root->rightChild)//是葉子結(jié)點(diǎn)則統(tǒng)計(jì)并打印{visit(root->data);}

DLR(root->leftChild,visit);//遞歸遍歷左子樹，直到葉子處；

DLR(root->rigthChild,visit);//遞歸遍歷右子樹，直到葉子處；}}127.5線索二叉樹所以，空指針數(shù)目＝2n－(n-1)=n+1個(gè)。證明：用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有2n個(gè)鏈域。除根結(jié)點(diǎn)外，二叉樹中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，意即每個(gè)結(jié)點(diǎn)地址占用了雙親的一個(gè)直接后繼，n個(gè)結(jié)點(diǎn)地址共占用了n-1個(gè)雙親的指針域。也就是說，只會(huì)有n－1個(gè)結(jié)點(diǎn)的鏈域存放指針。ThreadedBinaryTree討論：用二叉鏈表法（leftchild,rightchild）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針？有n+1個(gè)！13思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。結(jié)論：用二叉鏈表法存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的指針區(qū)域中會(huì)有n+1個(gè)空指針。這就是線索二叉樹（ThreadedBinaryTree）14二叉樹中容易找到結(jié)點(diǎn)的左右孩子信息，但該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在某種遍歷過程中動(dòng)態(tài)獲得。先依遍歷規(guī)則把每個(gè)結(jié)點(diǎn)對(duì)應(yīng)的前驅(qū)和后繼線索預(yù)存起來，這叫做“線索化”。意義：從任一結(jié)點(diǎn)出發(fā)都能快速找到其前驅(qū)和后繼，且不必借助堆棧。對(duì)二叉樹進(jìn)行某種遍歷之后，將得到一個(gè)線性有序的序列。例如對(duì)某二叉樹的中序遍歷結(jié)果是BDCEAFHG，意味著已將該樹轉(zhuǎn)為線性排列，顯然其中結(jié)點(diǎn)具有唯一前驅(qū)和唯一后繼。在此前提下，那n+1個(gè)空鏈域才能裝入（也裝得下）“線索”。討論2.如何獲得這種“直接前驅(qū)”或“直接后繼”？有何意義？討論1：二叉樹是1:2的非線性結(jié)構(gòu)，如何定義其直接后繼？15①每個(gè)結(jié)點(diǎn)增加兩個(gè)域：fwd和bwd；存放前驅(qū)指針存放后繼指針如何預(yù)存這類信息？有兩種解決方法：②與原有的左右孩子指針域“復(fù)用”，充分利用那n+1個(gè)空鏈域。規(guī)定：1）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。datalchildrchildfwdbwddatalchildrchild缺點(diǎn)：空間效率太低！問題：計(jì)算機(jī)如何判斷是孩子指針還是線索指針？如何區(qū)別？16lchildLTagdataRTagrchild約定:當(dāng)Tag域?yàn)?時(shí),表示正常情況;當(dāng)Tag域?yàn)?時(shí),表示線索情況.前驅(qū)(后繼)左(右)孩子為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域：問：增加了前驅(qū)和后繼等線索有什么好處？——能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用堆棧（遞歸）也能遍歷整個(gè)樹。各1bit171.有關(guān)線索二叉樹的幾個(gè)術(shù)語線索鏈表：線索：線索二叉樹：線索化：用含Tag的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表。指向結(jié)點(diǎn)前驅(qū)和后繼的指針。在二叉樹的結(jié)點(diǎn)上加上線索的二叉樹。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程。線索化過程就是在遍歷過程中修改空指針的過程：將空的lchild改為結(jié)點(diǎn)的直接前驅(qū)；將空的rchild改為結(jié)點(diǎn)的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況”）18dataAGEIDJHCFBLtag0011110101Rtag0001010111AGEIDJHCFB例5：帶了兩個(gè)標(biāo)志的某先序遍歷結(jié)果如下表所示，請(qǐng)畫出對(duì)應(yīng)的二叉樹。ATag=1表示線索:Ltag=1表示前驅(qū)Rtag=1表示后繼19ABCGEIDHFroot懸空？NIL懸空？NIL解：對(duì)該二叉樹中序遍歷的結(jié)果為:

H,D,I,B,E,A,F,C,G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)例6：畫出以下二叉樹對(duì)應(yīng)的中序線索二叉樹。2.線索二叉樹的生成——線索化線索化過程就是在遍歷過程中修改空指針的過程2000A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,

G0root0對(duì)應(yīng)的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)如圖所示：21例7：給定如圖所示二叉樹T，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹