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

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

2、247589109105負(fù)數(shù)表示根結(jié)點；非負(fù)數(shù)表示雙親結(jié)點的下標(biāo)。2.集合運算（1）查找某個元素所在的集合（用根結(jié)點表示）查找某個元素所在的集合（用根結(jié)點表示）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é)點在數(shù)組S中的下標(biāo)

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

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