數(shù)據(jù)結(jié)構(gòu)-第六章樹和二叉樹C(嚴(yán)蔚敏)課件

第6章樹和二叉樹

（TreeandBinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)二叉樹的運(yùn)算1遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、

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

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

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

2例1：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：BDCAFEDCBFEA口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根ABCEFABECFDD3先序遍歷結(jié)果E(BA(DC))(F(HG(I(KJ))))中序遍歷結(jié)果(A

B

(CD)

E(F(GH(I(JK))))例3：假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ,中序序列為ABCDEFGHIJK,畫出該樹.EBIAHFDCGKJ5已知中序遍歷：BDCEAFHG已知后序遍歷：DECBHGFA（BDCE）（FHG）A（DCE）BFGHCDEABBACCD

C

E練習(xí):6中序遍歷算法Inorder(BinTreeNode

*t){if(root!=NULL){Inorder(t->left);cout<<t->data<<endl;

Inorder(t->right);}return(0);}后序遍歷算法Postorder(BinTreeNode

*t){if(t!=NULL)

{Postorder(t->left);

Postorder(t->right);cout<<t->data<<endl;}return(0);}結(jié)點數(shù)據(jù)類型自定義ClassBinTreeNode{public:Tdata;Private:BinTreeNode*lfet,*right；}

先序遍歷算法::Preorder(BinTreeNode*t){if(t!=NULL)//非空二叉樹

{cout<<t->data<<endl;//訪問DPreorder(t->left);//遞歸遍歷左子樹preorder(t->right);//遞歸遍歷右子樹}return(0);}7對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將print語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點的時機(jī)不同。從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過3次。AFEDCBG第1次經(jīng)過時訪問，是先序遍歷第2次經(jīng)過時訪問，是中序遍歷第3次經(jīng)過時訪問，是后序遍歷2.二叉樹遍歷的時間效率和空間效率時間效率:O(n)

//每個結(jié)點只訪問一次空間效率:O(n)

//棧占用的最大輔助空間精確值：樹深為k的遞歸遍歷需要k+1個輔助單元8用空格字符表示‘無孩子’或指針為空如何把二叉樹存入電腦內(nèi)？例：將下面的二叉樹以二叉鏈表形式存入計算機(jī)內(nèi)。ABGDFCE考慮1：輸入結(jié)點時怎樣表示“無孩子”？考慮2：以何種遍歷方式來輸入和建樹？將二叉樹按先序遍歷次序輸入：ABC

DE

G

F

(/n)以先序遍歷最為合適，讓每個結(jié)點都能及時被連接到位。字符串輸完后應(yīng)當(dāng)再加一特殊的結(jié)束符號(如$)，因為

無法惟一表示結(jié)束。10特別討論：若已知先序（或后序）遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請畫出這棵二叉樹。分析：①由后序遍歷特征，根結(jié)點必在后序序列尾部（即A）；②由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是左子樹的子孫（即BDCE），其右部必全部是右子樹的子孫（即FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推?！緡?yán)題集6.31④】請證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。

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

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

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

G0root0對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：21線索二叉樹的生成算法（遞歸算法見教材P115-116）目的：在遍歷二叉樹的過程中修改空指針，添加前驅(qū)或后繼的線索，使之成為線索二叉樹。為了記下遍歷過程中訪問結(jié)點的先后次序，需要設(shè)置兩個指針：p指針→當(dāng)前結(jié)點之指針；pre指針→當(dāng)前結(jié)點的前趨結(jié)點指針。設(shè)計技巧：依某種順序遍歷二叉樹，對每個結(jié)點p，判斷其左指針是否為空，以及其前驅(qū)結(jié)點的右指針是否為空。每次只修改前驅(qū)結(jié)點的右指針（后繼）和本結(jié)點的左指針（前驅(qū)），參見算法6.6。若p->lchild＝NULL,則{p->Ltag=1;p->lchild＝pre;}

//p的前驅(qū)線索應(yīng)存p結(jié)點的左邊若pre->rchild＝NULL,則{pre->Rtag＝1;pre->rchild=p;}

//pre的后繼線索應(yīng)存pre結(jié)點的右邊233.線索二叉樹的遍歷（無需堆棧）對于線索二叉樹的遍歷，只要找到序列中的第一個結(jié)點，然后依次訪問結(jié)點的后繼直到后繼為空為止。（因為建立線索時已遍歷一次，相當(dāng)于線性化了！）難點：在線索化二叉樹中，并不是每個結(jié)點都能直接找到其后繼的，當(dāng)標(biāo)志為0時，則需要通過一定運(yùn)算才能找到它的后繼。以中序線索二叉樹為例：當(dāng)RTag=1時，直接后繼指針就在其rchild域內(nèi)；當(dāng)RTag=0時，直接后繼是當(dāng)前結(jié)點右子樹最左下方的結(jié)點；請注意中序遍歷規(guī)則是LDR，先左再根再右24有后繼找后繼算法流程：returnOK;p=T->lchild;p!=Tp->LTag==0p=p->lchild;visit(p->data);p->RTag==1&&p->rchild!=Tp=p->rchild;visit(p->data);p=p->rchild;YNYNYN先找最左子孫找到最左子孫無后繼找右子樹的最左子孫266.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹遍歷——指按某條搜索路線遍訪每個結(jié)點且不重復(fù)。常用的有先序、中序和后序遍歷，還有層次遍歷。TraversingBinaryTree6.3.2線索二叉樹用二叉鏈表法存儲包含n個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中會有n+1個空指針。可以用它來存放當(dāng)前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。ThreadedBinaryTree27例：【考研題】給定如圖所示二叉樹T，請畫出與其對應(yīng)的中序線索二叉樹。

2825405560330854解:因為中序遍歷序列是：5540256028083354對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。NILNILNIL和NULL的值都是0,區(qū)別何在？在Delphi中NIL用來標(biāo)記空指針，Null用來表示空的Variant型變量或是ASCII碼為0的字符，比如用于標(biāo)記字符串結(jié)束。在C/C++中定義的宏NULL不加區(qū)別的包括了以上兩種含義?？梢奜bjectPascal的語法要比C/C++嚴(yán)謹(jǐn)?shù)枚?86.4樹和森林6.4.1樹和森林與二叉樹的轉(zhuǎn)換6.4.2樹和森林的存儲方式6.4.3樹和森林的遍歷306.4.1樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：step1:將樹中同一結(jié)點的兄弟相連;加線抹線旋轉(zhuǎn)討論1：樹如何轉(zhuǎn)為二叉樹？孩子—兄弟表示法step2:保留結(jié)點的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。31方法：加線—抹線—旋轉(zhuǎn)

abeidfhgc樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連長兄為父孩子靠左特點是？根結(jié)點沒有右孩子！32討論2：二叉樹怎樣還原為樹？abeidfhgc要點：逆操作，把所有右孩子變?yōu)樾值埽?/p>

abdefhgic33法一：①各森林先各自轉(zhuǎn)為二叉樹；②依次連到前一個二叉樹的右子樹上。討論3：森林如何轉(zhuǎn)為二叉樹？即F={T1,T2,…,Tm}B={root,LB,RB}法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹（參見教材P138圖6.17，兩種方法都有轉(zhuǎn)換示意圖）法一和法二得到的二叉樹是完全相同的、惟一的。34ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林轉(zhuǎn)二叉樹舉例：

（用法二，森林直接變兄弟，再轉(zhuǎn)為二叉樹）兄弟相連長兄為父頭樹為根孩子靠左A35ABCDEFGHJI討論4：二叉樹如何還原為森林？要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?/p>

即B={root,LB,RB}F={T1,T2,…,Tm}ABCDEFGHJIEFABCDGHJI366.4.2樹和森林的存儲方式樹有三種常用存儲方式：①雙親表示法②孩子表示法③孩子—兄弟表示法

nextsiblingdatafirstchild指向左孩子指向右兄弟問：樹→二叉樹的“連線—抹線—旋轉(zhuǎn)”如何由計算機(jī)自動實現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。

存儲的過程就是樹轉(zhuǎn)換為二叉樹的過程！37abecdfhgbacedfgh例如：386.4.3樹和森林的遍歷樹的遍歷例如：abdec先根序列：后根序列：abcdebdcea深度優(yōu)先遍歷（先根、后根）廣度優(yōu)先遍歷（層次）先根遍歷訪問根結(jié)點；依次先根遍歷根結(jié)點的每棵子樹。后根遍歷依次后根遍歷根結(jié)點的每棵子樹；訪問根結(jié)點。樹沒有中序遍歷（因子樹不分左右）39討論：樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.樹的先根遍歷與二叉樹的先序遍歷相同；2.樹的后根遍歷相當(dāng)于二叉樹的中序遍歷；3.樹沒有中序遍歷，因為子樹無左右之分。結(jié)論：樹的先根序列：abcde樹的后根序列：bdcea40先根遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點；先根遍歷第一棵樹的根結(jié)點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷ABCDEFGHJI為何有中序？深度優(yōu)先遍歷（先根、中根、后根）廣度優(yōu)先遍歷（層次）中根遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結(jié)點的子樹森林；訪問第一棵樹的根結(jié)點；中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。41討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？例如：ABCDEFGHJI先根序列：中根序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG結(jié)論：森林的先根和中根遍歷在兩種方式下的結(jié)果相同。但森林的后根遍歷則不一定，因而少用422.如何按層次輸出二叉樹中所有結(jié)點？

算法思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結(jié)點的指針是個好辦法，此時絕不能用遞歸算法。技巧：當(dāng)根結(jié)點入隊后，令其左、右孩子結(jié)點入隊，而左孩子出隊時又令它的左右孩子結(jié)點入隊，……由此便可產(chǎn)生按層次輸出的效果。附：二叉樹若干典型算法（習(xí)題課）1.如何求二叉樹的深度，或從某個結(jié)點開始的子樹深度？

算法思路：只查各結(jié)點后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。ABCDE算法見附1算法見附243算法思路：若不用遞歸，則要實現(xiàn)二叉樹遍歷的“嵌套”規(guī)則，必用堆棧(迭代方式)。可直接用while語句和push/pop操作。參見教材P130-131程序。4中序遍歷的非遞歸算法如何實現(xiàn)？3.如何判別給定二叉樹是否為完全二叉樹？算法思路：完全二叉樹的特點是：沒有左子樹空而右子樹單獨存在的情況(前k-1層都是滿的，且第k層左邊也滿）。技巧:按層次遍歷方式，先把所有結(jié)點（不管當(dāng)前結(jié)點是否有左右孩子）都入隊列.若為完全二叉樹,則層次遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列.如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。算法見附3算法見附444VoidABC(Bitreep,intl,int&h){ifp≠NILthen

{l=l+1;ifl>hthenh=l;ABC(p->Lchild,l,h);ABC(p->Rchild,l,h);

}}

法1：從根開始向下計算層次(比從葉子往上計算更簡單)l、h分別表示二叉樹的層次數(shù)和深度。想一想，l和h的初始值應(yīng)設(shè)為多少？開始調(diào)用時，應(yīng)當(dāng)用ABC（p,0,0