數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價問題(已修改)
2025-07-03 08:45 本頁面
【正文】 上堂課要點回顧 森林與二叉樹的轉(zhuǎn)換 ? 樹轉(zhuǎn)換為二叉樹 ? 二叉樹轉(zhuǎn)換為樹 ? 森林轉(zhuǎn)換為二叉樹 ? 二叉樹轉(zhuǎn)換為森林 森林的遍歷 ? 先根深度優(yōu)先遍歷 ? 后根深度優(yōu)先遍歷 二叉樹的應用 ? 哈夫曼樹與哈夫曼編碼 第 十二 次 課 閱讀： 朱戰(zhàn)立， 第 200204頁 習題： 作業(yè) 11 數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容 二叉樹 數(shù)據(jù)結(jié)構(gòu)的應用 等價問題 （ 并查集 ） 基本概念 ? 等價關(guān)系 (equivalence relation)：假定有一具有 n個元素的非空集合 S={1， 2， … ， n}，另有一個具有 r個關(guān)系的集合 R={(i1,j1),(i2,j2),…,( ir,jr)}，若 R滿足： ? 對所有的 i∈ S，有 (i,i)∈ R時，即關(guān)系是自反的 ? 對所有的 i， j∈ S，當且僅當 (i,j)∈ R時 (j,i)∈ R，即關(guān)系是對稱的 ? 對所有的 i， j∈ S，若 (i,j)∈ R且 (j,k)∈ R，則有(i,j)∈ R，即關(guān)系是傳遞的 則稱關(guān)系 R是定義在 S上的一個 等價關(guān)系 ，其中， i1等價于 j1， i2等價于 j2， …… ， ir等價于 jr。 ? 等價類 (equivalence classes)：設(shè) R是定義在非空集合 S上的一個的等價關(guān)系， 稱 是 x的等價類 。 R可產(chǎn)生集合 S的唯一劃分 ，即可以按 R將 S劃分為若干不相交的子集 S1， S2， … ，這些子集 Si稱為 S的 R等價類 。 簡言之 ， 等價類是集合中相互等價的元素的最大子集合 。 }|{][, x R ySyyxSx R ?????Rx][在一些應用問題中，給出各個元素之間的聯(lián)系，要求將這些元素分成幾個集合，每個集合中的元素直接或間接有聯(lián)系。在這類問題中主要涉及的是對集合的合并和查找，因此將這種集合稱為 并查集 。 例如：親戚 或許你并不知道，你的某個朋友是你的親戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子。如果能得到完整的家譜，判斷兩個人是否是親戚應該是可行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗親戚關(guān)系實非人力所能及。在這種情況下，最好的幫手是計算機。 為了將問題簡化，你將得到一些親戚關(guān)系的信息，如同Xuebin和 Grant是親戚， Grant和 Tension是親戚等，從這些信息中，你可以推出 Xuebin和 Tension是親戚。請寫一個程序，對于我
教學教案相關(guān)推薦
鄂ICP備17016276號-1