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

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

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

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

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