數(shù)據(jù)結構第7章3

上節(jié)回顧

7.3二叉樹的設計和實現(xiàn)

7.3.1二叉樹的存儲結構

7.3.2二叉鏈存儲結構的二叉樹操作實現(xiàn)

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

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

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

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

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

35、二叉樹遍歷的基本方法有三種:先序遍歷(DLR)、中序遍歷(LDR)、后序遍歷(LRD)通?？梢园讯鏄浔闅v操作設計成遞歸算法。（一）先序遍歷二叉樹的遞歸算法為：若二叉樹為空，則算法結束；否則：（1）訪問根結點；（2）先序遍歷根結點的左子樹；（3）先序遍歷根結點的右子樹。（二）中序遍歷二叉樹的遞歸算法為：若二叉樹為空，則算法結束；否則：(1）中序遍歷根結點的左子樹；（2）訪問根結點；4（3）中序遍歷根結點的右子樹。（三）后序遍歷二叉樹的遞歸算法為：若二叉樹為空，則算法結束；否則：（1）后序遍歷根結點的左子樹；（2）后序遍歷根結點的右子樹；（3）訪問根結點。（四）二叉樹的層序遍歷算法：(1)初始化設置一個隊列；(2)把根結點指針入隊列；(3)當隊列非空時，循環(huán)執(zhí)行步驟(3.a)到步驟(3.c):5

(3.a)出隊列取得一個結點指針，訪問該結點；

(3.b)若該結點的左子樹非空，則將該結點的左子樹指針入隊列；

(3.c)若該結點的右子樹非空，則將該結點的右子樹指針入隊列；

（4）結束。

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

ABCDEDBEACDEBCA口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根ABDEC7+*A*/EDCB先序遍歷結果+**/ABCDE—前綴表示法中序遍歷結果A/B*C*D+E—中綴表示法后序遍歷結果AB/C*D*E+—后綴表示法層次遍歷結果+*E*D/CAB例2：用二叉樹表示算術表達式8例3：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請畫出這棵二叉樹。分析：①由后序遍歷特征，根結點必在后序序列尾部（即A）；②由中序遍歷特征，根結點必在其中間，而且其左部必全部是左子樹的子孫（即BDCE），其右部必全部是右子樹的子孫（即FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。9已知中序遍歷：BDCEAFHG已知后序遍歷：DECBHGFA（BDCE）（FHG）（DCE）BFGHCDEA107.4.2二叉鏈存儲結構下二叉樹遍歷的實現(xià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); }}思考：請同學們寫出中序和后序遍歷算法思想和函數(shù)。

11例4：編寫遞歸算法，打印二叉樹中所有葉子結點的值。

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

voidDLR(BiTreeNode*root,voidvisit(DataTypeitem))

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

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

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

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

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

G0root0對應的中序線索二叉樹存儲結構如圖所示：21例7：給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹