第四章樹與樹的表示(五)

1、4.6.3 集合及運(yùn)算11.集合的表示 集合運(yùn)算：交、并、補(bǔ)、差，判定一個(gè)元素是否屬于某一集合 并查集：集合并、查某元素屬于什么集合 并查集問題中集合存儲如何實(shí)現(xiàn)？ 可以用樹結(jié)構(gòu)表示集合，樹的每個(gè)結(jié)點(diǎn)代表一個(gè)集合元素例如，有三個(gè)整數(shù)集合S1=1,2,4,7S2=3,5,8S3=6,9,10集合名 指針雙親表示法：孩子指向雙親。S1S2S32467538910 采用數(shù)組存儲形式下標(biāo)01234Data12345Parent-10-102數(shù)組中每個(gè)元素的類型描述為：typedef struct ElementType Data;int Parent; SetType;56-1136670788925

2、247589109105負(fù)數(shù)表示根結(jié)點(diǎn)；非負(fù)數(shù)表示雙親結(jié)點(diǎn)的下標(biāo)。2.集合運(yùn)算（1）查找某個(gè)元素所在的集合（用根結(jié)點(diǎn)表示）查找某個(gè)元素所在的集合（用根結(jié)點(diǎn)表示）int Find( SetType S , ElementType X )/* 在數(shù)組S中查找值為X的元素所屬的集合 */* MaxSize是全局變量，為數(shù)組S的最大長度 */int i;for ( i=0; i = MaxSize ) return -1; /* 未找到X，返回-1 */for( ; Si.Parent = 0; i = Si.Parent ) ;return i; /* 找到X所屬集合，返回樹根結(jié)點(diǎn)在數(shù)組S中的下標(biāo)

3、*/（2） 集合的并運(yùn)算 分別找到X1和X2兩個(gè)元素所在集合樹的根結(jié)點(diǎn) 如果它們不同根，則將其中一個(gè)根結(jié)點(diǎn)的父結(jié)點(diǎn)指針設(shè)置成另一個(gè)根結(jié)點(diǎn)的數(shù)組下標(biāo)。void Union( SetType S , ElementType X1, ElementType X2 )int Root1, Root2;當(dāng)x1和x2不屬于同一子集時(shí)，才需要合并Root1 = Find(S, X1);Root2 = Find(S, X2);if（ Root1 != Root2 ）SRoot2.Parent = Root1;改成-7。表示集下標(biāo)dataParent合有7個(gè)元素0112-10162302473910340455

4、62-1586789789100255改成-3。表示集合有3個(gè)元素為了改善合并以后的查找性能，可以采用小的集合合并到相對大的集合中。（修改Union函數(shù)）作業(yè)：1.課本154頁題目4.6.2.課本154頁題目4.7.3. 一棵深度為h的滿k叉樹有如下性質(zhì)： 第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。 如果按層次順序(同層自左至右)從1開始對全部結(jié)點(diǎn)編號，問： 各層的結(jié)點(diǎn)數(shù)是多少? 編號為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號是多少? 編號為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)(若存在)的編號是多少? 編號為i的結(jié)點(diǎn)的有右兄弟的條件是什么? 其右兄弟的編號是多少? 4.在最大堆 97,76,65,50,49,13,27中插入83后，該最大堆為：.A.97,76,65,83,49,13,27,50B.97,83,6