第5與二叉樹(shù)樹(shù)

1、數(shù)據(jù)結(jié)構(gòu)與算法第五章 二叉樹(shù)和樹(shù)（二）王昭信息學(xué)院wangzhaoi1wangzhao內(nèi)容提要 二叉樹(shù) 二叉樹(shù)的應(yīng)用 樹(shù)與樹(shù)林2wangzhao樹(shù)與樹(shù)林樹(shù)的定義基本術(shù)語(yǔ)樹(shù)林樹(shù)的基本運(yùn)算樹(shù)的周游樹(shù)林的周游樹(shù)、樹(shù)林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和樹(shù)林的表示3wangzhao關(guān)系行政區(qū)社會(huì)機(jī)構(gòu)：公司-處-科-室書(shū)籍目錄：書(shū)-章-節(jié)小節(jié)物種分類(lèi)：門(mén)-綱-類(lèi)-科-目種4wangzhao教學(xué)內(nèi)容第二章第三章第九章第一章演示隨堂小測(cè)作業(yè)提交和講評(píng)源程序示例動(dòng)畫(huà)演示授課課件課件 2中源程上機(jī)作業(yè)講評(píng)課件1中動(dòng)畫(huà)動(dòng)畫(huà)動(dòng)畫(huà)書(shū)面上機(jī)授課授課作業(yè)源程序演示 n演示 2演示 1作業(yè)作業(yè)課件 2課件 1序及講評(píng)源程序n源程序1源程序2

2、5wangzhao幼兒園初中大學(xué)高中工作小學(xué)大四大三大二大一好友 C好友 B班級(jí)中班級(jí)羽中秋晚畢業(yè)留班級(jí)秋班級(jí)籃球班級(jí)室友A生賽來(lái)訪春游日聚會(huì)來(lái)訪球晚會(huì)毛球賽會(huì)影游6wangzhao建筑設(shè)計(jì)素材網(wǎng)首頁(yè)室內(nèi)模型素材建筑景觀室內(nèi)設(shè)計(jì)方建筑動(dòng)畫(huà)素材建筑效果圖素材建筑設(shè)計(jì)書(shū)籍室內(nèi)設(shè)計(jì)書(shū)籍景觀設(shè)計(jì)書(shū)籍案景觀設(shè)室內(nèi)設(shè)建筑設(shè)計(jì)方案計(jì)方案計(jì)方案建筑景觀室內(nèi)建筑景觀建筑景觀室內(nèi)設(shè)計(jì)方案 2設(shè)計(jì)方案 2設(shè)計(jì)方案 1設(shè)計(jì)方案 1設(shè)計(jì)方案 1設(shè)計(jì)方案 n設(shè)計(jì)方案 n設(shè)計(jì)方案 27wangzhao樹(shù)的表現(xiàn)形式ABCDEFGHIJ（a）樹(shù)形表示b入8wangzhao樹(shù)的表現(xiàn)形式(c)文氏圖ABGCHDFIEJ(A(B(D

3、)(E(I)(J)(F)(C(G)(H)(d)嵌套括號(hào)表示法9wangzhao樹(shù)的定義樹(shù)的遞歸定義：n(n0)個(gè)結(jié)點(diǎn)的有窮集合T，當(dāng)T非空時(shí)滿足：有且僅有一個(gè)特別標(biāo)出的稱(chēng)為根的結(jié)點(diǎn)除根外，其余結(jié)點(diǎn)分為m0個(gè)互不相交的非空集合T1,T2,Tm，而且每個(gè)非空集合Ti又是一顆樹(shù)，稱(chēng)為根結(jié)點(diǎn)的。T1=B，T2=C，E，H，I，J， T3=D，F(xiàn)，G特別地，允許不包括任何結(jié)點(diǎn)的樹(shù)，把它稱(chēng)作空樹(shù)。10wangzhao樹(shù)的特點(diǎn)在一棵樹(shù)中，通常將一個(gè)結(jié)點(diǎn)定義為其的根結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，而的根結(jié)點(diǎn)就是它的后繼結(jié)點(diǎn)。根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其它結(jié)點(diǎn)有唯一前驅(qū)所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼樹(shù)描述的是層次關(guān)系，數(shù)據(jù)元間存在一對(duì)

4、多或多對(duì)一關(guān)系。11wangzhao樹(shù)與樹(shù)林樹(shù)的定義基本術(shù)語(yǔ)樹(shù)林樹(shù)的基本運(yùn)算樹(shù)的周游樹(shù)林的周游樹(shù)、樹(shù)林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和樹(shù)林的表示12wangzhao樹(shù)和二叉樹(shù)之間差別二叉樹(shù)不是樹(shù)的特殊情形，它們是兩個(gè)概念。樹(shù)和二叉樹(shù)之間差別二叉樹(shù)中結(jié)點(diǎn)的在結(jié)點(diǎn)只有一棵樹(shù)還是右樹(shù)和二叉樹(shù)之間相同處要區(qū)分為樹(shù)和右，即使是的情況下也要明確該父結(jié)點(diǎn)、子結(jié)點(diǎn)、路徑、路徑長(zhǎng)度等概念與二叉樹(shù)的定義相同13wangzhao基本術(shù)語(yǔ)1無(wú)序樹(shù)、有序樹(shù)對(duì)的次序不加區(qū)別的樹(shù)叫作“無(wú)序樹(shù)”。對(duì)之間的次序加以區(qū)別的樹(shù)叫作“有序樹(shù)”例如在右圖中，按無(wú)序樹(shù)的概念t和t是同一棵樹(shù)，按有序樹(shù)的概念則是不同的樹(shù)，本章討論的樹(shù)一般是有序樹(shù)wang

5、zhao基本術(shù)語(yǔ)2結(jié)點(diǎn)的次序在有序樹(shù)中可以從左到右地規(guī)定結(jié)點(diǎn)的次序例如圖中，結(jié)點(diǎn)2，3，4是從左到右排序的；可以說(shuō)結(jié)點(diǎn)3是結(jié)點(diǎn)2右邊的結(jié)點(diǎn)，是結(jié)點(diǎn)4左邊的結(jié)點(diǎn)還可以說(shuō)結(jié)點(diǎn)3的所有都在結(jié)點(diǎn)2及其的右邊，而在結(jié)點(diǎn)4及其的左邊按從左到右的順序，可以把一個(gè)結(jié)點(diǎn)的最左邊的結(jié)點(diǎn)簡(jiǎn)稱(chēng)“最結(jié)點(diǎn)”或“長(zhǎng)子”，長(zhǎng)子右邊的結(jié)點(diǎn)稱(chēng)為“次子”注意：祖先與子孫之間不存在左右的概念。15wangzhao樹(shù)與樹(shù)林樹(shù)的定義基本術(shù)語(yǔ)樹(shù)林樹(shù)的基本運(yùn)算樹(shù)的周游樹(shù)林的周游樹(shù)、樹(shù)林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和樹(shù)林的表示16wangzhao樹(shù)林的概念“樹(shù)林”是由0個(gè)到多個(gè)不相交的樹(shù)所組成的集O合樹(shù)林中每棵樹(shù)的根彼此稱(chēng)為“兄弟”，與自然界的樹(shù)林有所不

6、同， 這里的樹(shù)林可以是一個(gè)空集。如果從一棵樹(shù)中將根結(jié)點(diǎn)（連同根結(jié)點(diǎn)到各子結(jié)點(diǎn)的邊） 刪除，便得到一個(gè)樹(shù)林17wangzhao樹(shù)與樹(shù)林樹(shù)的定義基本術(shù)語(yǔ)樹(shù)林樹(shù)的基本運(yùn)算樹(shù)的周游樹(shù)林的周游樹(shù)、樹(shù)林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和樹(shù)林的表示18wangzhao樹(shù)的基本運(yùn)算1Tree t;Node p;1.TreecreatTree(NodeP,Treet1,Treet2,.,Treeti)(i=1,2,3,.)創(chuàng)建一棵空樹(shù)；2.isNULL(Tree t)判斷某棵樹(shù)是否為空；3.Node root(Tree t)求樹(shù)中的根結(jié)點(diǎn)，若為空樹(shù)，則返回一特殊值；Node parent(Node P)求樹(shù)中某個(gè)指定結(jié)點(diǎn)p的父

7、結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)為根時(shí)，4.返回一特殊值；19wangzhao樹(shù)的基本運(yùn)算2eftChild (Node p)5.N求樹(shù)中某個(gè)指定結(jié)點(diǎn)p的最結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)為樹(shù)葉時(shí)，它沒(méi)有，則返回一特殊值；6.Node rightSibling(Node P)求樹(shù)中某個(gè)指定結(jié)點(diǎn)p的右兄弟結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)沒(méi)有右兄弟時(shí)，返回一特殊值；7.樹(shù)的周游，即按某種方式樹(shù)中的所有結(jié)點(diǎn)，并使每個(gè)結(jié)點(diǎn)恰好被一次20wangzhao樹(shù)與樹(shù)林樹(shù)的定義基本術(shù)語(yǔ)樹(shù)林樹(shù)的基本運(yùn)算樹(shù)的周游樹(shù)林的周游樹(shù)、樹(shù)林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和樹(shù)林的表示21wangzhao樹(shù)的周游定義：對(duì)一棵樹(shù)進(jìn)行“周游”就是按某一規(guī)律系統(tǒng)地樹(shù)的所有結(jié)點(diǎn)，并使每個(gè)結(jié)點(diǎn)恰好被

8、一周游的結(jié)果： 存放：在周游樹(shù)的過(guò)程中，如果將各個(gè)結(jié)點(diǎn)按其被的先后順序排列起來(lái)，則到一個(gè)包括所有結(jié)點(diǎn)的線性表 周游空樹(shù)得到的線性表為空表 當(dāng)樹(shù)中只有一個(gè)結(jié)點(diǎn)時(shí)，對(duì)應(yīng)的線性表也只有一個(gè)元素 除以上兩種情況外，周游一棵樹(shù)所得到的線性表依賴(lài)于周游方法本質(zhì)：將非線性結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)。22wangzhao周游方法按深度方向周游縱向遍歷按寬度方向周游橫向遍歷23wangzhao按深度方向周游 主要有以下三種方法：先根次序中根次序后根次序24wangzhao先根次序根結(jié)點(diǎn)；從左到右按先根次序周游根結(jié)點(diǎn)的每棵按先根次序周游所列出的線性表為：12358961047通常按先根次序?qū)σ豢脴?shù)周游得到的線性稱(chēng)為這棵樹(shù)

9、的先根序列。25wangzhao按先根次序周游樹(shù)的算法/遞歸算法void preOrder(Node p)Node c;visit(p);c = leftChild(q);/*獲取該結(jié)點(diǎn)的長(zhǎng)子*/然后按照從左往右的次序先根遍歷該結(jié)點(diǎn)的while (c!=NULL)reOrderc/先根遍歷c = rightSibling(c);/右兄弟26wangzhao中根次序按中根次序周游根結(jié)點(diǎn)的最根結(jié)點(diǎn)；樹(shù)；從左到右按中根次序周游根結(jié)點(diǎn)的其它各按中根次序周游得到的線性表為：21859310674通常按中根次序?qū)σ豢脴?shù)周游得到的線性表稱(chēng)為這棵樹(shù)的中根序列。按中根次序周游樹(shù)的遞歸算法27wangzhao后根

10、次序從左到右按后根次序周游根結(jié)點(diǎn)的每棵；根結(jié)點(diǎn)按后根次序周游得到的線性表為：28951063741通常按后根次序?qū)σ豢脴?shù)周游得到的線性表稱(chēng)為這棵樹(shù)的后根序列。28wangzhao按后根次序周游樹(shù)的遞歸算法voidtOrder(Node p)Node c;c = leftChild(q);/獲取該結(jié)點(diǎn)的長(zhǎng)子/然后按照從左往右的次序后根遍歷該結(jié)點(diǎn)的所有while (c!=NULL)tOrder( c);/后根遍歷c = rightSibling(c);/繼續(xù)后根遍歷右兄弟visit(p);/最后根29wangzhao遍歷特點(diǎn)相同點(diǎn)：在先、中和后根遍歷序列中，樹(shù)結(jié)點(diǎn)的左右次序不變;不同點(diǎn)：那些屬于同

11、一條路徑上的結(jié)點(diǎn)，即只有祖先孫之間的相對(duì)次序，在上述三種序列中可能有所不同在先根遍歷序列中，結(jié)點(diǎn)的所有子孫都緊密排列在該結(jié)點(diǎn)的右邊；假定 ost n 表示結(jié)點(diǎn)n在先根序列中的位置，desc(n)表示結(jié)點(diǎn)n的子孫個(gè)數(shù)，則結(jié)點(diǎn)x是結(jié)點(diǎn)n的子孫的充分必要條件為： ost n +desc nost xost n在后根遍歷序列中，結(jié)點(diǎn)的所有子孫都緊密排列在該結(jié)點(diǎn)的左邊；假定 ost n 表示結(jié)點(diǎn)n在后根序列中的位置，desc(n)表示結(jié)點(diǎn)n的子孫個(gè)數(shù)，則結(jié)點(diǎn)x是結(jié)點(diǎn)n的子孫的充分必要條件為： ost n -desc nost xnistp+1.parent = p)return p+1;elseretu

12、rn -1;50wangzhao求右兄弟結(jié)點(diǎn)的位置rightSibling_partree(PParTree t,p)if(p=0 & pn)-n; i+)if (t-nisti.parent = t-nreturn i;istp.parent;)return 1;51wangzhao樹(shù)的表示樹(shù)的表示父指針表示法子表表示法雙親表示法孩子表示法長(zhǎng)子-兄弟表示法 孩子兄弟表示法樹(shù)林的表示52wangzhao樹(shù)的子表表示法方法：把整棵樹(shù)看成一個(gè)結(jié)點(diǎn)表，而結(jié)點(diǎn)表中的每個(gè)元素又包一表，它了這結(jié)點(diǎn)的有子結(jié)點(diǎn)的置，稱(chēng)為“子表”結(jié)點(diǎn)表的長(zhǎng)度即樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)，通常采用順序的方式表示而子表的長(zhǎng)度依賴(lài)于各結(jié)點(diǎn)的度數(shù)

13、，所以各不相同，一般用表示子表中結(jié)點(diǎn)的進(jìn)行的在結(jié)點(diǎn)表中需要保存子表的表頭指針順序是按其在樹(shù)中從左到右的次序53wangzhao子表的結(jié)點(diǎn)結(jié)構(gòu)定義nodeition;/nodeition是子結(jié)點(diǎn)在nist數(shù)組中的位置structEdgeNode*link;wangzhao/link則是指向子表中下一個(gè)元素（右兄弟）的指針;struct ChiTreeNode/* 結(jié)點(diǎn)表中結(jié)點(diǎn)的結(jié)構(gòu) */Daype info;/ info字段是樹(shù)結(jié)點(diǎn)的信息struct EdgeNode *children;/children是一個(gè)指針，指向子表中的第一個(gè)元素;struct EdgeNode/* 子表中結(jié)點(diǎn)的結(jié)構(gòu)

14、*/子表表示的樹(shù)結(jié)構(gòu)的定義n;/*結(jié)點(diǎn)的個(gè)數(shù)*/structChiTreeNode*nist;55wangzhao;typedef struct ChiTree *PChiTree;/*樹(shù)類(lèi)型的指針類(lèi)型*/struct ChiTree/* 樹(shù)結(jié)構(gòu) */MAXNUM;root;/* 根結(jié)點(diǎn)的下標(biāo) */子表表示的特點(diǎn)優(yōu)點(diǎn)：方便找女、找所有等缺點(diǎn)： 找父結(jié)點(diǎn)和找右兄弟麻煩，因?yàn)橐夷辰Y(jié)點(diǎn)的父結(jié)點(diǎn)必須依次檢查每個(gè)結(jié)點(diǎn)的子表中是否包含該結(jié)點(diǎn)，而要找某結(jié)點(diǎn)的右兄弟時(shí)，則首先要找到其父結(jié)點(diǎn)，然后再?gòu)母附Y(jié)點(diǎn)的子表中找尋它的右兄弟結(jié)點(diǎn)一個(gè)新樹(shù)時(shí)(createTree_chitree操 合并若干個(gè)作)也要考慮多個(gè)

15、結(jié)點(diǎn)表的合并問(wèn)題,因?yàn)榻Y(jié)點(diǎn)表通常用順序表示,合并起來(lái)比較麻煩.56wangzhao求右兄弟結(jié)點(diǎn)的位置rightSibling_chitree(PChiTree t, i;struct EdgeNode *v; for (i=0; i n; i+)p)v = t-nisti.children;while (v!=NULL)-nodeition = p)if (v-link=NULL)return 1;elsereturn v-link-nodeition;elsev = v-link; return 1;57wangzhao求父結(jié)點(diǎn)的位置parent_chitree(PChiTree t, i;

16、struct EdgeNode *v;p)for (i = 0; i n;i+)/*逐個(gè)檢查樹(shù)的各個(gè)結(jié)點(diǎn),是不是父結(jié)點(diǎn)*/v = t-nisti.children;/*若檢查的結(jié)點(diǎn)子表中有p,則返回值是該結(jié)點(diǎn)的位置*/while(v!=NULL)if (v-nodeition = p)return(i);elsev = v-link;return 1; /*無(wú)父結(jié)點(diǎn),則返回值為-1*/58wangzhao樹(shù)的表示樹(shù)的表示父指針表示法子表表示法雙親表示法孩子表示法長(zhǎng)子-兄弟表示法 孩子兄弟表示法59wangzhao長(zhǎng)子-兄弟表示法女的指針lchild和在樹(shù)的每個(gè)結(jié)點(diǎn)中設(shè)一個(gè)指向其最一個(gè)指向其右兄

17、弟的指針rsibling，其類(lèi)型定義為structCSNode;/* 樹(shù)中結(jié)點(diǎn)結(jié)構(gòu) */typedef struct CSNode *PCSNode; /*結(jié)點(diǎn)的指針類(lèi)型*/struct CSNode/* 結(jié)點(diǎn)結(jié)構(gòu)定義*/Daeinfo/* 結(jié)點(diǎn)中的元素 */PCSNode PCSNodelchild;/* 結(jié)點(diǎn)的最女的指針 */rsibling;/* 結(jié)點(diǎn)的右兄弟的指針 */;typedef typedefstruct CSNode*CSTree;/* 樹(shù)類(lèi)型定義 */CSTree*PCSTree;/* 樹(shù)類(lèi)型的指針類(lèi)型 */60wangzhao長(zhǎng)子-兄弟表示法對(duì)于任意一棵樹(shù)，可以可定義一個(gè)

18、指向樹(shù)的指針變量：PCSTreet;*t為指向樹(shù)根結(jié)點(diǎn)的指針，也叫根指針，根指針既根結(jié)點(diǎn)的位置，又用來(lái)標(biāo)識(shí)一樹(shù)；樹(shù)中其它各個(gè)結(jié)點(diǎn)按其邏輯關(guān)系用指針字段lchild和rsibling相；61wangzhao長(zhǎng)子-兄弟表示法示意圖62wangzhao長(zhǎng)子-兄弟表示法的特點(diǎn)缺點(diǎn)：找父結(jié)點(diǎn)麻煩，首先找到長(zhǎng)子，然后再找父結(jié)點(diǎn)。優(yōu)點(diǎn)：方便找、找兄弟等運(yùn)算leftChild_cstree(p)p-lchildrightSibling_cstree(p)p-rsiblingroot_cstree(t)tisNull_cstree(t)t=NULL;很容易，先由lchild找到長(zhǎng)子，再由找到全部rsibling字段逐個(gè)找右兄弟結(jié)點(diǎn)63wangzhao樹(shù)和樹(shù)林的表示樹(shù)的樹(shù)林的表示表示64