第5與二叉樹樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、結(jié)點表的合并問題,因為結(jié)點表通常用順序表示,合并起來比較麻煩.56wangzhao求右兄弟結(jié)點的位置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é)點的位置parent_chitree(PChiTree t, i;

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

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

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