數(shù)據(jù)結(jié)構(gòu)(第7章)-清華大學(xué)

第七章樹與森林⒈教學(xué)內(nèi)容：7.1樹的概念與表示7.2基本操作與存儲(chǔ)7.3樹、森林與二叉樹的轉(zhuǎn)換7.4樹或森林的遍歷7.5樹的應(yīng)用⒉教學(xué)目的：⑴深刻理解樹的定義、術(shù)語(yǔ)；⑵領(lǐng)會(huì)并掌握樹的各種存儲(chǔ)結(jié)構(gòu)；⑶熟練掌握森林與二叉樹間的相互轉(zhuǎn)換；⑷領(lǐng)會(huì)樹和森林的遍歷；⑸了解樹的簡(jiǎn)單應(yīng)用。⒊教學(xué)重點(diǎn)：⑴樹的存儲(chǔ)結(jié)構(gòu)；⑵森林與二叉樹的轉(zhuǎn)換。⒋教學(xué)難點(diǎn)：⑴森林與二叉樹的轉(zhuǎn)換；⑵判定樹；⑶等價(jià)關(guān)系與等價(jià)類問題。⒌學(xué)時(shí)安排：

4學(xué)時(shí)2/5/20231數(shù)據(jù)結(jié)構(gòu)講義7.1樹的概念與表示樹的定義及相關(guān)術(shù)語(yǔ)樹的表示2/5/20232數(shù)據(jù)結(jié)構(gòu)講義7.1.1樹的定義及相關(guān)術(shù)語(yǔ)1．樹的定義

樹（Tree）是n（n≥0）個(gè)有限數(shù)據(jù)元素的集合。當(dāng)n＝0時(shí)，稱這棵樹為空樹。在一棵非樹T中：⑴有一個(gè)特殊的數(shù)據(jù)元素稱為樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)。⑵若n>1，除根結(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分成m（m>0）個(gè)互不相交的集合T1，T2，…，Tm，其中每一個(gè)集合Ti（1≤i≤m）本身又是一棵樹。樹T1，T2，…，Tm稱為這個(gè)根結(jié)點(diǎn)的子樹?？梢钥闯?，在樹的定義中用了遞歸概念，即用樹來定義樹。因此，樹結(jié)構(gòu)的算法類同于二叉樹結(jié)構(gòu)的算法，也可以使用遞歸方法。2/5/20233數(shù)據(jù)結(jié)構(gòu)講義樹的定義還可形式化的描述為二元組的形式：

T＝（D，R）其中D為樹T中結(jié)點(diǎn)的集合，R為樹中結(jié)點(diǎn)之間關(guān)系的集合。當(dāng)樹為空樹時(shí)，D＝Φ；當(dāng)樹T不為空樹時(shí)有：

D＝{Root}∪DF其中，Root為樹T的根結(jié)點(diǎn)，DF為樹T的根Root的子樹集合。DF可由下式表示：

DF＝D1∪D2∪…∪Dm且Di∩Dj＝Φ（i≠j，1≤i≤m，1≤j≤m

當(dāng)樹T中結(jié)點(diǎn)個(gè)數(shù)n≤1時(shí)，R＝Φ；當(dāng)樹T中結(jié)點(diǎn)個(gè)數(shù)n>1時(shí)有：

R＝{<Root，ri>，i＝1，2，…，m}其中，Root為樹T的根結(jié)點(diǎn)，ri是樹T的根結(jié)點(diǎn)Root的子樹Ti的根結(jié)點(diǎn)。2/5/20234數(shù)據(jù)結(jié)構(gòu)講義下圖是一棵具有9個(gè)結(jié)點(diǎn)的樹，即T＝{A，B，C，…，H，I}，結(jié)點(diǎn)A為樹T的根結(jié)點(diǎn)，除根結(jié)點(diǎn)A之外的其余結(jié)點(diǎn)分為兩個(gè)不相交的集合：T1＝{B,D,E,F,H,I}和T2={C,G}，T1和T2構(gòu)成了結(jié)點(diǎn)A的兩棵子樹，T1和T2本身也分別是一棵樹。例如，子樹T1的根結(jié)點(diǎn)為B，其余結(jié)點(diǎn)又分為兩個(gè)不相交的集合：T11＝{D}，T12＝{E,H,I}和T13＝{F}。T11、T12和T13構(gòu)成了子樹T1的根結(jié)點(diǎn)B的三棵子樹。如此可繼續(xù)向下分為更小的子樹，直到每棵子樹只有一個(gè)根結(jié)點(diǎn)為止。2/5/20235數(shù)據(jù)結(jié)構(gòu)講義從樹的定義和圖7.1(a)的示例可以看出，樹具有下面兩個(gè)特點(diǎn)：⑴樹的根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。⑵樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。由此特點(diǎn)可知，下圖所示的都不是樹結(jié)構(gòu)。2/5/20236數(shù)據(jù)結(jié)構(gòu)講義2．相關(guān)術(shù)語(yǔ)在二叉樹中介紹的有關(guān)概念在樹中仍然適用。除此之外，再介紹兩個(gè)關(guān)于樹的術(shù)語(yǔ)。⑴有序樹和無序樹。如果一棵樹中結(jié)點(diǎn)的各子樹叢左到右是有次序的，即若交換了某結(jié)點(diǎn)各子樹的相對(duì)位置，則構(gòu)成不同的樹，稱這棵樹為有序樹；反之，則稱為無序樹。⑵森林。零棵或有限棵不相交的樹的集合稱為森林。自然界中樹和森林是不同的概念，但在數(shù)據(jù)結(jié)構(gòu)中，樹和森林只有很小的差別。任何一棵樹，刪去根結(jié)點(diǎn)就變成了森林。2/5/20237數(shù)據(jù)結(jié)構(gòu)講義7.1.2樹的表示樹的表示方法有四種，各用于不同的目的。1．直觀表示法樹的直觀表示法就是以倒著的分支樹的形式表示，下圖就是一棵樹的直觀表示。其特點(diǎn)就是對(duì)樹的邏輯結(jié)構(gòu)的描述非常直觀。是數(shù)據(jù)結(jié)構(gòu)中最常用的樹的描述方法。2/5/20238數(shù)據(jù)結(jié)構(gòu)講義2．嵌套集合表示法所謂嵌套集合是指一些集合的集體，對(duì)于其中任何兩個(gè)集合，或者不相交，或者一個(gè)包含另一個(gè)。用嵌套集合的形式表示樹，就是將根結(jié)點(diǎn)視為一個(gè)大的集合，其若干棵子樹構(gòu)成這個(gè)大集合中若干個(gè)互不相交的子集，如此嵌套下去，即構(gòu)成一棵樹的嵌套集合表示。下圖就是一棵樹的嵌套集合表示。2/5/20239數(shù)據(jù)結(jié)構(gòu)講義3．凹入表示法

樹的凹入表示法如左圖所示。4．廣義表表示法樹用廣義表表示，就是將根作為由子樹森林組成的表的名字寫在表的左邊，這樣依次將樹表示出來。(A(B(D,E(H,I),F),C(G)))2/5/202310數(shù)據(jù)結(jié)構(gòu)講義7.2樹的基本操作與存儲(chǔ)樹的基本操作樹的存儲(chǔ)結(jié)構(gòu)2/5/202311數(shù)據(jù)結(jié)構(gòu)講義7.2.1樹的基本操作樹的基本操作通常有以下幾種：⑴Initiate（t）初始化一棵空樹t。⑵Root（x）求結(jié)點(diǎn)x所在樹的根結(jié)點(diǎn)。⑶Parent（t，x）求樹t中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。⑷Child（t，x，i）求樹t中結(jié)點(diǎn)x的第i個(gè)孩子結(jié)點(diǎn)。⑸RightSibling（t，x）求樹t中結(jié)點(diǎn)x的第一個(gè)右邊兄弟結(jié)點(diǎn)。⑹Insert（t，x，i，s）把以s為根結(jié)點(diǎn)的樹插入到樹t中作為結(jié)點(diǎn)x的第i棵子樹。⑺Delete（t，x，i）在樹t中刪除結(jié)點(diǎn)x的第i棵子樹。⑻Tranverse（t）是樹的遍歷操作，即按某種方式訪問樹t中的每個(gè)結(jié)點(diǎn)，且使每個(gè)結(jié)點(diǎn)只被訪問一次。2/5/202312數(shù)據(jù)結(jié)構(gòu)講義7.2.2樹的存儲(chǔ)結(jié)構(gòu)1．雙親表示法

由樹的定義可以知道，樹中的每個(gè)結(jié)點(diǎn)都有唯一的一個(gè)雙親結(jié)點(diǎn)，根據(jù)這一特性，可用一組連續(xù)的存儲(chǔ)空間（一維數(shù)組）存儲(chǔ)樹中的各個(gè)結(jié)點(diǎn)，數(shù)組中的一個(gè)元素表示樹中的一個(gè)結(jié)點(diǎn)，數(shù)組元素為結(jié)構(gòu)體類型，其中包括結(jié)點(diǎn)本身的信息以及結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的序號(hào)，樹的這種存儲(chǔ)方法稱為雙親表示法。其存儲(chǔ)表示可描述為：#defineMAXNODE<樹中結(jié)點(diǎn)的最大個(gè)數(shù)>

typedefstruct{elemtypedata;intparent;}NodeType;NodeTypet[MAXNODE];2/5/202313數(shù)據(jù)結(jié)構(gòu)講義下圖所示為樹的雙親表示。圖中用parent域的值為-1表示該結(jié)點(diǎn)無雙親結(jié)點(diǎn)，即該結(jié)點(diǎn)是一個(gè)根結(jié)點(diǎn)。2/5/202314數(shù)據(jù)結(jié)構(gòu)講義樹的雙親表示法對(duì)于實(shí)現(xiàn)Parent（t，x）操作和Root（x）操作很方便。但若求某結(jié)點(diǎn)的孩子結(jié)點(diǎn)，即實(shí)現(xiàn)Child（t，x，i）操作時(shí)，則需查詢整個(gè)數(shù)組。此外，這種存儲(chǔ)方式不能夠反映各兄弟結(jié)點(diǎn)之間的關(guān)系，所以實(shí)現(xiàn)RightSibling（t，x）操作也比較困難。在實(shí)際中，如果需要實(shí)現(xiàn)這些操作，可在結(jié)點(diǎn)結(jié)構(gòu)中增設(shè)存放第一個(gè)孩子的域和存放第一個(gè)右兄弟的域，就能較方便地實(shí)現(xiàn)上述操作了。2/5/202315數(shù)據(jù)結(jié)構(gòu)講義2．孩子表示法⑴多重鏈表法由于樹中每個(gè)結(jié)點(diǎn)都有零個(gè)或多個(gè)孩子結(jié)點(diǎn)，因此，可以令每個(gè)結(jié)點(diǎn)包括一個(gè)結(jié)點(diǎn)信息域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)，通過各個(gè)指針域值反映出樹中各結(jié)點(diǎn)之間的邏輯關(guān)系。在這種表示法中，樹中每個(gè)結(jié)點(diǎn)有多個(gè)指針域，形成了多條鏈表，所以這種方法又常稱為多重鏈表法。在一棵樹中，各結(jié)點(diǎn)的度數(shù)各異，因此結(jié)點(diǎn)的指針域個(gè)數(shù)的設(shè)置有兩種方法：①每個(gè)結(jié)點(diǎn)指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度數(shù)；②每個(gè)結(jié)點(diǎn)指針域的個(gè)數(shù)等于樹的度數(shù)。2/5/202316數(shù)據(jù)結(jié)構(gòu)講義⑵孩子鏈表表示法孩子鏈表法是將樹按如下圖所示的形式存儲(chǔ)。其主體是一個(gè)與結(jié)點(diǎn)個(gè)數(shù)一樣大小的一維數(shù)組，數(shù)組的每一個(gè)元素有兩個(gè)域組成，一個(gè)域用來存放結(jié)點(diǎn)信息，另一個(gè)用來存放指針，該指針指向由該結(jié)點(diǎn)孩子組成的單鏈表的首位置。單鏈表的結(jié)構(gòu)也由兩個(gè)域組成，一個(gè)存放孩子結(jié)點(diǎn)在一維數(shù)組中的序號(hào)，另一個(gè)是指針域，指向下一個(gè)孩子。2/5/202317數(shù)據(jù)結(jié)構(gòu)講義在孩子表示法中查找雙親比較困難，查找孩子卻十分方便，故適用于對(duì)孩子操作多的應(yīng)用。這種存儲(chǔ)表示可描述為：#defineMAXNODE<樹中結(jié)點(diǎn)的最大個(gè)數(shù)>

typedefstructChildNode{intchildcode;structChildNode*nextchild;};

typedefstruct{elemtypedata;structChildNode*firstchild;}NodeType;NodeTypet[MAXNODE];2/5/202318數(shù)據(jù)結(jié)構(gòu)講義3．雙親孩子表示法雙親表示法是將雙親表示法和孩子表示法相結(jié)合的結(jié)果。其仍將各結(jié)點(diǎn)的孩子結(jié)點(diǎn)分別組成單鏈表，同時(shí)用一維數(shù)組順序存儲(chǔ)樹中的各結(jié)點(diǎn)，數(shù)組元素除了包括結(jié)點(diǎn)本身的信息和該結(jié)點(diǎn)的孩子結(jié)點(diǎn)鏈表的頭指針之外，還增設(shè)一個(gè)域，存儲(chǔ)該結(jié)點(diǎn)雙親結(jié)點(diǎn)在數(shù)組中的序號(hào)。下圖所示為采用這種方法的存儲(chǔ)示意圖。2/5/202319數(shù)據(jù)結(jié)構(gòu)講義4．孩子兄弟表示法這是一種常用的存儲(chǔ)結(jié)構(gòu)。其方法是這樣的：在樹中，每個(gè)結(jié)點(diǎn)除其信息域外，再增加兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)的指針。在這種存儲(chǔ)結(jié)構(gòu)下，樹中結(jié)點(diǎn)的存儲(chǔ)表示可描述為：

typedefstructTreeNode{elemtypedata;structTreeNode*lchild;structTreeNode*nextsibling;}NodeType,*CSTree;2/5/202320數(shù)據(jù)結(jié)構(gòu)講義下圖給出采用孩子兄弟表示法時(shí)的存儲(chǔ)示意圖。從樹的孩子兄弟表示法可以看到，如果設(shè)定一定規(guī)則，就可用二叉樹結(jié)構(gòu)表示樹和森林，這樣，對(duì)樹的操作實(shí)現(xiàn)就可以借助二叉樹存儲(chǔ)，利用二叉樹上的操作來實(shí)現(xiàn)。2/5/202321數(shù)據(jù)結(jié)構(gòu)講義7.3樹、森林與二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹二叉樹轉(zhuǎn)換為樹和森林2/5/202322數(shù)據(jù)結(jié)構(gòu)講義7.3.1樹轉(zhuǎn)換為二叉樹將一棵樹轉(zhuǎn)換為二叉樹的方法是：⑴樹中所有相鄰兄弟之間加一條連線。⑵對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線。⑶以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之結(jié)構(gòu)層次分明。

由上面的轉(zhuǎn)換可以看出，在二叉樹中，左分支上的各結(jié)點(diǎn)在原來的樹中是父子關(guān)系，而右分支上的各結(jié)點(diǎn)在原來的樹中是兄弟關(guān)系。由于樹的根結(jié)點(diǎn)沒有兄弟，所以變換后的二叉樹的根結(jié)點(diǎn)的右孩子必為空。2/5/202323數(shù)據(jù)結(jié)構(gòu)講義給出了轉(zhuǎn)換為二叉樹的轉(zhuǎn)換過程示意圖。2/5/202324數(shù)據(jù)結(jié)構(gòu)講義7.3.2森林轉(zhuǎn)換為二叉樹由森林的概念可知，森林是若干棵樹的集合，只要將森林中各棵樹的根視為兄弟，森林同樣可以用二叉樹表示。森林轉(zhuǎn)換為二叉樹的方法如下：⑴將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。⑵第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連起來后，此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。2/5/202325數(shù)據(jù)結(jié)構(gòu)講義這一方法可形式化描述為：如果F＝{T1，T2，…，Tm}是森林，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹B＝（root，LB，RB）。⑴若F為空，即m＝0，則B為空樹；⑵若F非空，即m≠0，則B的根root即為森林中第一棵樹的根Root(T1)；B的左子樹LB是從T1中根結(jié)點(diǎn)的子樹森林F1＝{T11，T12，…，T1m1}轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林F’＝{T2，T3，…，Tm}轉(zhuǎn)換而成的二叉樹。2/5/202326數(shù)據(jù)結(jié)構(gòu)講義下圖給出森林及其轉(zhuǎn)換為二叉樹的過程。2/5/202327數(shù)據(jù)結(jié)構(gòu)講義7.3.3二叉樹轉(zhuǎn)換為樹和森林樹和森林都可以轉(zhuǎn)換為二叉樹，這一轉(zhuǎn)換過程是可逆的，即可以將一棵二叉樹還原為樹或森林，具體方法如下：⑴若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子……都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來；⑵刪去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；⑶整理由⑴、⑵兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。2/5/202328數(shù)據(jù)結(jié)構(gòu)講義這一方法可形式化描述為：如果B＝（root，LB，RB）是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F＝{T1，T2，…，Tm}。⑴若B為空，則F為空；⑵若B非空，則森林中第一棵樹T1的根ROOT（T1）即為B的根root；T1中根結(jié)點(diǎn)的子樹森林F1是由B的左子樹LB轉(zhuǎn)換而成的森林；F中除T1之外其余樹組成的森林F’＝{T2，T3，…，Tm}是由B的右子樹RB轉(zhuǎn)換而成的森林。2/5/202329數(shù)據(jù)結(jié)構(gòu)講義下圖給出一棵二叉樹還原為森林的過程示意。2/5/202330數(shù)據(jù)結(jié)構(gòu)講義7.4樹和森林的遍歷樹的遍歷森林的遍歷2/5/202331數(shù)據(jù)結(jié)構(gòu)講義7.4.1樹的遍歷1．先根遍歷先根遍歷的定義為：⑴訪問根結(jié)點(diǎn)；⑵按照從左到右的順序先根遍歷根結(jié)點(diǎn)的每一棵子樹。按照樹的先根遍歷的定義，對(duì)上圖所示的樹進(jìn)行先根遍歷，得到的結(jié)果序列為：

ABEFCDG2/5/202332數(shù)據(jù)結(jié)構(gòu)講義2．后根遍歷

后根遍歷的定義為：⑴按照從左到右的順序后根遍歷根結(jié)點(diǎn)的每一棵子樹。⑵訪問根結(jié)點(diǎn)；按照樹的后根遍歷的定義，對(duì)下圖所示的樹進(jìn)行后根遍歷，得到的結(jié)果序列為：

EFBCGDA2/5/202333數(shù)據(jù)結(jié)構(gòu)講義7.4.2森林的遍歷1．前序遍歷

前序遍歷的定義為：⑴訪問森林中第一棵樹的根結(jié)點(diǎn)；⑵前序遍歷第一棵樹的根結(jié)點(diǎn)的子樹；⑶前序遍歷去掉第一棵樹后的子森林。對(duì)于下圖所示的森林進(jìn)行前序遍歷，得到的結(jié)果序列為：

ABCDEFGHJIK2/5/202334數(shù)據(jù)結(jié)構(gòu)講義2.中序遍歷中序遍歷的定義為：⑴中序遍歷第一棵樹的根結(jié)點(diǎn)的子樹；⑵訪問森林中第一棵樹的根結(jié)點(diǎn)；⑶中序遍歷去掉第一棵樹后的子森林。對(duì)于下圖所示的森林進(jìn)行中序遍歷，得到的結(jié)果序列為：

BADEFCJHKIG2/5/202335數(shù)據(jù)結(jié)構(gòu)講義7.5樹的應(yīng)用判定樹集合的表示關(guān)系等價(jià)求等價(jià)類問題2/5/202336數(shù)據(jù)結(jié)構(gòu)講義7.5.1判定樹在實(shí)際應(yīng)用中，樹可用于判定問題的描述和解決。設(shè)有八枚硬幣，分別表示為a，b，c，d，e，f，g，h，其中有一枚且僅有一枚硬幣是偽造的，假硬幣的重量與真硬幣的重量不同，可能輕，也可能重?，F(xiàn)要求以天平為工具，用最少的比較次數(shù)挑選出假硬幣，并同時(shí)確定這枚硬幣的重量比其它真硬幣是輕還是重。問題的解決過程如下圖所示，解決過程中的一系列判斷構(gòu)成了樹結(jié)構(gòu)，我們稱這樣的樹為判定樹。2/5/202337數(shù)據(jù)結(jié)構(gòu)講義7.5.2集合的表示集合是一種常用的數(shù)據(jù)表示方法，對(duì)集合可以作多種操作，假設(shè)集合S由若干個(gè)元素組成，可以按照某一規(guī)則把集合S劃分成若干個(gè)互不相交的子集合，例如，集合S＝{1，2，3，4，5，6，7，8，9，10}，可以被分成如下三個(gè)互不相交的子集合：

S1＝{1，2，4，7}S2＝{3，5，8}S3＝{6，9，10}

集合{S1，S2，S3}就被稱為集合S的一個(gè)劃分。此外，在集合上還有最常用的一些運(yùn)算，比如集合的交、并、補(bǔ)、差以及判定一個(gè)元素是否是集合中的元素，等等。2/5/202338數(shù)據(jù)結(jié)構(gòu)講義為了有效地對(duì)集合執(zhí)行各種操作，可以用樹結(jié)構(gòu)表示集合。用樹中的一個(gè)結(jié)點(diǎn)表示集合中的一個(gè)元素，樹結(jié)構(gòu)采用雙親表示法存儲(chǔ)。例如，集合S1、S2和S3可分別表示為圖(a)、(b)、(c)所示的結(jié)構(gòu)。將它們作為集合S的一個(gè)劃分，存儲(chǔ)在一維數(shù)組中，如下圖所示。2/5/202339數(shù)據(jù)結(jié)構(gòu)講義數(shù)組元素結(jié)構(gòu)的存儲(chǔ)表示描述如下：

typedefstruct{elemtypedata;intparent;}NodeType；

其中data域存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)，parent域?yàn)橹赶螂p親結(jié)點(diǎn)的指針，即存儲(chǔ)雙親結(jié)點(diǎn)在數(shù)組中的序號(hào)。當(dāng)集合采用這種存儲(chǔ)表示方法時(shí)，很容易實(shí)現(xiàn)集合的一些基本操作。例如，求兩個(gè)集合的并集，就可以簡(jiǎn)單地把一個(gè)集合的樹根結(jié)點(diǎn)作為另一個(gè)集合的樹根結(jié)點(diǎn)的孩子結(jié)點(diǎn)。如求上述集合S1和S2的并集，可以表示為：

S1∪S2＝{1，2，3，4，5，7，8}2/5/202340數(shù)據(jù)結(jié)構(gòu)講義該結(jié)果用樹結(jié)構(gòu)表示如下圖所示。2/5/202341數(shù)據(jù)結(jié)構(gòu)講義集合并運(yùn)算的算法實(shí)現(xiàn)如下：voidUnion（NodeTypea[]，inti，intj）

/*合并以數(shù)組a的第i個(gè)元素和第j個(gè)元素為樹根結(jié)點(diǎn)的集合*/{if(a[i].parent!=-1||a[j].parent!=-1)

{printf(“\n調(diào)用參數(shù)不正確”)；

return；}a[j].parent=i;/*將i置為兩個(gè)集合共同的根結(jié)點(diǎn)*/}2/5/202342數(shù)據(jù)結(jié)構(gòu)講義如果要查找某個(gè)元素所在的集合，可以沿著該元素的雙親域向上查，當(dāng)查到某個(gè)元素的雙親域值為－1時(shí)，該元素就是所查元素所屬集合的樹根結(jié)點(diǎn)，算法如下：intFind（NodeTypea[]，elemtypex）/*在數(shù)組a中查找值為x的元素所屬的集合，若找到，返回樹根結(jié)點(diǎn)在數(shù)組a中的序號(hào)；否則，返回－1。常量MAXNODE為數(shù)組a的最大容量*/{inti,j;

i=0;while(i<MAXNODE&&a[i].data!=x)

i++;if(i>=MAXNODE)

return–1;

/*值為x的元素不屬于該組集合，返回－1*/

j=i;while(a[j].parent!=-1)j=a[j].parent;returnj;/*j為該集合的樹根結(jié)點(diǎn)在數(shù)組a中的序號(hào)*/}2/5/202343數(shù)據(jù)結(jié)構(gòu)講義7.5.3關(guān)系等價(jià)求等價(jià)類問題

1.問題：已知集合S及其上的等價(jià)關(guān)系R，求R在S上的一個(gè)劃分{S1,S2,…,Sn}，其中，S1,S2,…,Sn分別為R的等價(jià)類，它們滿足：

Si＝S且Si∩Sj＝ф(i≠j)設(shè)集合S中有n個(gè)元素，關(guān)系R中有m個(gè)序偶對(duì)。2/5/202344數(shù)據(jù)結(jié)構(gòu)講義2.算法思想：⑴令S中每個(gè)元素各自形成一個(gè)單元素的子集，記作S1，S2，…，Sn；⑵重復(fù)讀入m個(gè)序偶對(duì)，對(duì)每個(gè)