樹(shù)與二叉樹(shù)ppt課件

1、第六章 樹(shù)和二叉樹(shù) 樹(shù)是一類(lèi)重要的非線性數(shù)據(jù)構(gòu)造，是以分支關(guān)系定義的層次構(gòu)造5.1 樹(shù)的定義定義定義：樹(shù)(tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱(chēng)為樹(shù)的根(root)當(dāng)n1時(shí)，其他結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)(subtree)特點(diǎn)：樹(shù)中至少有一個(gè)結(jié)點(diǎn)根樹(shù)中各子樹(shù)是互不相交的集合A只需根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)根本術(shù)語(yǔ)結(jié)點(diǎn)(node)表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及假設(shè)干指向其子樹(shù)的分支結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹(shù)數(shù)葉子(leaf)度為0的結(jié)點(diǎn)孩子(child)結(jié)

2、點(diǎn)子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的兄弟(sibling)同一雙親的孩子樹(shù)的度一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層深度(depth)樹(shù)中結(jié)點(diǎn)的最大層次數(shù)森林(forest)m(m0)棵互不相交的樹(shù)的集合ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖

3、先bacghdefijabdeijfcghijdfghabcea ( b ( d, e ( i, j ), c ( g, h ) ) )5.2 二叉樹(shù)定義定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn))二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能恣意顛倒根本形狀A(yù)只需根結(jié)點(diǎn)的二叉樹(shù)空二叉樹(shù)AB右子樹(shù)為空AB左子樹(shù)為空ABC左、右子樹(shù)均非空二叉樹(shù)性質(zhì)性質(zhì)1：) 1(21iii個(gè)結(jié)點(diǎn)層上至多有在二叉樹(shù)的第證明：用歸納法證明之 i=1時(shí)，只需一個(gè)根結(jié)點(diǎn)， 是對(duì)的 假設(shè)對(duì)一切j(

4、1j1，那么其雙親是i/2u (2) 假設(shè)2in，那么結(jié)點(diǎn)i無(wú)左孩子；假設(shè)2in，那么其左孩子是2iu (3) 假設(shè)2i+1n，那么結(jié)點(diǎn)i無(wú)右孩子；假設(shè)2i+1n，那么其右孩子是2i+15.3 樹(shù)的存儲(chǔ)構(gòu)造樹(shù)的存儲(chǔ)構(gòu)造雙親表示法實(shí)現(xiàn)：定義構(gòu)造數(shù)組存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn)：找雙親容易，找孩子難typedef struct node datatype data; int parent;JD;JD tM;abcdefhgiacdefghib012235551096012345789dataparent0號(hào)單元不用或存結(jié)點(diǎn)個(gè)數(shù)

5、如何找孩子結(jié)點(diǎn)v孩子表示法v多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹(shù)的根v結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹(shù)的度Dv結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度ddata child1 child2 . childDdata degree child1 child2 . childdl孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)，再用含n個(gè)元素的構(gòu)造數(shù)組指向每個(gè)孩子鏈表孩子結(jié)點(diǎn)：typedef struct node int child; /該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo) struct node *next; /指向下一孩子結(jié)點(diǎn) JD;表頭結(jié)點(diǎn)：typedef struct tnode datatyp

6、e data; /數(shù)據(jù)域 struct node *fc; /指向第一個(gè)孩子結(jié)點(diǎn) TD; TD tM; /t0不用abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結(jié)點(diǎn)l帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiv孩子兄弟表示法二叉樹(shù)表示法v實(shí)現(xiàn)：用二叉鏈表作樹(shù)的存儲(chǔ)構(gòu)造，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)v特點(diǎn)v操作容易v破壞了樹(shù)的層次typedef struct node datatype data; struct node *fch, *nsib;JD;abcdefhgi a b c d e f g h i二叉樹(shù)的存儲(chǔ)構(gòu)造順序存儲(chǔ)構(gòu)造實(shí)現(xiàn)：按滿二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依