數(shù)據(jù)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù).ppt

樹(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ù)的定義 樹(shù) n n 0 個(gè)結(jié)點(diǎn)的有限集合 當(dāng)n 0時(shí) 稱為空樹(shù) 任意一棵非空樹(shù)滿足以下條件 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn) 當(dāng)n 1時(shí) 除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m m 0 個(gè)互不相交的有限集合T1 T2 Tm 其中每個(gè)集合又是一棵樹(shù) 并稱為這個(gè)根結(jié)點(diǎn)的子樹(shù) 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的定義是采用遞歸方法 a 一棵樹(shù)結(jié)構(gòu) b 一個(gè)非樹(shù)結(jié)構(gòu) c 一個(gè)非樹(shù)結(jié)構(gòu) 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的定義 樹(shù)的應(yīng)用舉例 文件結(jié)構(gòu) 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 結(jié)點(diǎn)的度 結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù) 樹(shù)的度 樹(shù)中各結(jié)點(diǎn)度的最大值 5 1樹(shù)的邏輯結(jié)構(gòu) 5 1樹(shù)的邏輯結(jié)構(gòu) 葉子結(jié)點(diǎn) 度為0的結(jié)點(diǎn) 也稱為終端結(jié)點(diǎn) 分支結(jié)點(diǎn) 度不為0的結(jié)點(diǎn) 也稱為非終端結(jié)點(diǎn) 樹(shù)的基本術(shù)語(yǔ) 孩子 雙親 樹(shù)中某結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn) 這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn) 兄弟 具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 路徑 如果樹(shù)的結(jié)點(diǎn)序列n1 n2 nk有如下關(guān)系 結(jié)點(diǎn)ni是ni 1的雙親 1 i k 則把n1 n2 nk稱為一條由n1至nk的路徑 路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱為路徑長(zhǎng)度 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 祖先 子孫 在樹(shù)中 如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y 那么x就稱為y的祖先 而y稱為x的子孫 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 結(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ù) 也稱高度 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 層序編號(hào) 將樹(shù)中結(jié)點(diǎn)按照從上層到下層 同層從左到右的次序依次給他們編以從1開(kāi)始的連續(xù)自然數(shù) 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 有序樹(shù) 無(wú)序樹(shù) 如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的 稱這棵樹(shù)為有序樹(shù) 反之 稱為無(wú)序樹(shù) 數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹(shù) 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 森林 m m 0 棵互不相交的樹(shù)的集合 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 同構(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)系也相等 則稱這兩棵樹(shù)同構(gòu) 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的基本術(shù)語(yǔ) 樹(shù)結(jié)構(gòu)和線性結(jié)構(gòu)的比較 線性結(jié)構(gòu) 樹(shù)結(jié)構(gòu) 無(wú)前驅(qū) 無(wú)雙親 無(wú)后繼 無(wú)孩子 一個(gè)前驅(qū) 一個(gè)后繼 一個(gè)雙親 多個(gè)孩子 一對(duì)一一對(duì)多 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的抽象數(shù)據(jù)類型定義 ADTTreeData樹(shù)是由一個(gè)根結(jié)點(diǎn)和若干棵子樹(shù)構(gòu)成 樹(shù)中結(jié)點(diǎn)具有相同數(shù)據(jù)類型及層次關(guān)系OperationInitTree前置條件 樹(shù)不存在輸入 無(wú)功能 初始化一棵樹(shù)輸出 無(wú)后置條件 構(gòu)造一個(gè)空樹(shù) 5 1樹(shù)的邏輯結(jié)構(gòu) DestroyTree前置條件 樹(shù)已存在輸入 無(wú)功能 銷毀一棵樹(shù)輸出 無(wú)后置條件 釋放該樹(shù)占用的存儲(chǔ)空間Root前置條件 樹(shù)已存在輸入 無(wú)功能 求樹(shù)的根結(jié)點(diǎn)輸出 樹(shù)的根結(jié)點(diǎn)的信息后置條件 樹(shù)保持不變 樹(shù)的抽象數(shù)據(jù)類型定義 5 1樹(shù)的邏輯結(jié)構(gòu) Parent前置條件 樹(shù)已存在輸入 結(jié)點(diǎn)x功能 求結(jié)點(diǎn)x的雙親輸出 結(jié)點(diǎn)x的雙親的信息后置條件 樹(shù)保持不變Depth前置條件 樹(shù)已存在輸入 無(wú)功能 求樹(shù)的深度輸出 樹(shù)的深度后置條件 樹(shù)保持不變 樹(shù)的抽象數(shù)據(jù)類型定義 5 1樹(shù)的邏輯結(jié)構(gòu) PreOrder前置條件 樹(shù)已存在輸入 無(wú)功能 前序遍歷樹(shù)輸出 樹(shù)的前序遍歷序列后置條件 樹(shù)保持不變PostOrder前置條件 樹(shù)已存在輸入 無(wú)功能 后序遍歷樹(shù)輸出 樹(shù)的后序遍歷序列后置條件 樹(shù)保持不變endADT 樹(shù)的抽象數(shù)據(jù)類型定義 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)的遍歷操作 樹(shù)的遍歷 從根結(jié)點(diǎn)出發(fā) 按照某種次序訪問(wèn)樹(shù)中所有結(jié)點(diǎn) 使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次 如何理解訪問(wèn) 抽象操作 可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理 這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù) 如何理解次序 樹(shù)通常有前序 根 遍歷 后序 根 遍歷和層序 次 遍歷三種方式 5 1樹(shù)的邏輯結(jié)構(gòu) 樹(shù)結(jié)構(gòu) 非線性結(jié)構(gòu) 線性結(jié)構(gòu) 遍歷的實(shí)質(zhì) 前序遍歷 樹(shù)的前序遍歷操作定義為 若樹(shù)為空 則空操作返回 否則 訪問(wèn)根結(jié)點(diǎn) 按照從左到右的順序前序遍歷根結(jié)點(diǎn)的每一棵子樹(shù) 5 1樹(shù)的邏輯結(jié)構(gòu) 前序遍歷序列 ABDEHIFCG 后序遍歷 樹(shù)的后序遍歷操作定義為 若樹(shù)為空 則空操作返回 否則 按照從左到右的順序后序遍歷根結(jié)點(diǎn)的每一棵子樹(shù) 訪問(wèn)根結(jié)點(diǎn) 5 1樹(shù)的邏輯結(jié)構(gòu) 后序遍歷序列 DHIEFBGCA 層序遍歷 樹(shù)的層序遍歷操作定義為 從樹(shù)的第一層 即根結(jié)點(diǎn) 開(kāi)始 自上而下逐層遍歷 在同一層中 按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn) 5 1樹(shù)的邏輯結(jié)構(gòu) 層序遍歷序列 ABCDEFGHI 5 2樹(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ù)組來(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) 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) templatestructPNode Tdata 數(shù)據(jù)域intparent 指針域 雙親在數(shù)組中的下標(biāo) 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)的雙親表示法實(shí)質(zhì)上是一個(gè)靜態(tài)鏈表 雙親表示法 下標(biāo)dataparent 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 如何查找雙親結(jié)點(diǎn) 時(shí)間性能 雙親表示法 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 雙親表示法 如何查找孩子結(jié)點(diǎn) 時(shí)間性能 下標(biāo)dataparent firstchild 下標(biāo)dataparent rightsib 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 雙親表示法 如何查找兄弟結(jié)點(diǎn) 時(shí)間性能 鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域 每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn) 如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu) 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 孩子鏈表表示法 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 缺點(diǎn) 浪費(fèi)空間 A B C D E F G H I 鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域 每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn) 如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu) 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 孩子鏈表表示法 方案二 指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度 其中 data 數(shù)據(jù)域 存放該結(jié)點(diǎn)的數(shù)據(jù)信息 degree 度域 存放該結(jié)點(diǎn)的度 child1 childd 指針域 指向該結(jié)點(diǎn)的孩子 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 缺點(diǎn) 結(jié)點(diǎn)結(jié)構(gòu)不一致 A2 B3 C2 E1 I0 G0 H0 F0 D0 孩子鏈表表示法 基本思想 把每個(gè)結(jié)點(diǎn)的孩子排列起來(lái) 看成是一個(gè)線性表 且以單鏈表存儲(chǔ) 則n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表 這n個(gè)單鏈表共有n個(gè)頭指針 這n個(gè)頭指針又組成了一個(gè)線性表 為了便于進(jìn)行查找采用順序存儲(chǔ) 最后 將存放n個(gè)頭指針的數(shù)組和存放n個(gè)結(jié)點(diǎn)的數(shù)組結(jié)合起來(lái) 構(gòu)成孩子鏈表的表頭數(shù)組 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu) 將結(jié)點(diǎn)的所有孩子放在一起 構(gòu)成線性表 structCTNode intchild CTNode next 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) templatestructCBNode Tdata CTNode firstchild 孩子鏈表表示法 012345678 下標(biāo)datafirstchild ABCDEFGHI 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 如何查找孩子結(jié)點(diǎn) 時(shí)間性能 012345678 下標(biāo)datafirstchild ABCDEFGHI 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 如何查找雙親結(jié)點(diǎn) 時(shí)間性能 雙親孩子表示法 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 孩子兄弟表示法 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 某結(jié)點(diǎn)的第一個(gè)孩子是惟一的某結(jié)點(diǎn)的右兄弟是惟一的 templatestructTNode Tdata TNode firstchild rightsib 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 結(jié)點(diǎn)結(jié)構(gòu) data 數(shù)據(jù)域 存儲(chǔ)該結(jié)點(diǎn)的數(shù)據(jù)信息 firstchild 指針域 指向該結(jié)點(diǎn)第一個(gè)孩子 rightsib 指針域 指向該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn) 孩子兄弟表示法 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 孩子兄弟表示法 如何查找兄弟結(jié)點(diǎn) 時(shí)間性能 5 2樹(shù)的存儲(chǔ)結(jié)構(gòu) 孩子兄弟表示法 如何查找孩子結(jié)點(diǎn) 時(shí)間性能 二叉樹(shù)的定義 二叉樹(shù)是n n 0 個(gè)結(jié)點(diǎn)的有限集合 該集合或者為空集 稱為空二叉樹(shù) 或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的 分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 問(wèn)題轉(zhuǎn)化 將樹(shù)轉(zhuǎn)換為二叉樹(shù) 從而利用二叉樹(shù)解決樹(shù)的有關(guān)問(wèn)題 研究二叉樹(shù)的意義 二叉樹(shù)的特點(diǎn) 每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù) 二叉樹(shù)是有序的 其次序不能任意顛倒 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 注意 二叉樹(shù)和樹(shù)是兩種樹(shù)結(jié)構(gòu) 二叉樹(shù)的基本形態(tài) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 具有3個(gè)結(jié)點(diǎn)的樹(shù)和具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)的形態(tài) 二叉樹(shù)和樹(shù)是兩種樹(shù)結(jié)構(gòu) 特殊的二叉樹(shù) 斜樹(shù)1 所有結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)稱為左斜樹(shù) 2 所有結(jié)點(diǎn)都只有右子樹(shù)的二叉樹(shù)稱為右斜樹(shù) 3 左斜樹(shù)和右斜樹(shù)統(tǒng)稱為斜樹(shù) 1 在斜樹(shù)中 每一層只有一個(gè)結(jié)點(diǎn) 2 斜樹(shù)的結(jié)點(diǎn)個(gè)數(shù)與其深度相同 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 斜樹(shù)的特點(diǎn) 滿二叉樹(shù)在一棵二叉樹(shù)中 如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù) 并且所有葉子都在同一層上 滿二叉樹(shù)的特點(diǎn) 葉子只能出現(xiàn)在最下一層 只有度為0和度為2的結(jié)點(diǎn) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 特殊的二叉樹(shù) 滿二叉樹(shù) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 不是滿二叉樹(shù) 雖然所有分支結(jié)點(diǎn)都有左右子樹(shù) 但葉子不在同一層上 滿二叉樹(shù)在同樣深度的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹(shù)在同樣深度的二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)最多 特殊的二叉樹(shù) 完全二叉樹(shù)對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào) 如果編號(hào)為i 1 i n 的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 特殊的二叉樹(shù) 在滿二叉樹(shù)中 從最后一個(gè)結(jié)點(diǎn)開(kāi)始 連續(xù)去掉任意個(gè)結(jié)點(diǎn) 即是一棵完全二叉樹(shù) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) A 1 5 2 3 4 6 7 9 10 B C D E F G H I J 不是完全二叉樹(shù) 結(jié)點(diǎn)10與滿二叉樹(shù)中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn) 特殊的二叉樹(shù) 1 葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層 且最下層的葉子結(jié)點(diǎn)都集中在二叉樹(shù)的左部 2 完全二叉樹(shù)中如果有度為1的結(jié)點(diǎn) 只可能有一個(gè) 且該結(jié)點(diǎn)只有左孩子 3 深度為k的完全二叉樹(shù)在k 1層上一定是滿二叉樹(shù) 完全二叉樹(shù)的特點(diǎn) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 特殊的二叉樹(shù) 二叉樹(shù)的基本性質(zhì) 性質(zhì)5 1二叉樹(shù)的第i層上最多有2i 1個(gè)結(jié)點(diǎn) i 1 證明 當(dāng)i 1時(shí) 第1層只有一個(gè)根結(jié)點(diǎn) 而2i 1 20 1 結(jié)論顯然成立 假定i k 1 k i 時(shí)結(jié)論成立 即第k層上至多有2k 1個(gè)結(jié)點(diǎn) 則i k 1時(shí) 因?yàn)榈趉 1層上的結(jié)點(diǎn)是第k層上結(jié)點(diǎn)的孩子 而二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有2個(gè)孩子 故在第k 1層上最大結(jié)點(diǎn)個(gè)數(shù)為第k層上的最大結(jié)點(diǎn)個(gè)數(shù)的二倍 即2 2k 1 2k 結(jié)論成立 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 性質(zhì)5 2一棵深度為k的二叉樹(shù)中 最多有2k 1個(gè)結(jié)點(diǎn) 最少有k個(gè)結(jié)點(diǎn) 證明 由性質(zhì)1可知 深度為k的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多 2k 1 每一層至少要有一個(gè)結(jié)點(diǎn) 因此深度為k的二叉樹(shù) 至少有k個(gè)結(jié)點(diǎn) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 二叉樹(shù)的基本性質(zhì) 性質(zhì)5 3在一棵二叉樹(shù)中 如果葉子結(jié)點(diǎn)數(shù)為n0 度為2的結(jié)點(diǎn)數(shù)為n2 則有 n0 n2 1 證明 設(shè)n為二叉樹(shù)的結(jié)點(diǎn)總數(shù) n1為二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù) 則有 n n0 n1 n2在二叉樹(shù)中 除了根結(jié)點(diǎn)外 其余結(jié)點(diǎn)都有唯一的一個(gè)分枝進(jìn)入 由于這些分枝是由度為1和度為2的結(jié)點(diǎn)射出的 一個(gè)度為1的結(jié)點(diǎn)射出一個(gè)分枝 一個(gè)度為2的結(jié)點(diǎn)射出兩個(gè)分枝 所以有 n n1 2n2 1因此可以得到 n0 n2 1 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 二叉樹(shù)的基本性質(zhì) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 在有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)中 有多少個(gè)葉子結(jié)點(diǎn) 二叉樹(shù)的基本性質(zhì) 性質(zhì)5 3在一棵二叉樹(shù)中 如果葉子結(jié)點(diǎn)數(shù)為n0 度為2的結(jié)點(diǎn)數(shù)為n2 則有 n0 n2 1 性質(zhì)5 4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n 1 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 證明 假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k 根據(jù)完全二叉樹(shù)的定義和性質(zhì)2 有下式成立2k 1 n 2k 最少結(jié)點(diǎn)數(shù) 最多結(jié)點(diǎn)數(shù) 完全二叉樹(shù)的基本性質(zhì) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 證明 假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k 根據(jù)完全二叉樹(shù)的定義和性質(zhì)2 有下式成立2k 1 n 2k 完全二叉樹(shù)的基本性質(zhì) 性質(zhì)5 5對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從1開(kāi)始按層序編號(hào) 則對(duì)于任意的序號(hào)為i 1 i n 的結(jié)點(diǎn) 簡(jiǎn)稱為結(jié)點(diǎn)i 有 1 如果i 1 則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為i 2 如果i 1 則結(jié)點(diǎn)i是根結(jié)點(diǎn) 無(wú)雙親結(jié)點(diǎn) 2 如果2i n 則結(jié)點(diǎn)i的左孩子的序號(hào)為2i 如果2i n 則結(jié)點(diǎn)i無(wú)左孩子 3 如果2i 1 n 則結(jié)點(diǎn)i的右孩子的序號(hào)為2i 1 如果2i 1 n 則結(jié)點(diǎn)i無(wú)右孩子 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 完全二叉樹(shù)的基本性質(zhì) 對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從1開(kāi)始按層序編號(hào) 則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為i 2 結(jié)點(diǎn)i的左孩子為2i 結(jié)點(diǎn)i的右孩子為2i 1 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 性質(zhì)5表明 在完全二叉樹(shù)中 結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系 完全二叉樹(shù)的基本性質(zhì) 二叉樹(shù)的抽象數(shù)據(jù)類型定義 ADTBiTreeData由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹(shù)構(gòu)成 結(jié)點(diǎn)具有相同數(shù)據(jù)類型及層次關(guān)系OperationInitBiTree前置條件 無(wú)輸入 無(wú)功能 初始化一棵二叉樹(shù)輸出 無(wú)后置條件 構(gòu)造一個(gè)空的二叉樹(shù) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) DestroyBiTree前置條件 二叉樹(shù)已存在輸入 無(wú)功能 銷毀一棵二叉樹(shù)輸出 無(wú)后置條件 釋放二叉樹(shù)占用的存儲(chǔ)空間InsertL前置條件 二叉樹(shù)已存在輸入 數(shù)據(jù)值x 指針parent功能 將數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)插入到二叉樹(shù)中 作為結(jié)點(diǎn)parent的左孩子 如果結(jié)點(diǎn)parent原來(lái)有左孩子 則將結(jié)點(diǎn)parent原來(lái)的左孩子作為結(jié)點(diǎn)x的左孩子輸出 無(wú)后置條件 如果插入成功 得到一個(gè)新的二叉樹(shù) 二叉樹(shù)的抽象數(shù)據(jù)類型定義 5 3二叉樹(shù)的邏輯結(jié)構(gòu) DeleteL前置條件 二叉樹(shù)已存在輸入 指針parent功能 在二叉樹(shù)中刪除結(jié)點(diǎn)parent的左子樹(shù)輸出 無(wú)后置條件 如果刪除成功 得到一個(gè)新的二叉樹(shù)Search前置條件 二叉樹(shù)已存在輸入 數(shù)據(jù)值x功能 在二叉樹(shù)中查找數(shù)據(jù)元素x輸出 指向該元素結(jié)點(diǎn)的指針后置條件 二叉樹(shù)不變 二叉樹(shù)的抽象數(shù)據(jù)類型定義 5 3二叉樹(shù)的邏輯結(jié)構(gòu) PreOrder前置條件 二叉樹(shù)已存在輸入 無(wú)功能 前序遍歷二叉樹(shù)輸出 二叉樹(shù)中結(jié)點(diǎn)的一個(gè)線性排列后置條件 二叉樹(shù)不變InOrder前置條件 二叉樹(shù)已存在輸入 無(wú)功能 中序遍歷二叉樹(shù)輸出 二叉樹(shù)中結(jié)點(diǎn)的一個(gè)線性排列后置條件 二叉樹(shù)不變 二叉樹(shù)的抽象數(shù)據(jù)類型定義 5 3二叉樹(shù)的邏輯結(jié)構(gòu) PostOrder前置條件 二叉樹(shù)已存在輸入 無(wú)功能 后序遍歷二叉樹(shù)輸出 二叉樹(shù)中結(jié)點(diǎn)的一個(gè)線性排列后置條件 二叉樹(shù)不變LeverOrder前置條件 二叉樹(shù)已存在輸入 無(wú)功能 層序遍歷二叉樹(shù)輸出 二叉樹(shù)中結(jié)點(diǎn)的一個(gè)線性排列后置條件 二叉樹(shù)不變endADT 二叉樹(shù)的抽象數(shù)據(jù)類型定義 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 二叉樹(shù)的遍歷操作 二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā) 按照某種次序訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn) 使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次 二叉樹(shù)遍歷操作的結(jié)果 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 二叉樹(shù)的遍歷方式 DLR LDR LRD DRL RDL RLD 如果限定先左后右 則二叉樹(shù)遍歷方式有三種 前序 DLR中序 LDR后序 LRD 層序遍歷 按二叉樹(shù)的層序編號(hào)的次序訪問(wèn)各結(jié)點(diǎn) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 考慮二叉樹(shù)的組成 前序 根 遍歷若二叉樹(shù)為空 則空操作返回 否則 訪問(wèn)根結(jié)點(diǎn) 前序遍歷根結(jié)點(diǎn)的左子樹(shù) 前序遍歷根結(jié)點(diǎn)的右子樹(shù) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 前序遍歷序列 ABDGCEF 二叉樹(shù)的遍歷操作 中序 根 遍歷若二叉樹(shù)為空 則空操作返回 否則 中序遍歷根結(jié)點(diǎn)的左子樹(shù) 訪問(wèn)根結(jié)點(diǎn) 中序遍歷根結(jié)點(diǎn)的右子樹(shù) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 中序遍歷序列 DGBAECF 二叉樹(shù)的遍歷操作 后序 根 遍歷若二叉樹(shù)為空 則空操作返回 否則 后序遍歷根結(jié)點(diǎn)的左子樹(shù) 后序遍歷根結(jié)點(diǎn)的右子樹(shù) 訪問(wèn)根結(jié)點(diǎn) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 后序遍歷序列 GDBEFCA 二叉樹(shù)的遍歷操作 層序遍歷二叉樹(shù)的層次遍歷是指從二叉樹(shù)的第一層 即根結(jié)點(diǎn) 開(kāi)始 從上至下逐層遍歷 在同一層中 則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 層序遍歷序列 ABCDEFG 二叉樹(shù)的遍歷操作 5 3二叉樹(shù)的邏輯結(jié)構(gòu) a b c d e f 二叉樹(shù)遍歷操作練習(xí) 前序遍歷結(jié)果 a b cd ef中序遍歷結(jié)果 a b c d e f后序遍歷結(jié)果 abcd ef 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 若已知一棵二叉樹(shù)的前序 或中序 或后序 或?qū)有?序列 能否唯一確定這棵二叉樹(shù)呢 例 已知前序序列為ABC 則可能的二叉樹(shù)有5種 二叉樹(shù)的遍歷操作 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 例 已知前序遍歷序列為ABC 后序遍歷序列為CBA 則下列二叉樹(shù)都滿足條件 若已知一棵二叉樹(shù)的前序序列和后序序列 能否唯一確定這棵二叉樹(shù)呢 二叉樹(shù)的遍歷操作 若已知一棵二叉樹(shù)的前序序列和中序序列 能否唯一確定這棵二叉樹(shù)呢 怎樣確定 例如 已知一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI 如何構(gòu)造該二叉樹(shù)呢 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 二叉樹(shù)的遍歷操作 前序 ABCDEFGHI中序 BCAEDGHFI 前序 BC中序 BC 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 前序 DEFGHI中序 EDGHFI 前序 FGHI中序 GHFI 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 前序 DEFGHI中序 EDGHFI 1 根據(jù)前序序列的第一個(gè)元素建立根結(jié)點(diǎn) 2 在中序序列中找到該元素 確定根結(jié)點(diǎn)的左右子樹(shù)的中序序列 3 在前序序列中確定左右子樹(shù)的前序序列 4 由左子樹(shù)的前序序列和中序序列建立左子樹(shù) 5 由右子樹(shù)的前序序列和中序序列建立右子樹(shù) 5 3二叉樹(shù)的邏輯結(jié)構(gòu) 已知一棵二叉樹(shù)的前序序列和中序序列 構(gòu)造該二叉樹(shù)的過(guò)程如下 二叉樹(shù)的遍歷操作 順序存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn) 并且結(jié)點(diǎn)的存儲(chǔ)位置 下標(biāo) 應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系 父子關(guān)系 如何利用數(shù)組下標(biāo)來(lái)反映結(jié)點(diǎn)之間的邏輯關(guān)系 完全二叉樹(shù)和滿二叉樹(shù)中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 完全二叉樹(shù)的順序存儲(chǔ) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 以編號(hào)為下標(biāo) 二叉樹(shù)的順序存儲(chǔ) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 以編號(hào)為下標(biāo) 按照完全二叉樹(shù)編號(hào) 一棵斜樹(shù)的順序存儲(chǔ)會(huì)怎樣呢 深度為k的右斜樹(shù) k個(gè)結(jié)點(diǎn)需分配2k 1個(gè)存儲(chǔ)單元 一棵二叉樹(shù)改造后成完全二叉樹(shù)形態(tài) 需增加很多空結(jié)點(diǎn) 造成存儲(chǔ)空間的浪費(fèi) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)一般僅存儲(chǔ)完全二叉樹(shù) 二叉鏈表 基本思想 令二叉樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn) 鏈表結(jié)點(diǎn)除了存放與二叉樹(shù)結(jié)點(diǎn)有關(guān)的數(shù)據(jù)信息外 還要設(shè)置指示左右孩子的指針 結(jié)點(diǎn)結(jié)構(gòu) 其中 data 數(shù)據(jù)域 存放該結(jié)點(diǎn)的數(shù)據(jù)信息 lchild 左指針域 存放指向左孩子的指針 rchild 右指針域 存放指向右孩子的指針 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) templatestructBiNode Tdata BiNode lchild rchild 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 二叉鏈表 二叉鏈表 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 具有n個(gè)結(jié)點(diǎn)的二叉鏈表中 有多少個(gè)空指針 二叉鏈表 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 具有n個(gè)結(jié)點(diǎn)的二叉鏈表中 有n 1個(gè)空指針 二叉鏈表存儲(chǔ)結(jié)構(gòu)的類聲明 templateclassBiTree public BiTree root NULL BiTree BiNode root BiTree voidPreOrder BiNode root voidInOrder BiNode root voidPostOrder BiNode root voidLeverOrder BiNode root private BiNode root voidCreat BiNode root voidRelease BiNode root 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 前序遍歷 遞歸算法 templatevoidBiTree PreOrder BiNode root if root NULL return else coutdata PreOrder root lchild PreOrder root rchild 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 前序遍歷算法的執(zhí)行軌跡 二叉樹(shù)前序遍歷的非遞歸算法的關(guān)鍵 在前序遍歷過(guò)某結(jié)點(diǎn)的整個(gè)左子樹(shù)后 如何找到該結(jié)點(diǎn)的右子樹(shù)的根指針 解決辦法 在訪問(wèn)完該結(jié)點(diǎn)后 將該結(jié)點(diǎn)的指針保存在棧中 以便以后能通過(guò)它找到該結(jié)點(diǎn)的右子樹(shù) 在前序遍歷中 設(shè)要遍歷二叉樹(shù)的根指針為root 則有兩種可能 若root NULL 則表明 如何處理 若root NULL 則表明 如何處理 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 前序遍歷 非遞歸算法 訪問(wèn)結(jié)點(diǎn)序列 A 棧S內(nèi)容 B D A B 前序遍歷的非遞歸實(shí)現(xiàn) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) A D B C 訪問(wèn)結(jié)點(diǎn)序列 A 棧S內(nèi)容 B D A 前序遍歷的非遞歸實(shí)現(xiàn) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) A D B C D 訪問(wèn)結(jié)點(diǎn)序列 A 棧S內(nèi)容 B D C 前序遍歷的非遞歸實(shí)現(xiàn) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) A D B C C 1 棧s初始化 2 循環(huán)直到root為空且棧s為空2 1當(dāng)root不空時(shí)循環(huán)2 1 1輸出root data 2 1 2將指針root的值保存到棧中 2 1 3繼續(xù)遍歷root的左子樹(shù)2 2如果棧s不空 則2 2 1將棧頂元素彈出至root 2 2 2準(zhǔn)備遍歷root的右子樹(shù) 前序遍歷 非遞歸算法 偽代碼 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 前序遍歷 非遞歸算法 偽代碼 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) templatevoidBiTree PreOrder BiNode root top 1 采用順序棧 并假定不會(huì)發(fā)生上溢while root NULL top 1 while root NULL coutdata s top root root root lchild if top 1 root s top root root rchild 中序遍歷 遞歸算法 templatevoidBiTree InOrder BiNode root if root NULL return else InOrder root lchild coutdata InOrder root rchild 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 后序遍歷 遞歸算法 templatevoidBiTree PostOrder BiNode root if root NULL return else PostOrder root lchild PostOrder root rchild coutdata 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 層序遍歷 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 遍歷序列 A A B C B D C E F G D E F G 層序遍歷 隊(duì)列Q初始化 2 如果二叉樹(shù)非空 將根指針入隊(duì) 3 循環(huán)直到隊(duì)列Q為空3 1q 隊(duì)列Q的隊(duì)頭元素出隊(duì) 3 2訪問(wèn)結(jié)點(diǎn)q的數(shù)據(jù)域 3 3若結(jié)點(diǎn)q存在左孩子 則將左孩子指針入隊(duì) 3 4若結(jié)點(diǎn)q存在右孩子 則將右孩子指針入隊(duì) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 二叉樹(shù)的建立 為了建立一棵二叉樹(shù) 將二叉樹(shù)中每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn) 其值為一特定值如 以標(biāo)識(shí)其為空 把這樣處理后的二叉樹(shù)稱為原二叉樹(shù)的擴(kuò)展二叉樹(shù) 為什么如此處理 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何由一種遍歷序列生成該二叉樹(shù) 遍歷是二叉樹(shù)各種操作的基礎(chǔ) 可以在遍歷的過(guò)程中進(jìn)行各種操作 例如建立一棵二叉樹(shù) 擴(kuò)展二叉樹(shù)的前序遍歷序列 AB D C 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 二叉樹(shù)的建立 設(shè)二叉樹(shù)中的結(jié)點(diǎn)均為一個(gè)字符 假設(shè)擴(kuò)展二叉樹(shù)的前序遍歷序列由鍵盤(pán)輸入 root為指向根結(jié)點(diǎn)的指針 二叉鏈表的建立過(guò)程是 首先輸入根結(jié)點(diǎn) 若輸入的是一個(gè) 字符 則表明該二叉樹(shù)為空樹(shù) 即root NULL 否則輸入的字符應(yīng)該賦給root data 之后依次遞歸建立它的左子樹(shù)和右子樹(shù) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 二叉樹(shù)的建立 templateBiTree BiTree BiNode root creat root voidBiTree Creat BiNode root cin ch if ch root NULL else root newBiNode root data ch creat root lchild creat root rchild 建立二叉遞歸算法 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 二叉樹(shù)算法設(shè)計(jì)練習(xí) 遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ) 遍歷算法中對(duì)每個(gè)結(jié)點(diǎn)的訪問(wèn)操作可以是多種形式及多個(gè)操作 根據(jù)遍歷算法的框架 適當(dāng)修改訪問(wèn)操作的內(nèi)容 可以派生出很多關(guān)于二叉樹(shù)的應(yīng)用算法 voidInOrder BiNode root if root NULL return else InOrder root lchild coutdata InOrder root rchild 二叉樹(shù)算法設(shè)計(jì)練習(xí) 設(shè)計(jì)算法求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù) voidCount BiNode root n為全局量并已初始化為0 if root Count root lchild n Count root rchild 二叉樹(shù)算法設(shè)計(jì)練習(xí) 設(shè)計(jì)算法按前序次序打印二叉樹(shù)中的葉子結(jié)點(diǎn) voidPreOrder BiNode root if root if root lchild 二叉樹(shù)算法設(shè)計(jì)練習(xí) 設(shè)計(jì)算法求二叉樹(shù)的深度 intDepth BiNode root if root NULL return0 else hl Depth root lchild hr Depth root rchild returnmax hl hr 1 二叉樹(shù)算法設(shè)計(jì)練習(xí) 設(shè)計(jì)算法求樹(shù)中結(jié)點(diǎn)x的第i個(gè)孩子 templateTNode Search TNode root Tx inti if root data x j 1 p root firstchild while p NULL templatestructTNode Tdata TNode firstchild rightsib 三叉鏈表 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 在二叉鏈表中 如何求某結(jié)點(diǎn)的雙親 三叉鏈表 在二叉鏈表的基礎(chǔ)上增加了一個(gè)指向雙親的指針域 結(jié)點(diǎn)結(jié)構(gòu) 其中 data lchild和rchild三個(gè)域的含義同二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 三叉鏈表 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 三叉鏈表的靜態(tài)鏈表形式 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 線索鏈表 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何保存二叉樹(shù)的某種遍歷序列 中序遍歷序列 DGBAFCF 如果二叉樹(shù)不改變 如何保存 線索鏈表 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何保存二叉樹(shù)的某種遍歷序列 中序遍歷序列 DGBAFCF 如果二叉樹(shù)改變 如何保存 線索鏈表 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何保存二叉樹(shù)的某種遍歷序列 中序遍歷序列 DGBAFCF 如何將二叉鏈表與中序鏈表結(jié)合 線索鏈表 線索 將二叉鏈表中的空指針域指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針被稱為線索 線索化 使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或后繼信息的過(guò)程稱為線索化 線索二叉樹(shù) 加上線索的二叉樹(shù)稱為線索二叉樹(shù) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何保存二叉樹(shù)的某種遍歷序列 將二叉鏈表中的空指針域指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 結(jié)點(diǎn)結(jié)構(gòu) 線索鏈表 enumflag Child Thread templatestructThrNode Tdata ThrNode lchild rchild flagltag rtag 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 線索鏈表 結(jié)點(diǎn)結(jié)構(gòu) 二叉樹(shù)的遍歷方式有4種 故有4種意義下的前驅(qū)和后繼 相應(yīng)的有4種線索二叉樹(shù) 前序線索二叉樹(shù) 中序線索二叉樹(shù) 后序線索二叉樹(shù) 層序線索二叉樹(shù) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 線索二叉樹(shù) 中序線索二叉樹(shù) 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 線索二叉樹(shù) 中序序列 DGBAECF templateclassInThrBiTree public InThrBiTree ThrNode root InThrBiTree ThrNode Next ThrNode p voidInOrder ThrNode root private ThrNode root voidCreat ThrNode root voidThrBiTree ThrNode root 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序線索鏈表類的聲明 分析 建立線索鏈表 實(shí)質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索 而前驅(qū)或后繼的信息只有在遍歷該二叉樹(shù)時(shí)才能得到 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序線索鏈表的建立 構(gòu)造函數(shù) A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 已經(jīng)建立起二叉鏈表 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)的結(jié)點(diǎn) 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)的結(jié)點(diǎn) 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)的結(jié)點(diǎn) 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)的結(jié)點(diǎn) 1 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)的結(jié)點(diǎn) 1 1 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)的結(jié)點(diǎn) 1 1 1 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)的結(jié)點(diǎn) 1 1 1 1 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過(guò)程 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序遍歷二叉鏈表p為正在訪問(wèn)的結(jié)點(diǎn)pre為剛訪問(wèn)的結(jié)點(diǎn) 1 1 1 1 1 1 1 1 在遍歷過(guò)程中 訪問(wèn)當(dāng)前結(jié)點(diǎn)root的操作為 如果root的左 右指針域?yàn)榭?則將相應(yīng)標(biāo)志置1 若root的左指針域?yàn)榭?則令其指向它的前驅(qū) 這需要設(shè)指針pre始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn) 顯然pre的初值為NULL 若pre的右指針域?yàn)榭?則令其指向它的后繼 即當(dāng)前訪問(wèn)的結(jié)點(diǎn)root 令pre指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)root 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序線索鏈表的建立 1 建立二叉鏈表 將每個(gè)結(jié)點(diǎn)的左右標(biāo)志置為0 2 遍歷二叉鏈表 建立線索 2 1如果二叉鏈表root為空 則空操作返回 2 2對(duì)root的左子樹(shù)建立線索 2 3對(duì)根結(jié)點(diǎn)root建立線索 2 3 1若root沒(méi)有左孩子 則為root加上前驅(qū)線索 2 3 2若root沒(méi)有右孩子 則將root右標(biāo)志置為1 2 3 3若結(jié)點(diǎn)pre右標(biāo)志為1 則為pre加上后繼線索 2 3 4令pre指向剛剛訪問(wèn)的結(jié)點(diǎn)root 2 4對(duì)root的右子樹(shù)建立線索 5 4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 中序線索鏈表的建立 構(gòu)造函數(shù) 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 是哪些樹(shù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu) 樹(shù)和二叉樹(shù)之間具有對(duì)應(yīng)關(guān)系 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系樹(shù) 兄弟關(guān)系二叉樹(shù) 雙親和右孩子樹(shù) 雙親和長(zhǎng)子二叉樹(shù) 雙親和左孩子 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 1 兄弟加線 樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 2 保留雙親與第一孩子連線 刪去與其他孩子的連線 樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系 1 兄弟加線 3 順時(shí)針轉(zhuǎn)動(dòng) 使之層次分明 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系 2 保留雙親與第一孩子連線 刪去與其他孩子的連線 1 兄弟加線 A B C D E F G 3 順時(shí)針轉(zhuǎn)動(dòng) 使之層次分明 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系 2 保留雙親與第一孩子連線 刪去與其他孩子的連線 1 兄弟加線 樹(shù)轉(zhuǎn)換為二叉樹(shù) 加線 樹(shù)中所有相鄰兄弟之間加一條連線 去線 對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn) 只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線 刪去它與其它孩子結(jié)點(diǎn)之間的連線 層次調(diào)整 以根結(jié)點(diǎn)為軸心 將樹(shù)順時(shí)針轉(zhuǎn)動(dòng)一定的角度 使之層次分明 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 ABEFCDG ABEFCDG 樹(shù)的前序遍歷等價(jià)于二叉樹(shù)的前序遍歷 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 EFBCGDA EFBCGDA 樹(shù)的后序遍歷等價(jià)于二叉樹(shù)的中序遍歷 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 森林轉(zhuǎn)換為二叉樹(shù) 將森林中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù) 從第二棵二叉樹(shù)開(kāi)始 依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子 當(dāng)所有二叉樹(shù)連起來(lái)后 此時(shí)所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù) 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林 加線 若某結(jié)點(diǎn)x是其雙親y的左孩子 則把結(jié)點(diǎn)x的右孩子 右孩子的右孩子 都與結(jié)點(diǎn)y用線連起來(lái) 去線 刪去原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線 層次調(diào)整 整理由 兩步所得到的樹(shù)或森林 使之層次分明 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 森林的遍歷 森林有兩種遍歷方法 前序 根 遍歷 前序遍歷森林即為前序遍歷森林中的每一棵樹(shù) 后序 根 遍歷 后序遍歷森林即為后序遍歷森林中的每一棵樹(shù) 5 5樹(shù) 森林與二叉樹(shù)的轉(zhuǎn)換 相關(guān)概念 葉子結(jié)點(diǎn)的權(quán)值 對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量 二叉樹(shù)的帶權(quán)路徑長(zhǎng)度 設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn) 從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和 記為 WPL 5 6哈夫曼樹(shù)及哈夫曼編碼 哈夫曼樹(shù) 給定一組具有確定權(quán)值的葉子結(jié)點(diǎn) 帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù) 例 給定4個(gè)葉子結(jié)點(diǎn) 其權(quán)值分別為 2 3 4 7 可以構(gòu)造出形狀不同的多個(gè)二叉樹(shù) 5 6哈夫曼樹(shù)及哈夫曼編碼 WPL 32WPL 41WPL 30 哈夫曼樹(shù)的特點(diǎn) 1 權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn) 而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn) 2 只有度為0 葉子結(jié)點(diǎn) 和度為2 分支結(jié)點(diǎn) 的結(jié)點(diǎn) 不存在度為1的結(jié)點(diǎn) 5 6哈夫曼樹(shù)及哈夫曼編碼 2 3 4 7 WPL 32WPL 41WPL 30 2 3 4 7 7 4 2 3 哈夫曼算法基本思想 初始化 由給定的n個(gè)權(quán)值 w1 w2 wn 構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù) 從而得到一個(gè)二叉樹(shù)集合F T1 T2 Tn 選取與合并 在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹(shù)分別作為左 右子樹(shù)構(gòu)造一棵新的二叉樹(shù) 這棵新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左 右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和 刪除與加入 在F中刪除作為左 右子樹(shù)的兩棵二叉樹(shù) 并將新建立的二叉樹(shù)加入