【正文】 表類(lèi)的聲明 廣義線(xiàn)性表 —— 廣義表 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義表的操作 —— 建立廣義表 template class T Lists::Lists(Lists ls1,Lists ls2) { ls = new GLNode lstag = 1。 ls = ls1。 ls = ls2。 } 廣義線(xiàn)性表 —— 廣義表 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義表的操作 —— 求廣義表的深度 template class T int Lists::Depth(GLNodeT *ls) { if (ls==NULL) return 1。 if (lstag==0) return 0。 max=0。 p = ls。 while (p) { dep = Depth(p)。 if (depmax) max = dep。 p = p。 } return max+1。 } 廣義線(xiàn)性表 —— 廣義表 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義線(xiàn)性表 多維數(shù)組 廣義表 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) ⑴數(shù)組的定義 ⑵基本操作 ⑶ ADT定義 順序存儲(chǔ) 壓縮存儲(chǔ) 特殊矩陣 對(duì)稱(chēng)矩陣 三角矩陣 對(duì)角矩陣 稀疏矩陣 按行優(yōu)先 按列優(yōu)先 尋址的計(jì)算方法 ⑴基本概念 廣義表定義 表頭、表尾 長(zhǎng)度、深度 ⑵ ADT定義 鏈接存儲(chǔ) 頭尾表示法 轉(zhuǎn)置算法 第四章 廣義線(xiàn)性表 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 ?樹(shù)的邏輯結(jié)構(gòu) ?樹(shù)的存儲(chǔ)結(jié)構(gòu) ?二叉樹(shù)的邏輯結(jié)構(gòu) ?二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) ?樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 ?哈夫曼樹(shù) 第 5 章 樹(shù)和二叉樹(shù) 本章的主要內(nèi)容是 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹(shù)的定義 樹(shù)： n（ n≥ 0） 個(gè) 結(jié)點(diǎn) 的有限 集合 。當(dāng) n＝ 0時(shí)，稱(chēng)為空樹(shù)；任意一棵非空樹(shù)滿(mǎn)足以下條件： ⑴ 有且僅有一個(gè)特定的稱(chēng)為 根 的結(jié)點(diǎn)； ⑵ 當(dāng) n＞ 1時(shí) ， 除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成 m（ m0） 個(gè) 互不相交 的有限集合 T1,T2,… ,Tm， 其中每個(gè)集合又是一棵樹(shù) ， 并稱(chēng)為這個(gè)根結(jié)點(diǎn)的 子樹(shù) 。 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的定義是采用遞歸方法 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 (a) 一棵樹(shù)結(jié)構(gòu) (b)一個(gè)非樹(shù)結(jié)構(gòu) (c)一個(gè)非樹(shù)結(jié)構(gòu) 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的定義 A C B G F E D H I A C B G F D A C B G F D E 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹(shù)的應(yīng)用舉例 —— 文件結(jié)構(gòu) 樹(shù)的邏輯結(jié)構(gòu) My Computer C: D: E: etc WINDOWS Program Files Picture Music ?? ?? ?? ?? ?? ?? ?? ?? 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹(shù)的基本術(shù)語(yǔ) 結(jié)點(diǎn)的度： 結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。 樹(shù)的度： 樹(shù)中各結(jié)點(diǎn)度的最大值。 樹(shù)的邏輯結(jié)構(gòu) C G B D E F K L H M I J A 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹(shù)的邏輯結(jié)構(gòu) 葉子結(jié)點(diǎn)： 度為 0的結(jié)點(diǎn)，也稱(chēng)為終端結(jié)點(diǎn)。 分支結(jié)點(diǎn)： 度不為 0的結(jié)點(diǎn)，也稱(chēng)為非終端結(jié)點(diǎn)。 C G B D E F K L H M I J A 樹(shù)的基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 孩子、雙親： 樹(shù)中某結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)稱(chēng)為這個(gè)結(jié)點(diǎn)的 孩子結(jié)點(diǎn) ，這個(gè)結(jié)點(diǎn)稱(chēng)為它孩子結(jié)點(diǎn)的 雙親結(jié)點(diǎn) ； 兄弟： 具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱(chēng)為兄弟。 樹(shù)的邏輯結(jié)構(gòu) C G B D E F K L H M I J A 樹(shù)的基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 路徑： 如果樹(shù)的結(jié)點(diǎn)序列 n1, n2, …, nk有如下關(guān)系：結(jié)點(diǎn) ni是 ni+1的雙親（ 1=ik） ，則把 n1, n2, …, nk稱(chēng)為一條由 n1至 nk的路徑；路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱(chēng)為路徑長(zhǎng)度 。 C G B D E F K L H M I J A 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 祖先、子孫： 在樹(shù)中，如果有一條路徑從結(jié)點(diǎn) x到結(jié)點(diǎn) y， 那么 x就稱(chēng)為 y的祖先，而 y稱(chēng)為 x的子孫。 樹(shù)的邏輯結(jié)構(gòu) C G B D E F K L H M I J A 樹(shù)的基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 結(jié)點(diǎn)所在層數(shù)： 根結(jié)點(diǎn)的層數(shù)為 1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第 k層，則其孩子結(jié)點(diǎn)在第 k+1層。 樹(shù)的深度： 樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)，也稱(chēng) 高度 。 1層 2層 4層 3層 高度＝ 4 C G B D E F K L H M I J C 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 C B D E F K L H J A 7 1 2 3 4 5 6 8 9 10 層序編號(hào)： 將樹(shù)中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從 1開(kāi)始的連續(xù)自然數(shù)。 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 有序樹(shù)、無(wú)序樹(shù)： 如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，稱(chēng)這棵樹(shù)為有序樹(shù)；反之，稱(chēng)為無(wú)序樹(shù)。 數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹(shù) 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) A C B G F E D A C B G F E D 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 C B D E F K L H J 森林： m (m≥0)棵互不相交的樹(shù)的集合。 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) A 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 同構(gòu)： 對(duì)兩棵樹(shù) ， 若通過(guò)對(duì)結(jié)點(diǎn)適當(dāng)?shù)刂孛?，就可以使這兩棵樹(shù)完全相等 （ 結(jié)點(diǎn)對(duì)應(yīng)相等 ， 結(jié)點(diǎn)對(duì)應(yīng)關(guān)系也相等 ） ， 則稱(chēng)這兩棵樹(shù)同構(gòu) 。 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) A C B G F E D D A E C F B G 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹(shù)結(jié)構(gòu)和線(xiàn)性結(jié)構(gòu)的比較 線(xiàn)性結(jié)構(gòu) 樹(shù)結(jié)構(gòu) 第 一 個(gè)數(shù)據(jù)元素 根結(jié)點(diǎn)（只有 一 個(gè)） 無(wú)前驅(qū) 無(wú)雙親 最后 一 個(gè)數(shù)據(jù)元素 葉子結(jié)點(diǎn) (可以有 多 個(gè) ) 無(wú)后繼 無(wú)孩子 其它數(shù)據(jù)元素 其它結(jié)點(diǎn) 一個(gè)前驅(qū) ,一個(gè)后繼 一個(gè)雙親 ,多個(gè)孩子 一對(duì)一 一對(duì)多 樹(shù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹(shù)的抽象數(shù)據(jù)類(lèi)型定義 ADT Tree Data 樹(shù)是由一個(gè)根結(jié)點(diǎn)和若干棵子樹(shù)構(gòu)成， 樹(shù)中結(jié)點(diǎn)具有相同數(shù)據(jù)類(lèi)型及層次關(guān)系 Operation InitTree 前置條件：樹(shù)不存在 輸入：無(wú) 功能：初始化一棵樹(shù) 輸出：無(wú) 后置條件：構(gòu)造一個(gè)空樹(shù) 樹(shù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 DestroyTree 前置條件：樹(shù)已存在 輸入：無(wú) 功能：銷(xiāo)毀一棵樹(shù) 輸出：無(wú) 后置條件：釋放該樹(shù)占用的存儲(chǔ)空間 Root 前置條件：樹(shù)已存在 輸入：無(wú) 功能：求樹(shù)的根結(jié)點(diǎn) 輸出：樹(shù)的根結(jié)點(diǎn)的信息 后置條件：樹(shù)保持不變 樹(shù)的抽象數(shù)據(jù)類(lèi)型定義 樹(shù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 Parent 前置條件：樹(shù)已存在 輸入：結(jié)點(diǎn) x 功能：求結(jié)點(diǎn) x的雙親 輸出：結(jié)點(diǎn) x的雙親的信息 后置條件：樹(shù)保持不變 Depth 前置條件：樹(shù)已存在 輸入：無(wú) 功能：求樹(shù)的深度 輸出：樹(shù)的深度 后置條件：樹(shù)保持不變 樹(shù)的抽象數(shù)據(jù)類(lèi)型定義 樹(shù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 PreOrder 前置條件：樹(shù)已存在 輸入：無(wú) 功能：前序遍歷樹(shù) 輸出：樹(shù)的前序遍歷序列 后置條件：樹(shù)保持不變 PostOrder 前置條件：樹(shù)已存在 輸入：無(wú) 功能：后序遍歷樹(shù) 輸出：樹(shù)的后序遍歷序列 后置條件：樹(shù)保持不變 endADT 樹(shù)的抽象數(shù)據(jù)類(lèi)型定義 樹(shù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹(shù)的遍歷操作 樹(shù)的遍歷： 從 根 結(jié)點(diǎn)出發(fā)，按照某種 次 序訪(fǎng)問(wèn) 樹(shù)中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。 如何理解 訪(fǎng)問(wèn) ? 抽象 操作， 可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里 簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。 如何理解 次序 ? 樹(shù)通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式。 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)結(jié)構(gòu) （ 非線(xiàn)性結(jié)構(gòu) ） → 線(xiàn)性結(jié)構(gòu) 。 遍歷的實(shí)質(zhì) ? 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 前序遍歷 樹(shù)的前序遍歷操作定義為： 若樹(shù)為空 ， 則空操作返回；否則 ⑴ 訪(fǎng)問(wèn)根結(jié)點(diǎn)； ⑵ 按照從左到右的順序前序遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。 樹(shù)的邏輯結(jié)構(gòu) 前序遍歷序列： A B D E H I F C G A C B G F E D H I 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 后序遍歷 樹(shù)的后序遍歷操作定義為： 若樹(shù)為空 ， 則空操作返回；否則 ⑴ 按照從左到右的順序后序遍歷根結(jié)點(diǎn)的每一棵子樹(shù)； ⑵ 訪(fǎng)問(wèn)根結(jié)點(diǎn) 。 樹(shù)的邏輯結(jié)構(gòu) 后序遍歷序列： D H I E F B G C A A C B G F E D H I 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 層序遍歷 樹(shù)的層序遍歷操作定義為： 從樹(shù)的第一層 （ 即根結(jié)點(diǎn) ）開(kāi) 始 ， 自上而下逐層遍歷 ，在同一層中 ， 按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪(fǎng)問(wèn) 。 樹(shù)的邏輯結(jié)構(gòu) 層序遍歷序列： A B C D E F G H I A C B G F E D H I 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹(shù)的存儲(chǔ)結(jié)構(gòu) 實(shí)現(xiàn)樹(shù)的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵是什么 ? 什么是存儲(chǔ)結(jié)構(gòu) ? 樹(shù)中結(jié)點(diǎn)之間的邏輯關(guān)系是什么 ? 思考問(wèn)題的出發(fā)點(diǎn)：如何表示結(jié)點(diǎn)的雙親和孩子 如何表示樹(shù)中結(jié)點(diǎn)之間的邏輯關(guān)系。 數(shù)據(jù)元素以及數(shù)據(jù)元素之間的 邏輯關(guān)系 在存儲(chǔ)器中的表示。 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 雙親表示法 基本思想： 用一維數(shù)組來(lái)存儲(chǔ)樹(shù)的各個(gè)結(jié)點(diǎn)（一般按 層序 存儲(chǔ)），數(shù)組中的一個(gè)元素對(duì)應(yīng)樹(shù)中的 一個(gè)結(jié)點(diǎn)，包括結(jié)點(diǎn)的數(shù)據(jù)信息以及該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。 樹(shù)的存儲(chǔ)結(jié)構(gòu)