數(shù)據(jù)結(jié)構(gòu) 06-2課件

第6章樹和二叉樹

（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)二叉樹的運算16.2二叉樹為何要重點研究每結(jié)點最多只有兩個“叉”的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。6.2.1 二叉樹的定義6.2.2 二叉樹的性質(zhì)6.2.3二叉樹的存儲結(jié)構(gòu)26.2.2二叉樹的性質(zhì)

(3+2)性質(zhì)1:在二叉樹的第i層上至多有2i-1個結(jié)點（i>0）。性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點（k>0）。性質(zhì)3:對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備以下2個性質(zhì)：性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為log2n＋1性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結(jié)點，其左孩子編號必為2i，其右孩子編號為2i＋1；其雙親的編號必為i/2（i＝1時為根,除外）。

3討論：不是完全二叉樹怎么辦？答：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點”，其內(nèi)容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點：①浪費空間；②插入、刪除不便

5二、鏈?zhǔn)酱鎯Y(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_childright_childdataleft_childright_child二叉樹結(jié)點數(shù)據(jù)類型定義：typedefstructnode

*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,

right_child;}node;一般從根結(jié)點開始存儲。

（相應(yīng)地，訪問樹中結(jié)點時也只能從根開始）注：如果需要倒查某結(jié)點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。6二叉樹鏈?zhǔn)酱鎯εe例：

ABECD^AB^D^C^^E^優(yōu)點：①不浪費空間；②插入、刪除方便

76.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹遍歷定義——遍歷用途——遍歷方法——指按某條搜索路線遍訪每個結(jié)點且不重復(fù)（又稱周游）。它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。對每個結(jié)點的查看通常都是“先左后右”。TraversingBinaryTree8例1：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：ABCDEDBEACDEBCA口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根ABDEC10中序遍歷算法LDR(node*root){if(root!=NULL){LDR(root->lchild);printf(“%d”,root->data);

LDR(root->rchild);}return(0);}后序遍歷算法LRD(node*root){if(root!=NULL)

{LRD(root->lchild);LRD(root->rchild);printf(“%d”,root->data);}return(0);}結(jié)點數(shù)據(jù)類型自定義typedefstructnode{intdata;structnode*lchild,*rchild；}node;node*root;

先序遍歷算法DLR(node*root){if(root!=NULL)//非空二叉樹

{printf(“%d”,root->data);//訪問DDLR(root->lchild);//遞歸遍歷左子樹DLR(root->rchild);//遞歸遍歷右子樹}return(0);}12例：編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。

思路：若左右指針均空，必為葉子?？蛇x用任何一種遍歷算法查找葉子，將其統(tǒng)計并打印出來。DLR(node*root)//采用先序遍歷的遞歸算法{if(root!=NULL)//非空二叉樹條件，等效于if(root){if(!root->lchild&&!root->rchild)//是葉子結(jié)點則統(tǒng)計并打印{sum++;printf("%d\n",root->data);}

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

DLR(root->rchild);}//遞歸遍歷右子樹，直到葉子處；}return(0);}14用空格字符表示‘無孩子’或指針為空如何把二叉樹存入電腦內(nèi)？例：將下面的二叉樹以二叉鏈表形式存入計算機(jī)內(nèi)。ABGDFCE考慮1：輸入結(jié)點時怎樣表示“無孩子”？考慮2：以何種遍歷方式來輸入和建樹？將二叉樹按先序遍歷次序輸入：ABC

DE

G

F

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

無法惟一表示結(jié)束。15建樹算法：StatusCreateBiTree(BiTree&T){//構(gòu)造二叉樹Tscanf(“%c”,&ch);if(ch==’’)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(overflow);T->data=ch;//生成根結(jié)點CreateBiTree(T->lchild);//構(gòu)造左子樹CreateBiTree(T->rchild);//構(gòu)造右子樹}returnOK;}//CreateBiTree輸入序列：

ABC

DE

G

F

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

17已知中序遍歷：BDCEAFHG已知后序遍歷：DECBHGFA（BDCE）（FHG）A（DCE）BFGHCDEABBACCD

C

E18思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——我們可以用它來存放當(dāng)前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。結(jié)論：用二叉鏈表法存儲包含n個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中會有n+1個空指針。這就是線索二叉樹（ThreadedBinaryTree）20二叉樹中容易找到結(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)，如何定義其直接后繼？21lchildLTagdataRTagrchild約定:當(dāng)Tag域為0時,表示正常情況;當(dāng)Tag域為1時,表示線索情況.前驅(qū)(后繼)左(右)孩子為區(qū)別兩種不同情況，特增加兩個標(biāo)志域：問：增加了前驅(qū)和后繼等線索有什么好處？——能方便找出當(dāng)前結(jié)點的前驅(qū)和后繼，不用堆棧（遞歸）也能遍歷整個樹。各1bit231.有關(guān)線索二叉樹的幾個術(shù)語：線索鏈表：線索：線索二叉樹：線索化：用含Tag的結(jié)點樣式所構(gòu)成的二叉鏈表指向結(jié)點前驅(qū)和后繼的指針加上線索的二叉樹對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程線索化過程就是在遍歷過程中修改空指針的過程：將空的lchild改為結(jié)點的直接前驅(qū)；將空的rchild改為結(jié)點的直接后繼。非空指針呢？仍然指向孩子結(jié)點（稱為“正常情況”）24ABCGEIDHFroot懸空？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.線索二叉樹的生成——線索化線索化過程就是在遍歷過程中修改空指針的過程2600A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:

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

G0root0對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：27例2：給定如圖所示二叉樹T，請畫出與其對應(yīng)的中序線索二叉樹。

2825