數(shù)據(jù)結(jié)構(gòu)第二部分

1 第二部分樹(shù) 樹(shù)形結(jié)構(gòu)式處理具有層次關(guān)系的數(shù)據(jù)元素這部分將介紹樹(shù)二叉樹(shù)堆 2 第五章樹(shù) 樹(shù)的概念二叉樹(shù)表達(dá)式樹(shù)哈夫曼樹(shù)與哈夫曼編碼樹(shù)和森林 3 樹(shù)的概念 樹(shù)的定義樹(shù)的術(shù)語(yǔ)樹(shù)的運(yùn)算 4 樹(shù)的定義 樹(shù)是n n 1 個(gè)結(jié)點(diǎn)的有限集合T 并且滿(mǎn)足 1 有一個(gè)被稱(chēng)之為根 root 的結(jié)點(diǎn) 2 其余的結(jié)點(diǎn)可分為m m 0 個(gè)互不相交的集合Tl T2 Tm 這些集合本身也是一棵樹(shù) 并稱(chēng)它們?yōu)楦Y(jié)點(diǎn)的子樹(shù) Subree 每棵子樹(shù)同樣有自己的根結(jié)點(diǎn) 5 樹(shù)的概念 樹(shù)的定義樹(shù)的術(shù)語(yǔ)樹(shù)的運(yùn)算 6 根結(jié)點(diǎn) 葉結(jié)點(diǎn) 內(nèi)部節(jié)點(diǎn)結(jié)點(diǎn)的度和樹(shù)的度兒子結(jié)點(diǎn)父親結(jié)點(diǎn)兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)子孫結(jié)點(diǎn)結(jié)點(diǎn)所處層次樹(shù)的高度 有序樹(shù)無(wú)序樹(shù)森林 樹(shù)的術(shù)語(yǔ) 7 樹(shù)的概念 樹(shù)的定義樹(shù)的術(shù)語(yǔ)樹(shù)的運(yùn)算 8 樹(shù)的常用操作 建樹(shù)create 創(chuàng)建一棵空樹(shù) 清空clear 刪除樹(shù)中的所有結(jié)點(diǎn) 判空IsEmpty 判別是否為空樹(shù) 找根結(jié)點(diǎn)root 找出樹(shù)的根結(jié)點(diǎn) 如果樹(shù)是空樹(shù) 則返回一個(gè)特殊的標(biāo)記 找父結(jié)點(diǎn)parent x 找出結(jié)點(diǎn)x的父結(jié)點(diǎn) 找子結(jié)點(diǎn)child x i 找結(jié)點(diǎn)x的第i個(gè)子結(jié)點(diǎn) 剪枝delete x i 刪除結(jié)點(diǎn)x的第i棵子樹(shù) 構(gòu)建一棵樹(shù)MakeTree x T1 T2 Tn 構(gòu)建一棵以x為根結(jié)點(diǎn) 以T1 T2 Tn為第i棵子樹(shù)的樹(shù) 遍歷traverse 訪(fǎng)問(wèn)樹(shù)上的每一個(gè)結(jié)點(diǎn) 9 第五章樹(shù) 樹(shù)的概念二叉樹(shù)表達(dá)式樹(shù)哈夫曼樹(shù)與哈夫曼編碼樹(shù)和森林 10 二叉樹(shù) 二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的基本運(yùn)算二叉樹(shù)的遍歷二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)類(lèi)二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 11 二叉樹(shù)的定義 二叉樹(shù) BinaryTree 是結(jié)點(diǎn)的有限集合 它或者為空 或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左 右子樹(shù)構(gòu)成 而其左 右子樹(shù)又都是二叉樹(shù) 注意 二叉樹(shù)必須嚴(yán)格區(qū)分左右子樹(shù) 即使只有一棵子樹(shù) 也要說(shuō)明它是左子樹(shù)還是右子樹(shù) 交換一棵二叉樹(shù)的左右子樹(shù)后得到的是另一棵二叉樹(shù) 12 二叉樹(shù)的基本形態(tài) a 空二叉樹(shù) b 根和空的左右子樹(shù) c 根和左右子樹(shù) d 根和左子樹(shù) e 根和右子樹(shù) 13 結(jié)點(diǎn)總數(shù)為3的所有二叉樹(shù)的不同形狀 14 一棵高度為k并具有2k 1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù) 一棵二叉樹(shù)中任意一層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到了最大值 滿(mǎn)二叉樹(shù) 15 滿(mǎn)二叉樹(shù)實(shí)例 不是滿(mǎn)二叉樹(shù) 16 完全二叉樹(shù) 在滿(mǎn)二叉樹(shù)的最底層自右至左依次 注意 不能跳過(guò)任何一個(gè)結(jié)點(diǎn) 去掉若干個(gè)結(jié)點(diǎn)得到的二叉樹(shù)也被稱(chēng)之為完全二叉樹(shù) 滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù) 但完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù) 完全二叉樹(shù)的特點(diǎn)是 1 所有的葉結(jié)點(diǎn)都出現(xiàn)在最低的兩層上 2 對(duì)任一結(jié)點(diǎn) 如果其右子樹(shù)的高度為k 則其左子樹(shù)的高度為k或k 1 17 完全二叉樹(shù) 非完全二叉樹(shù) 18 二叉樹(shù) 二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的基本運(yùn)算二叉樹(shù)的遍歷二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)類(lèi)二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 19 二叉樹(shù)的性質(zhì)1 一棵非空二叉樹(shù)的第i層上最多有2i 1個(gè)結(jié)點(diǎn) i 1 1層 結(jié)點(diǎn)個(gè)數(shù)21 1 1個(gè)2層 結(jié)點(diǎn)個(gè)數(shù)22 1 2個(gè)3層 結(jié)點(diǎn)個(gè)數(shù)23 1 4個(gè) 20 證明 當(dāng)i 1時(shí) 只有一個(gè)根結(jié)點(diǎn) 2i 1 20 1 命題成立 假定對(duì)于所有的j 1 j k 命題成立 即第j層上至多有2j 1個(gè)結(jié)點(diǎn) 由歸納假設(shè)可知 第j k層上至多有2k 1個(gè)結(jié)點(diǎn) 若要使得第k 1層上結(jié)點(diǎn)數(shù)為最多 那么 第k層上的每個(gè)結(jié)點(diǎn)都必須有二個(gè)兒子結(jié)點(diǎn) 因此 第k 1層上結(jié)點(diǎn)數(shù)最多為為第k層上最多結(jié)點(diǎn)數(shù)的二倍 即 2 2k 1 2k 1 1 2k 所以 命題成立 21 二叉樹(shù)的性質(zhì)2 一棵高度為k的二叉樹(shù) 最多具有2k 1個(gè)結(jié)點(diǎn) 證明 這棵二叉樹(shù)中的每一層的結(jié)點(diǎn)個(gè)數(shù)必須最多 根據(jù)性質(zhì)1 第i層的結(jié)點(diǎn)數(shù)最多為等于2i 1 因此結(jié)點(diǎn)個(gè)數(shù)N最多為 22 對(duì)于一棵非空二叉樹(shù) 如果葉子結(jié)點(diǎn)數(shù)為n0 度數(shù)為2的結(jié)點(diǎn)數(shù)為n2 則有 n0 n2 1成立 二叉樹(shù)的性質(zhì)3 23 證明 設(shè)n為二叉樹(shù)的結(jié)點(diǎn)總數(shù) n1為二叉樹(shù)中度數(shù)為1的結(jié)點(diǎn)數(shù) 二叉樹(shù)中所有結(jié)點(diǎn)均小于或等于2 所以有 n n0 n1 n2再看二叉樹(shù)中的樹(shù)枝 父結(jié)點(diǎn)和兒子結(jié)點(diǎn)之間的線(xiàn)段 總數(shù) 在二叉樹(shù)中 除根結(jié)點(diǎn)外 其余結(jié)點(diǎn)都有唯一的一個(gè)樹(shù)枝進(jìn)入本結(jié)點(diǎn) 性質(zhì)3證明 24 設(shè)B為二叉樹(shù)中的樹(shù)枝數(shù) 那么有下式成立 B n 1這些樹(shù)枝都是由度為1和度為2的結(jié)點(diǎn)發(fā)出的 一個(gè)度為1的結(jié)點(diǎn)發(fā)出一個(gè)樹(shù)枝 一個(gè)度為2的結(jié)點(diǎn)發(fā)出兩個(gè)樹(shù)枝 所以有 B n1 2n2因此 n0 n2 1 25 二叉樹(shù)的性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度k log2n 1 證明根據(jù)完全二叉樹(shù)的定義和性質(zhì)2可知 高度為k的完全二叉樹(shù)的第一層到第k 1層具有最多的結(jié)點(diǎn)個(gè)數(shù) 總數(shù)為2k 1 1個(gè) 第k層至少具有一個(gè)結(jié)點(diǎn) 至多有2k 1個(gè)結(jié)點(diǎn) 因此 2k 1 1 n 2k 1即2k 1 n 2k對(duì)不等式取對(duì)數(shù) 有k 1 log2n k由于k是整數(shù) 所以有 k log2n 1 26 二叉樹(shù)的性質(zhì)5 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中的結(jié)點(diǎn)按層自上而下 從第1層到第 log2n 1層 每一層按自左至右依次編號(hào) 若設(shè)根結(jié)點(diǎn)的編號(hào)為1 則對(duì)任一編號(hào)為i的結(jié)點(diǎn) 1 i n 有 1 如果i 1 則該結(jié)點(diǎn)是二叉樹(shù)的根結(jié)點(diǎn) 如果i 1 則其父親結(jié)點(diǎn)的編號(hào)為 i 2 2 如果2i n 則編號(hào)為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn) 沒(méi)有兒子 否則 其左兒子的編號(hào)為2i 3 如果2i 1 n 則編號(hào)為i的結(jié)點(diǎn)無(wú)右兒子 否則 其右兒子的編號(hào)為2i 1 27 28 二叉樹(shù) 二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的基本運(yùn)算二叉樹(shù)的遍歷二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)類(lèi)二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 29 二叉樹(shù)常用操作 建樹(shù)create 創(chuàng)建一棵空的二叉樹(shù) 清空clear 刪除二叉樹(shù)中的所有結(jié)點(diǎn) 判空IsEmpty 判別二叉樹(shù)是否為空樹(shù) 找根結(jié)點(diǎn)root 找出二叉樹(shù)的根結(jié)點(diǎn) 找父結(jié)點(diǎn)parent x 找出結(jié)點(diǎn)x的父結(jié)點(diǎn) 找左孩子lchild x 找結(jié)點(diǎn)x的左孩子結(jié)點(diǎn) 找右孩子rchild x 找結(jié)點(diǎn)x的右孩子結(jié)點(diǎn) 刪除左子樹(shù)delLeft x 刪除結(jié)點(diǎn)x的左子樹(shù) 刪除右子樹(shù)delRight x 刪除結(jié)點(diǎn)x的右子樹(shù) 構(gòu)建一棵樹(shù)MakeTree x TL TR 構(gòu)建一棵以x為根結(jié)點(diǎn) 以TL TR為左右子樹(shù)的二叉樹(shù) 遍歷traverse 訪(fǎng)問(wèn)二叉樹(shù)上的每一個(gè)結(jié)點(diǎn) 30 二叉樹(shù) 二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的基本運(yùn)算二叉樹(shù)的遍歷二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)類(lèi)二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 31 二叉樹(shù)的遍歷 二叉樹(shù)的遍歷討論的是如何訪(fǎng)問(wèn)到樹(shù)上的每一個(gè)結(jié)點(diǎn)在線(xiàn)性表中 我們可以沿著后繼鏈訪(fǎng)問(wèn)到所有結(jié)點(diǎn) 而二叉樹(shù)是有分叉的 因此在分叉處必須確定下一個(gè)要訪(fǎng)問(wèn)的節(jié)點(diǎn) 是根結(jié)點(diǎn) 左結(jié)點(diǎn)還是右結(jié)點(diǎn)根據(jù)不同的選擇 有三種遍歷的方法 前序 中序和后序 32 前序遍歷 如果二叉樹(shù)為空 則操作為空否則訪(fǎng)問(wèn)根結(jié)點(diǎn)前序遍歷左子樹(shù)前序遍歷右子樹(shù) 33 中序遍歷 如果二叉樹(shù)為空 則操作為空否則中序遍歷左子樹(shù)訪(fǎng)問(wèn)根結(jié)點(diǎn)中序遍歷右子樹(shù) 34 后序遍歷 如果二叉樹(shù)為空 則操作為空否則后序遍歷左子樹(shù)后序遍歷右子樹(shù)訪(fǎng)問(wèn)根結(jié)點(diǎn) 35 前序 A L B E C D W X 中序 B L E A C W X D 后序 B E L X W D C A 36 前序 中序唯一確定一棵二叉樹(shù) 前序 A B D E F C中序 D B E F A C 前序 B D E F中序 D B E F 前序 E F中序 E F 37 同理 由二叉樹(shù)的后序序列和中序序列同樣可以唯一地確定一棵二叉樹(shù)但是 已知二叉樹(shù)的前序遍歷序列和后序遍歷序列卻無(wú)法確定一棵二叉樹(shù) 比如 已知一棵二叉樹(shù)的前序遍歷序列為A B 后序遍歷序列為B A 我們雖然可以很容易地得知結(jié)點(diǎn)A為根結(jié)點(diǎn) 但是無(wú)法確定結(jié)點(diǎn)B是結(jié)點(diǎn)A的左兒子還是右兒子 因?yàn)锽無(wú)論是結(jié)點(diǎn)A的右兒子還是左兒子都是符合已知條件的 38 二叉樹(shù) 二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的基本運(yùn)算二叉樹(shù)的遍歷二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)類(lèi)二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 39 二叉樹(shù)的實(shí)現(xiàn) 順序?qū)崿F(xiàn)鏈接實(shí)現(xiàn) 40 完全二叉樹(shù)的順序存儲(chǔ) 根據(jù)編號(hào)性質(zhì) 可以省略左右孩子字段 41 普通二叉樹(shù)的順序存儲(chǔ) D B A H I 將普通的樹(shù)修補(bǔ)成完全二叉樹(shù) 42 右單支樹(shù)的實(shí)例 43 順序?qū)崿F(xiàn)的特點(diǎn) 存儲(chǔ)空間的浪費(fèi) 一般只用于一些特殊的場(chǎng)合 如靜態(tài)的并且結(jié)點(diǎn)個(gè)數(shù)已知的完全二叉樹(shù)或接近完全二叉樹(shù)的二叉樹(shù) 44 二叉樹(shù)的實(shí)現(xiàn) 順序?qū)崿F(xiàn)鏈接實(shí)現(xiàn) 45 鏈接存儲(chǔ)結(jié)構(gòu) 標(biāo)準(zhǔn)形式 二叉鏈表 廣義標(biāo)準(zhǔn)形式 三叉鏈表 46 標(biāo)準(zhǔn)形式的實(shí)例 47 廣義標(biāo)準(zhǔn)形式的實(shí)例 48 二叉樹(shù)基本運(yùn)算的實(shí)現(xiàn) 由于二叉樹(shù)是一個(gè)遞歸的結(jié)構(gòu) 因此二叉樹(shù)中的許多運(yùn)算的實(shí)現(xiàn)都是基于遞歸函數(shù) create 將指向根結(jié)點(diǎn)的指針設(shè)為空指針就可以了 即root NULL isEmpty 只需要判別root即可 如果root等于空指針 返回true 否則 返回false root 返回root指向的結(jié)點(diǎn)的數(shù)據(jù)部分 如果二叉樹(shù)是空樹(shù) 則返回一個(gè)特殊的標(biāo)記 49 clear 從遞歸的觀(guān)點(diǎn)看 一棵二叉樹(shù)由三部分組成 根結(jié)點(diǎn) 左子樹(shù) 右子樹(shù) 刪除一棵二叉樹(shù)就是刪除這三個(gè)部分 根結(jié)點(diǎn)的刪除很簡(jiǎn)單 只要回收根結(jié)點(diǎn)的空間 把指向根結(jié)點(diǎn)的指針設(shè)為空指針 如何刪除左子樹(shù)和右子樹(shù)呢 記住左子樹(shù)也是一棵二叉樹(shù) 右子樹(shù)也是一棵二叉樹(shù) 左右子樹(shù)的刪除和整棵樹(shù)的刪除過(guò)程是一樣的 50 If 左子樹(shù)非空 遞歸刪除左子樹(shù) If 右子樹(shù)非空 遞歸刪除右子樹(shù) deleteroot指向的結(jié)點(diǎn) root NULL 51 parent x 在二叉鏈表的實(shí)現(xiàn)中一般不實(shí)現(xiàn)這個(gè)操作lchild x 返回結(jié)點(diǎn)x的left值rchild x 返回結(jié)點(diǎn)x的right值delLeft x 對(duì)左子樹(shù)調(diào)用clear函數(shù)刪除左子樹(shù) 然后將結(jié)點(diǎn)x的left置為NULL delRight x 對(duì)右子樹(shù)調(diào)用clear函數(shù)刪除右子樹(shù) 然后將結(jié)點(diǎn)x的right置為NULL makeTree x TL TR 為x申請(qǐng)一個(gè)結(jié)點(diǎn) 讓它的left指向TL的根結(jié)點(diǎn) right指向TR的根結(jié)點(diǎn) 52 二叉樹(shù)的遍歷 前序 訪(fǎng)問(wèn)根結(jié)點(diǎn) If 左子樹(shù)非空 前序遍歷左子樹(shù) If 右子樹(shù)非空 前序遍歷右子樹(shù) 其他兩種遍歷只要調(diào)整一下次序即可 53 二叉樹(shù) 二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的基本運(yùn)算二叉樹(shù)的遍歷二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)類(lèi)二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 54 二叉樹(shù)類(lèi) 由于二叉樹(shù)的順序?qū)崿F(xiàn)僅用于一些特殊的場(chǎng)合 大多數(shù)情況下 二叉樹(shù)都是用二叉鏈表實(shí)現(xiàn) 所以?xún)H介紹用二叉鏈表實(shí)現(xiàn)的二叉樹(shù)類(lèi) 55 二叉樹(shù)類(lèi)的設(shè)計(jì) 標(biāo)準(zhǔn)的鏈接存儲(chǔ)由兩個(gè)類(lèi)組成 結(jié)點(diǎn)類(lèi)和樹(shù)類(lèi) 和線(xiàn)性表的實(shí)現(xiàn)類(lèi)似 這個(gè)結(jié)點(diǎn)類(lèi)是樹(shù)類(lèi)專(zhuān)用的 因此可作為樹(shù)類(lèi)的私有內(nèi)嵌類(lèi) 56 結(jié)點(diǎn)類(lèi)Node的設(shè)計(jì) 存儲(chǔ)和處理樹(shù)上每一個(gè)結(jié)點(diǎn)的類(lèi) 數(shù)據(jù)成員包括 結(jié)點(diǎn)的數(shù)據(jù)及左右孩子的指針 結(jié)點(diǎn)的操作包括 構(gòu)造和析構(gòu) 57 二叉樹(shù)類(lèi)的設(shè)計(jì) 樹(shù)的存儲(chǔ) 存儲(chǔ)指向根結(jié)點(diǎn)的指針樹(shù)的操作 樹(shù)的標(biāo)準(zhǔn)操作增加了一個(gè)建樹(shù)的函數(shù) 58 遞歸函數(shù)的設(shè)計(jì) 對(duì)于二叉樹(shù)類(lèi)的用戶(hù)來(lái)說(shuō) 他并不需要知道這些操作時(shí)用遞歸函數(shù)實(shí)現(xiàn)的 對(duì)用戶(hù)來(lái)說(shuō) 調(diào)用這些函數(shù)并不需要參數(shù)但遞歸函數(shù)必須有一個(gè)控制遞歸終止的參數(shù)設(shè)計(jì)時(shí) 我們將用戶(hù)需要的函數(shù)原型作為公有的成員函數(shù) 每個(gè)公有成員函數(shù)對(duì)應(yīng)一個(gè)私有的 帶遞歸參數(shù)的成員函數(shù) 公有函數(shù)調(diào)用私有函數(shù)完成相應(yīng)的功能 59 二叉樹(shù)類(lèi)的定義 templateclassBinaryTree private structNode Node left right 結(jié)點(diǎn)的左 右兒子的地址Typedata 結(jié)點(diǎn)的數(shù)據(jù)信息Node left NULL right NULL Node Typeitem Node L NULL Node R NULL data item left L right R Node Node root 二叉樹(shù)的根結(jié)點(diǎn) 60 public BinaryTree root NULL 構(gòu)造空二叉樹(shù)BinaryTree constType 61 voidmakeTree constType 62 boolisEmpty const returnroot NULL voidclear if root NULL clear root root NULL intsize const returnsize root intheight const returnheight root voidpreOrder const voidpostOrder const voidmidOrder const voidcreateTree Typeflag 63 private voidclear Node t intheight Node t const intsize Node t const voidpreOrder Node t const voidpostOrder Node t const voidmidOrder Node t const 64 求規(guī)模操作的實(shí)現(xiàn) 用遞歸的觀(guān)點(diǎn)來(lái)看 二叉樹(shù)是由根結(jié)點(diǎn)和左右子樹(shù)構(gòu)成 因此 樹(shù)的規(guī)模應(yīng)該為 左子樹(shù)的規(guī)模 右子樹(shù)的規(guī)模 1 根 65 size intsize const returnsize root intsize Node t const if t NULL return0 return1 size t left size t right 66 求高度操作的實(shí)現(xiàn) 用遞歸的觀(guān)點(diǎn)來(lái)看 二叉樹(shù)是由根結(jié)點(diǎn)和左右子樹(shù)構(gòu)成 因此 樹(shù)的高度應(yīng)該為 1 max 左子樹(shù)高度 右子樹(shù)高度 67 height intheight const returnheight root intheight Node t const if t NULL return0 else intlt height t left rt height t right return1 lt rt lt rt 68 三種遍歷的實(shí)現(xiàn) 樹(shù)的遍歷本身就是用遞歸形式描述的 因此用遞歸函數(shù)實(shí)現(xiàn)是很自然的 69 preOrder voidpreOrder const if root NULL coutdataleft preOrder t right 70 midOrder voidmidOrder const if root NULL coutleft coutdataright 71 postOrder voidpostOrder const if root NULL coutleft postOrder t right coutdata 72 樹(shù)的刪除的實(shí)現(xiàn) 樹(shù)的刪除可以用遞歸的方法來(lái)實(shí)現(xiàn) 先遞歸刪除左右子樹(shù) 再刪除根結(jié)點(diǎn)本身 73 clear voidclear if root NULL clear root root NULL voidclear Node t if t left NULL clear t left if t right NULL clear t right deletet 74 創(chuàng)建一棵樹(shù) 創(chuàng)建過(guò)程 先輸入根結(jié)點(diǎn)的值 創(chuàng)建根節(jié)點(diǎn)對(duì)已添加到樹(shù)上的每個(gè)結(jié)點(diǎn) 依次輸入它的兩個(gè)兒子的值 如果沒(méi)有兒子 則輸入一個(gè)特定值實(shí)現(xiàn)工具 使用一個(gè)隊(duì)列 將新加入到樹(shù)中的結(jié)點(diǎn)放入隊(duì)列依次出隊(duì) 對(duì)每個(gè)出隊(duì)的元素輸入它的兒子 75 隊(duì)列的變化 76 createTree templatevoidBinaryTree createTree Typeflag linkQueueque Node tmp Typex ldata rdata 創(chuàng)建樹(shù) 輸入flag表示空cout x root newNode x que enQueue root 77 while que isEmpty tmp que deQueue coutdata ldata rdata if ldata flag que enQueue tmp left newNode ldata if rdata flag que enQueue tmp right newNode rdata cout createcompleted n 78 二叉樹(shù)類(lèi)的應(yīng)用 創(chuàng)建一棵由整型值組成的二叉樹(shù)求高度求規(guī)模按前序 中序和后序遍歷歸并兩棵樹(shù) 79 intmain BinaryTreetree tree1 M tree2 tree createTree cout 高度為 tree height endl cout 規(guī)模為 tree size endl tree PreOrder tree MidOrder tree PostOrder 80 tree2 makeTree Y tree tree1 cout endl cout 高度為 tree2 height endl cout 規(guī)模為 tree2 size endl tree2 PreOrder tree2 MidOrder tree2 PostOrder return0 81 執(zhí)行實(shí)例 輸入根結(jié)點(diǎn) A輸入A的兩個(gè)兒子 表示空結(jié)點(diǎn) LC輸入L的兩個(gè)兒子 表示空結(jié)點(diǎn) BE輸入C的兩個(gè)兒子 表示空結(jié)點(diǎn) D輸入B的兩個(gè)兒子 表示空結(jié)點(diǎn) 輸入E的兩個(gè)兒子 表示空結(jié)點(diǎn) 輸入D的兩個(gè)兒子 表示空結(jié)點(diǎn) W 輸入W的兩個(gè)兒子 表示空結(jié)點(diǎn) X輸入X的兩個(gè)兒子 表示空結(jié)點(diǎn) 82 高度為 5規(guī)模為 8前序遍歷 ALBECDWX中序遍歷 BLEACWXD后序遍歷 BELXWDCA高度為 6規(guī)模為 10前序遍歷 YALBECDWXM中序遍歷 BLEACWXDYM后序遍歷 BELXWDCAMY 83 二叉樹(shù) 二叉樹(shù)的概念二叉樹(shù)的性質(zhì)二叉樹(shù)的基本運(yùn)算二叉樹(shù)的遍歷二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)類(lèi)二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 84 二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 遞歸是程序設(shè)計(jì)中強(qiáng)有力的工具 遞歸程序結(jié)構(gòu)清晰 明了 美觀(guān) 遞歸程序的弱點(diǎn) 它的時(shí)間 空間的效率比較低 所以在實(shí)際使用中 我們常常希望使用它的非遞歸版本二叉樹(shù)的遍歷也是如此 盡管二叉樹(shù)遍歷的遞歸函數(shù)非常簡(jiǎn)潔 但有時(shí)我們還是希望使用速度更快的非遞歸函數(shù) 85 二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 前序遍歷中序遍歷后序遍歷 86 前序遍歷的非遞歸實(shí)現(xiàn) 前序遍歷第一個(gè)被訪(fǎng)問(wèn)的結(jié)點(diǎn)是根結(jié)點(diǎn) 然后訪(fǎng)問(wèn)左子樹(shù) 最后訪(fǎng)問(wèn)右子樹(shù) 可以設(shè)置一個(gè)棧 保存將要訪(fǎng)問(wèn)的樹(shù)的樹(shù)根 開(kāi)始時(shí) 把二叉樹(shù)的根結(jié)點(diǎn)存入棧中 然后重復(fù)以下過(guò)程 直到棧為空 從棧中取出一個(gè)結(jié)點(diǎn) 輸出根結(jié)點(diǎn)的值 然后把右子樹(shù) 左子樹(shù)放入棧中 87 前序遍歷的過(guò)程 輸出 ALBECDWX 88 templatevoidBinaryTree preOrder const linkStacks Node current coutdata if current right NULL s push current right if current left NULL s push current left 89 二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 前序遍歷中序遍歷后序遍歷 90 中序遍歷的非遞歸實(shí)現(xiàn) 采用一個(gè)棧存放要遍歷的樹(shù)的樹(shù)根中序遍歷中 先要遍歷左子樹(shù) 接下去才能訪(fǎng)問(wèn)根結(jié)點(diǎn) 因此 當(dāng)根結(jié)點(diǎn)出棧時(shí) 我們不能訪(fǎng)問(wèn)它 而要訪(fǎng)問(wèn)它的左子樹(shù) 此時(shí)要把樹(shù)根結(jié)點(diǎn)暫存一下 存哪里 由于左子樹(shù)訪(fǎng)問(wèn)完后還要訪(fǎng)問(wèn)根結(jié)點(diǎn) 因此仍可以把它存在棧中 接著左子樹(shù)也進(jìn)棧 此時(shí)執(zhí)行出棧操作 出棧的是左子樹(shù) 左子樹(shù)問(wèn)結(jié)束后 再次出棧的是根結(jié)點(diǎn) 此時(shí)根結(jié)點(diǎn)可被訪(fǎng)問(wèn) 根結(jié)點(diǎn)訪(fǎng)問(wèn)后 訪(fǎng)問(wèn)右子樹(shù) 則將右子樹(shù)進(jìn)棧 91 棧元素的設(shè)計(jì) 在中序遍歷中根結(jié)點(diǎn)要進(jìn)棧兩次 當(dāng)要遍歷一棵樹(shù)時(shí) 將根結(jié)點(diǎn)進(jìn)棧 根結(jié)點(diǎn)第一次出棧時(shí) 它不能被訪(fǎng)問(wèn) 必須重新進(jìn)棧 并將左子樹(shù)也進(jìn)棧 表示接下去要訪(fǎng)問(wèn)的是左子樹(shù) 根結(jié)點(diǎn)第二次出棧時(shí) 才能被訪(fǎng)問(wèn) 并將右子樹(shù)進(jìn)棧 表示右子樹(shù)可以訪(fǎng)問(wèn)了 在中序遍歷時(shí)不僅要記住需要訪(fǎng)問(wèn)哪一棵樹(shù) 而且還必須記住根結(jié)點(diǎn)是在第幾次進(jìn)棧 92 中序遍歷的過(guò)程 輸出 B L E A C W X D 93 StNode類(lèi)的定義 structStNode Node node intTimesPop StNode Node N NULL node N TimesPop 0 94 中序遍歷的非遞歸實(shí)現(xiàn) templatevoidBinaryTree midOrder const linkStacks StNodecurrent root cout 中序遍歷 s push current 95 while s isEmpty current s pop if current TimesPop 2 coutdata if current node right NULL s push StNode current node right else s push current if current node left NULL s push StNode current node left 96 二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 前序遍歷中序遍歷后序遍歷 97 后序遍歷的非遞歸實(shí)現(xiàn) 將中序遍歷的非遞歸實(shí)現(xiàn)的思想進(jìn)一步延伸 可以得到后序遍歷的非遞歸實(shí)現(xiàn) 當(dāng)以后序遍歷一棵二叉樹(shù)時(shí) 先將樹(shù)根進(jìn)棧 表示要遍歷這棵樹(shù) 根結(jié)點(diǎn)第一次出棧時(shí) 根結(jié)點(diǎn)不能訪(fǎng)問(wèn) 應(yīng)該訪(fǎng)問(wèn)左子樹(shù) 于是 根結(jié)點(diǎn)重新入棧 并將左子樹(shù)也入棧 根結(jié)點(diǎn)第二次出棧時(shí) 根結(jié)點(diǎn)還是不能訪(fǎng)問(wèn) 要先訪(fǎng)問(wèn)右子樹(shù) 于是 根結(jié)點(diǎn)再次入棧 右子樹(shù)也入棧 當(dāng)根結(jié)點(diǎn)第三次出棧時(shí) 表示右子樹(shù)遍歷結(jié)束 此時(shí) 根結(jié)點(diǎn)才能被訪(fǎng)問(wèn) 98 后序遍歷的過(guò)程 輸出 B E L 99 輸出 B L E X W D C A 100 后序遍歷的非遞歸實(shí)現(xiàn) templatevoidBinaryTree postOrder const linkStacks StNodecurrent root cout 后序遍歷 s push current 101 while s isEmpty current s pop if current TimesPop 3 coutdata continue s push current if current TimesPop 1 if current node left NULL s push StNode current node left else if current node right NULL s push StNode current node right 102 第五章樹(shù) 樹(shù)的概念二叉樹(shù)表達(dá)式樹(shù)哈夫曼樹(shù)與哈夫曼編碼樹(shù)和森林 103 表達(dá)式樹(shù) 算術(shù)表達(dá)式可以表示為一棵二叉樹(shù) 如 4 2 10 4 6 2 2對(duì)這棵樹(shù)后序遍歷可得到結(jié)果設(shè)計(jì)一個(gè)類(lèi) 利用表達(dá)式樹(shù)計(jì)算由四則運(yùn)算組成的表達(dá)式 104 樹(shù)的構(gòu)建過(guò)程 3 4 5 7 9 8構(gòu)建左節(jié)點(diǎn)3 3 4 5 7 9 8構(gòu)建根節(jié)點(diǎn) 4 5 7 9 8構(gòu)建右節(jié)點(diǎn)4 5 7 9 8構(gòu)建根節(jié)點(diǎn) 原樹(shù)作為左子樹(shù) 5 7 9 8構(gòu)建右節(jié)點(diǎn)5 105 7 9 8下移到右節(jié)點(diǎn) 構(gòu)建根節(jié)點(diǎn) 原來(lái)的右節(jié)點(diǎn)作為它的左節(jié)點(diǎn) 7 9 8構(gòu)建右節(jié)點(diǎn)7 9 8創(chuàng)建根 原樹(shù)作為左子樹(shù) 106 8上移到根 創(chuàng)建根 原樹(shù)作為左子樹(shù) 88作為左節(jié)點(diǎn) 9 89作為右子樹(shù) 107 構(gòu)建過(guò)程總結(jié) 順序掃描中綴表達(dá)式當(dāng)掃描到的是運(yùn)算數(shù) 先檢查當(dāng)前的表達(dá)式樹(shù)是否存在 如果不存在 則表示掃描到的是第一個(gè)運(yùn)算數(shù) 將它作為樹(shù)根 如果樹(shù)存在 則將此運(yùn)算數(shù)作為前一運(yùn)算符的右孩子 如果掃描到的是 或 將它作為根結(jié)點(diǎn) 原來(lái)的樹(shù)作為它的左子樹(shù) 108 構(gòu)建過(guò)程總結(jié)續(xù) 如果掃描到的是 或 則與根結(jié)點(diǎn)比較 如果根結(jié)點(diǎn)也是 或 則根結(jié)點(diǎn)應(yīng)該先執(zhí)行 于是將當(dāng)前運(yùn)算符作為根結(jié)點(diǎn) 原來(lái)的樹(shù)作為左子樹(shù) 如果根結(jié)點(diǎn)是 或 則當(dāng)前運(yùn)算符應(yīng)該先運(yùn)算 于是將它作為右子樹(shù)的根 原來(lái)的右子樹(shù)作為它的左子樹(shù) 在遇到運(yùn)算數(shù)時(shí) 如何知道它前面的運(yùn)算符是誰(shuí) 這只需要判別根結(jié)點(diǎn)有沒(méi)有右孩子 如果沒(méi)有右孩子 則運(yùn)算數(shù)是根結(jié)點(diǎn)的右運(yùn)算數(shù) 否則就是根結(jié)點(diǎn)右孩子的右運(yùn)算數(shù) 109 構(gòu)建過(guò)程 括號(hào)的處理 4 5 8 9 10遇到括號(hào) 將括號(hào)內(nèi)的子表達(dá)式構(gòu)建一棵子樹(shù)作為整個(gè)表達(dá)式的一個(gè)運(yùn)算數(shù) 8 9 10 作為根節(jié)點(diǎn) 括號(hào)內(nèi)的子樹(shù)作為左子樹(shù) 8 9 10括號(hào)內(nèi)的子表達(dá)式構(gòu)建一棵子樹(shù)作為整棵樹(shù)的右子樹(shù) 10 作為根節(jié)點(diǎn) 原樹(shù)作為左子樹(shù) 10作為右子樹(shù) 110 表達(dá)式樹(shù)類(lèi)的設(shè)計(jì) 數(shù)據(jù)成員 指向樹(shù)根節(jié)點(diǎn)的指針公有成員函數(shù) 構(gòu)造函數(shù) 調(diào)用create從表達(dá)式構(gòu)建一棵樹(shù)result 計(jì)算表達(dá)式的結(jié)果 用后序遍歷過(guò)程私有成員函數(shù) Create帶有遞歸參數(shù)的result函數(shù)getToken create函數(shù)所用的子函數(shù) 用于從表達(dá)式中獲取一個(gè)語(yǔ)法單位 111 結(jié)點(diǎn)的設(shè)計(jì) 在表達(dá)式樹(shù)中 每個(gè)葉子結(jié)點(diǎn)保存的是一個(gè)運(yùn)算數(shù) 每個(gè)非葉結(jié)點(diǎn)保存的是一個(gè)運(yùn)算符 結(jié)點(diǎn)的數(shù)據(jù)部分應(yīng)該包括兩個(gè)部分 結(jié)點(diǎn)的類(lèi)型和值 112 calc類(lèi)的定義 classcalc enumType DATA ADD SUB MULTI DIV OPAREN CPAREN EOL structnode Typetype intdata node lchild rchild node Typet intd 0 node lc NULL node rc NULL type t data d lchild lc rchild rc node root 113 public calc char s root create s intresult if root NULL return0 returnresult root private node create char 114 私有create函數(shù)的實(shí)現(xiàn) calc node calc create char 115 caseCPAREN caseEOL returnroot caseADD caseSUB if root NULL root newnode returnType 0 p elseroot newnode returnType 0 root break caseMULTI caseDIV if root NULL root newnode returnType 0 p elseif root type MULTI root type DIV root newnode returnType 0 root elseroot rchild newnode returnType 0 root rchild returnroot 116 getToken calc Typecalc getToken char 117 if s 0 returnEOL type s s switch type case returnADD case returnSUB case returnMULTI case returnDIV case returnOPAREN case returnCPAREN default returnEOL 118 私有的result函數(shù)的實(shí)現(xiàn) intcalc result calc node t intnum1 num2 if t type DATA returnt data num1 result t lchild num2 result t rchild switch t type caseADD t data num1 num2 break caseSUB t data num1 num2 break caseMULTI t data num1 num2 break caseDIV t data num1 num2 returnt data 119 Calc類(lèi)的應(yīng)用 intmain calcexp 2 3 1 2 3 6 6 2 3 5 2 2 cout exp result endl return0 120 Calc類(lèi)的特點(diǎn) 使用時(shí)和基于棧實(shí)現(xiàn)的calc類(lèi)完全一樣缺點(diǎn)沒(méi)有考慮表達(dá)式不正確的情況沒(méi)有考慮乘方運(yùn)算 121 第五章樹(shù) 樹(shù)的概念二叉樹(shù)表達(dá)式樹(shù)哈夫曼樹(shù)與哈夫曼編碼樹(shù)和森林 122 字符的機(jī)內(nèi)表示 在計(jì)算機(jī)中每個(gè)字符是用一個(gè)編碼表示大多數(shù)編碼系統(tǒng)都采用等長(zhǎng)編碼 如ASCII編碼例如在某段文本中用到了下列字符 括號(hào)中是它們出現(xiàn)的頻率 a 10 e 15 i 12 s 3 t 4 空格 13 換行 1 如采用定長(zhǎng)編碼 7個(gè)不同的字符至少要用3位編碼 123 總存儲(chǔ)量 3 10 15 12 3 4 13 1 3 58 174bit 124 這個(gè)編碼可以對(duì)應(yīng)成如下的完全二叉樹(shù) 左枝為0 右枝為1 125 很顯然 將換行上移一層可以減少存儲(chǔ)量 不等長(zhǎng)編碼可以減少存儲(chǔ)量 126 前綴編碼 字符只放在葉結(jié)點(diǎn)中字符編碼可以有不同的長(zhǎng)度由于字符只放在葉結(jié)點(diǎn)中 所以每個(gè)字符的編碼都不可能是其他字符編碼的前綴前綴編碼可被惟一解碼 127 哈夫曼樹(shù) 哈夫曼樹(shù)是一棵最小代價(jià)的二叉樹(shù) 在這棵樹(shù)上 所有的字符都包含在葉結(jié)點(diǎn)上 要使得整棵樹(shù)的代價(jià)最小 顯然權(quán)值大的葉子應(yīng)當(dāng)盡量靠近樹(shù)根 權(quán)值小的葉子可以適當(dāng)離樹(shù)根遠(yuǎn)一些 128 總共用了146bit 哈夫曼編碼 129 哈夫曼算法 1 給定一個(gè)具有n個(gè)權(quán)值 w1 w2 wn 的結(jié)點(diǎn)的集合F T1 T2 Tn 2 初始時(shí) 設(shè)集合A F 3 執(zhí)行i 1至n 1的循環(huán) 在每次循環(huán)時(shí)執(zhí)行以下操作從當(dāng)前集合中選取權(quán)值最小 次最小的兩個(gè)結(jié)點(diǎn) 以這兩個(gè)結(jié)點(diǎn)作為內(nèi)部結(jié)點(diǎn)bi的左右兒子 bi的權(quán)值為其左右兒子權(quán)值之和 在集合中去除這兩個(gè)權(quán)值最小 次最小的結(jié)點(diǎn) 并將內(nèi)部結(jié)點(diǎn)bI加入其中 這樣 在集合A中 結(jié)點(diǎn)個(gè)數(shù)便減少了一個(gè) 這樣 在經(jīng)過(guò)了n 1次循環(huán)之后 集合A中只剩下了一個(gè)結(jié)點(diǎn) 這個(gè)結(jié)點(diǎn)就是根結(jié)點(diǎn) 130 a 10 e 15 i 12 s 3 t 4 空格 13 換行 1 131 132 133 哈夫曼編碼的生成 每個(gè)字符的編碼是根節(jié)點(diǎn)到該字符的路徑左枝為0 右枝為1 134 哈夫曼樹(shù)類(lèi)的實(shí)現(xiàn) 為了便于找出一組符號(hào)的哈夫曼編碼 我們可以定義一個(gè)哈夫曼樹(shù)類(lèi) 哈夫曼樹(shù)類(lèi)的對(duì)象可以接受一組符號(hào)以及對(duì)應(yīng)的權(quán)值 并告知每個(gè)符號(hào)對(duì)應(yīng)的哈夫曼編碼 因此 哈夫曼樹(shù)類(lèi)應(yīng)該有兩個(gè)公有的成員函數(shù) 構(gòu)造函數(shù) 接受一組待編碼的符號(hào)以及它們的權(quán)值 構(gòu)造一棵哈夫曼樹(shù) GetCode函數(shù)根據(jù)保存的哈夫曼樹(shù)為每個(gè)葉結(jié)點(diǎn)生成哈夫曼編碼 135 哈夫曼樹(shù)的存儲(chǔ) 在哈夫曼樹(shù)中 每個(gè)要編碼的元素是一個(gè)葉結(jié)點(diǎn) 其它結(jié)點(diǎn)都是度數(shù)為2的節(jié)點(diǎn)一旦給定了要編碼的元素個(gè)數(shù) 由n0 n2 1可知哈夫曼樹(shù)的大小為2n 1哈夫曼樹(shù)可以用一個(gè)大小為2n的數(shù)組來(lái)存儲(chǔ) 0節(jié)點(diǎn)不用 根存放在節(jié)點(diǎn)1 葉結(jié)點(diǎn)依次放在n 1到2n的位置每個(gè)數(shù)組元素保存的信息 結(jié)點(diǎn)的數(shù)據(jù) 權(quán)值和父結(jié)點(diǎn)和左右孩子的位置 136 137 13 12 11 10 9 8 7 6 5 4 3 2 1 0 13 11 7 12 8 3 右 10 6 5 9 4 2 左 6 3 5 6 3 2 4 5 4 2 1 1 父 1 13 4 3 12 15 10 4 8 18 25 33 58 權(quán) nl sp t s i e a 值 生成過(guò)程 138 編碼的產(chǎn)生 生成a的代碼 結(jié)點(diǎn)4的右孩子 1 結(jié)點(diǎn)4是結(jié)點(diǎn)2的左孩子 01 結(jié)點(diǎn)2是結(jié)點(diǎn)1的左孩子 001 對(duì)每個(gè)結(jié)點(diǎn) 從葉子往根推進(jìn) 是左枝加0 是右枝加1 139 哈夫曼樹(shù)類(lèi) 存儲(chǔ)設(shè)計(jì)結(jié)點(diǎn)的表示 結(jié)點(diǎn)的數(shù)據(jù) 權(quán)值和父結(jié)點(diǎn)和左右孩子的位置哈夫曼樹(shù)的存儲(chǔ) 一個(gè)結(jié)點(diǎn)數(shù)組以及一個(gè)整型數(shù)據(jù)成員 保存數(shù)組的大小 操作構(gòu)建一棵哈夫曼樹(shù) 構(gòu)造函數(shù)實(shí)現(xiàn) 給出節(jié)點(diǎn)數(shù)據(jù)數(shù)組 權(quán)值數(shù)組和數(shù)據(jù)個(gè)數(shù)獲取樹(shù)上節(jié)點(diǎn)的哈夫曼編碼返回一個(gè)數(shù)組 數(shù)組的元素由數(shù)據(jù)和編碼兩部分組成的 140 templateclasshfTree private structNode Typedata 結(jié)點(diǎn)值intweight 結(jié)點(diǎn)的權(quán)值intparent left right Node elem intlength 141 public structhfCode Typedata stringcode hfTree constType x constint w intsize voidgetCode hfCoderesult hfTree delete elem 142 構(gòu)造函數(shù) templatehfTree hfTree constType v constint w intsize constintMAX INT 32767 intmin1 min2 最小樹(shù) 次最小樹(shù)的權(quán)值intx y 最小樹(shù) 次最小樹(shù)的下標(biāo) 置初值length 2 size elem newNode length for inti size i length i elem i weight w i size elem i data v i size elem i parent elem i left elem i right 0 143 構(gòu)造新的二叉樹(shù)for i size 1 i 0 i min1 min2 MAX INT x y 0 for intj i 1 j length j if elem j parent 0 if elem j weight min1 min2 min1 min1 elem j weight x y y j elseif elem j weight min2 min2 elem j weight x j elem i weight min1 min2 elem i left x elem i right y elem i parent 0 elem x parent i elem y parent i 144 getCode的偽代碼 getCode hfCoderesult for inti size i length i result i size data elem i data result i size code p elem i parent s i while p不等于0 if p的左孩子是 s result i size code前添加 0 elseresult i size code前添 1 移到上一層 145 getCode代碼 templatevoidhfTree getCode hfCoderesult intsize length 2 intp s s是追溯過(guò)程中正在處理的結(jié)點(diǎn) p是s的父結(jié)點(diǎn)下標(biāo)for inti size i length i result i size data elem i data result i size code p elem i parent s i while p if elem p left s result i size code 0 result i size code elseresult i size code 1 result i size code s p p elem p parent 146 哈夫曼類(lèi)的使用 為下列符號(hào)集生成哈夫曼編碼 a 10 e 15 i 12 s 3 t 4 d 13 n 1 147 intmain charch aeistdn intw 10 15 12 3 4 13 1 hfTreetree ch w 7 hfTree hfCoderesult 7 tree getCode result for inti 0 i 7 i cout result i data result i code endl return0 148 第五章樹(shù) 樹(shù)的概念二叉樹(shù)表達(dá)式樹(shù)哈夫曼樹(shù)與哈夫曼編碼樹(shù)和森林 149 樹(shù)和森林 樹(shù)的存儲(chǔ)實(shí)現(xiàn)樹(shù)的遍歷樹(shù) 森林和二叉樹(shù) 150 樹(shù)的存儲(chǔ)結(jié)構(gòu) 標(biāo)準(zhǔn)形式 樹(shù)中的每個(gè)結(jié)點(diǎn)除有數(shù)據(jù)字段之外 還有K個(gè)指針字段 其中K為樹(shù)的度 data son1 廣義標(biāo)準(zhǔn)形式 在標(biāo)準(zhǔn)形式的基礎(chǔ)上 再增加指向父親結(jié)點(diǎn)的指針場(chǎng) son2 sonk parent 151 E g 度數(shù)K 3的樹(shù)的廣義標(biāo)準(zhǔn)存儲(chǔ) 值s1s2s3p0A123 11B45 102C6 1 103D78 104L 1 1 115E 1 1 116F 1 1 127G9 1 138H 1 1 139I 1 1 17 1表示空缺點(diǎn) 空指針字段太多 多達(dá) K 1 n 2個(gè) 152 孩子鏈表示法 將每個(gè)結(jié)點(diǎn)的所有孩子組織成一個(gè)鏈表 樹(shù)的節(jié)點(diǎn)由兩部分組成 存儲(chǔ)數(shù)據(jù)元素值的數(shù)據(jù)部分指向孩子鏈的指針如果樹(shù)的所有結(jié)點(diǎn)存放在一個(gè)數(shù)組中 這個(gè)數(shù)組稱(chēng)為表頭數(shù)組 這種存儲(chǔ)方式稱(chēng)為靜態(tài)的孩子鏈表 將樹(shù)的所有結(jié)點(diǎn)組織成一個(gè)鏈表 稱(chēng)為動(dòng)態(tài)的孩子鏈表 153 154 孩子兄弟鏈表示法 實(shí)質(zhì)上是用二叉樹(shù)表示一棵樹(shù) 樹(shù)中的每個(gè)結(jié)點(diǎn)有數(shù)據(jù)字段 指向它的第一棵子樹(shù)樹(shù)根的指針字段 指向它的兄弟結(jié)點(diǎn)的指針字段 155 156 雙親表示法 通過(guò)指向父結(jié)點(diǎn)的指針將樹(shù)中所有的結(jié)點(diǎn)組織在一起在雙親表示法中 每個(gè)結(jié)點(diǎn)由兩部分組成 存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)字段存儲(chǔ)父結(jié)點(diǎn)位置的父指針字段這種表示法對(duì)求指定結(jié)點(diǎn)的祖先的操作很方便 但對(duì)求指定結(jié)點(diǎn)的子孫則不方便 只適合某些應(yīng)用 如不相交集的存儲(chǔ) 157 158 樹(shù)和森林 樹(shù)的存儲(chǔ)實(shí)現(xiàn)樹(shù)的遍歷樹(shù) 森林和二叉樹(shù) 159 前序遍歷 訪(fǎng)問(wèn)根結(jié)點(diǎn) 前序遍歷根結(jié)點(diǎn)的第一棵子樹(shù) 前序遍歷它的第二棵子樹(shù) 前序遍歷它的最后一棵子樹(shù) 160 后序遍歷 后序遍歷根結(jié)點(diǎn)的第一棵子樹(shù) 后序遍歷它的第二棵子樹(shù) 后序遍歷它的最后一棵子樹(shù) 訪(fǎng)問(wèn)根結(jié)點(diǎn) 161 層次遍歷 訪(fǎng)問(wèn)根結(jié)點(diǎn) 若第i層已被訪(fǎng)問(wèn) 且第i 1層的結(jié)點(diǎn)尚未被訪(fǎng)問(wèn) 則從左到右依次訪(fǎng)問(wèn)第i 1層的結(jié)點(diǎn) 162 前序 A B L E C F D G I H后序 L E B F C I G H D A層次 A B C D L E F G H I 163 樹(shù)和森林 樹(shù)的存儲(chǔ)實(shí)現(xiàn)樹(shù)的遍歷樹(shù) 森林和二叉樹(shù) 164 樹(shù) 森林和二叉樹(shù) 二叉樹(shù)是一種結(jié)構(gòu)最簡(jiǎn)單 運(yùn)算最簡(jiǎn)便的樹(shù)形結(jié)構(gòu) 但對(duì)很多問(wèn)題來(lái)講 其自然的描述形態(tài)是樹(shù)或森林 樹(shù)的孩子兄弟鏈表示法就是將一棵樹(shù)表示成二叉樹(shù)的形態(tài) 這樣就可以將二叉樹(shù)中的許多方法用在樹(shù)的處理中 165 A B C D F G E H I J 166 森林 森林通常定義為樹(shù)的集合或樹(shù)的序列 森林的存儲(chǔ) 存儲(chǔ)一個(gè)森林要包括兩方面的內(nèi)容存儲(chǔ)森林中的每一棵樹(shù)表示這些樹(shù)是屬于同一個(gè)森林 167 森林的二叉樹(shù)存儲(chǔ) 將每棵樹(shù)Ti轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)Bi 將Bi作為Bi 1根結(jié)點(diǎn)的的右子樹(shù) 168 169 170 總結(jié) 本章是數(shù)據(jù)結(jié)構(gòu)的重點(diǎn)之一 也是本書(shū)許多后續(xù)章節(jié)的基礎(chǔ) 本章主要介紹了樹(shù)形結(jié)構(gòu)的基本概念 詳細(xì)討論了一種重要的數(shù)據(jù)結(jié)構(gòu) 二叉樹(shù)的設(shè)計(jì)和實(shí)現(xiàn) 在此基礎(chǔ)上介紹了二叉樹(shù)的兩種應(yīng)用 表達(dá)式樹(shù)和哈夫曼樹(shù) 最后 本章還介紹了如何處理普通的樹(shù)形結(jié)構(gòu)以及森林 普通的樹(shù)形結(jié)構(gòu)和森林的處理方法是將它們轉(zhuǎn)換成二叉樹(shù)來(lái)處理 171 作業(yè) 172 第6章優(yōu)先級(jí)隊(duì)列 基本的優(yōu)先級(jí)隊(duì)列二叉堆D堆歸并優(yōu)先級(jí)隊(duì)列STL中的優(yōu)先級(jí)隊(duì)列排隊(duì)系統(tǒng)的模擬 173 基本的優(yōu)先級(jí)隊(duì)列 結(jié)點(diǎn)之間的關(guān)系是由結(jié)點(diǎn)的優(yōu)先級(jí)決定的 而不是由入隊(duì)的先后次序決定 優(yōu)先級(jí)高的先出隊(duì) 優(yōu)先級(jí)低的后出隊(duì) 這樣的隊(duì)列稱(chēng)為優(yōu)先級(jí)隊(duì)列 優(yōu)先級(jí)隊(duì)列的操作與普通的隊(duì)列相同 174 優(yōu)先級(jí)隊(duì)列的簡(jiǎn)單實(shí)現(xiàn) 利用現(xiàn)有的隊(duì)列結(jié)構(gòu) 有兩種方法可以處理優(yōu)先級(jí)入隊(duì)時(shí) 按照優(yōu)先級(jí)在隊(duì)列中尋找合適的位置 將新入隊(duì)的元素插入在此位置 出隊(duì)操作的實(shí)現(xiàn)保持不變 入隊(duì)操作的實(shí)現(xiàn)保持不變 將新入隊(duì)的元素放在隊(duì)列尾 但出隊(duì)時(shí) 在整個(gè)隊(duì)列中查找優(yōu)先級(jí)最高的元素 讓它出隊(duì) 175 時(shí)間性能分析 第一種方案的入隊(duì)操作的時(shí)間復(fù)雜度是O N 出隊(duì)操作的時(shí)間復(fù)雜度是O 1 第二種方案的入隊(duì)操作的時(shí)間復(fù)雜度是O 1 出隊(duì)操作的時(shí)間復(fù)雜度是O N 176 第6章優(yōu)先級(jí)隊(duì)列 基本的優(yōu)先級(jí)隊(duì)列二叉堆D堆歸并優(yōu)先級(jí)隊(duì)列STL中的優(yōu)先級(jí)隊(duì)列排隊(duì)系統(tǒng)的模擬 177 二叉堆 堆是一棵完全二叉樹(shù) 且滿(mǎn)足下述關(guān)系之一ki k2i且ki k2i 1 i 1 2 n 2 或者 ki k2i且ki k2i 1 i 1 2 n 2 其中 下標(biāo)是樹(shù)按層次遍歷的次序滿(mǎn)足前一條件的稱(chēng)為最小化堆 例如 序列 2 3 4 5 7 10 23 29 60 是最小化堆滿(mǎn)足后一條件的稱(chēng)為最大化堆 例如 序列 12 7 8 4 6 5 3 1 是最大化堆 178 最大化堆 最小化堆 179 二叉堆的特性 結(jié)構(gòu)性 符合完全二叉樹(shù)的結(jié)構(gòu)有序性 滿(mǎn)足父節(jié)點(diǎn)小于子節(jié)點(diǎn) 最小化堆 或父節(jié)點(diǎn)大于子節(jié)點(diǎn) 最大化堆 以下的討論都以最小化堆為例 180 二叉堆的存儲(chǔ) 可以采用順序存儲(chǔ)二叉堆的有序性可以很容易地通過(guò)下標(biāo)來(lái)反映 181 基于二叉堆的優(yōu)先級(jí)隊(duì)列 如果數(shù)值越小 優(yōu)先級(jí)越高 則可以用一個(gè)最小化堆存儲(chǔ)優(yōu)先級(jí)隊(duì)列在最小化堆中 最小元素是根元素 而根結(jié)點(diǎn)永遠(yuǎn)存放在數(shù)組的下標(biāo)為1的元素中 獲取隊(duì)頭元素的操作就是返回下標(biāo)為1的數(shù)組元素值出隊(duì)操作就是刪除下標(biāo)為1的數(shù)組元素中的值入隊(duì)操作就是在數(shù)組的末尾添加一個(gè)元素 但添加后要調(diào)整元素的位置 以保持堆的有序性 182 優(yōu)先級(jí)隊(duì)列類(lèi) 數(shù)據(jù)成員 用一個(gè)動(dòng)態(tài)數(shù)組成員函數(shù) 實(shí)現(xiàn)隊(duì)列類(lèi)的所有操作 183 優(yōu)先級(jí)隊(duì)列類(lèi)的定義 templateclasspriorityQueue private intcurrentSize Type array intmaxSize voiddoubleSpace voidbuildHeap voidpercolateDown inthole 184 public priorityQueue intcapacity 100 array newType capacity maxSize capacity currentSize 0 priorityQueue constTypedata intsize priorityQueue delete array boolisEmpty const returncurrentSize 0 voidenQueue constType 185 enQueue x enQueue操作是在堆中插入一個(gè)新元素堆的插入是在具有最大序號(hào)的元素之后插入新的元素或結(jié)點(diǎn) 否則將違反堆的結(jié)構(gòu)性 如果新元素放入后 沒(méi)有違反堆的有序性 那么操作結(jié)束 否則 讓該節(jié)點(diǎn)向父節(jié)點(diǎn)移動(dòng) 直到滿(mǎn)足有序性或到達(dá)根節(jié)點(diǎn) 新節(jié)點(diǎn)的向上移動(dòng)稱(chēng)為向上過(guò)濾 percolateup 186 在如下的堆中插入元素1的過(guò)程 187 188 enQueue過(guò)程 templatevoidpriorityQueue enQueue constType 189 enQueue的時(shí)間效率 最壞情況是對(duì)數(shù)的平均情況 過(guò)濾會(huì)提前結(jié)束 有資料表明 平均是2 6次比較 因此元素平均上移1 6層 190 DeQueue操作 當(dāng)最小元素被刪除時(shí) 在根上出現(xiàn)了一個(gè)空結(jié)點(diǎn) 堆的大小比以前小1 堆的結(jié)構(gòu)性告訴我們 最后一個(gè)結(jié)點(diǎn)應(yīng)該刪掉 如果最后一項(xiàng)可以放在此空結(jié)點(diǎn)中 就把它放進(jìn)去 然而 這通常是不可能的 我們必須玩與插入操作相同的游戲 把某些項(xiàng)放入空結(jié)點(diǎn) 然后移動(dòng)空結(jié)點(diǎn) 僅有的區(qū)別在于 對(duì)DeQueue操作 空結(jié)點(diǎn)是往下移動(dòng) 191 向下過(guò)濾過(guò)程 找到空結(jié)點(diǎn)的一個(gè)較小的子結(jié)點(diǎn) 如果該兒子的值小于我們要放入的項(xiàng) 則把該兒子放入空結(jié)點(diǎn) 把空結(jié)點(diǎn)往下推一層 重復(fù)這個(gè)動(dòng)作 直到該項(xiàng)能被放入正確的位置 192 193 deQueue templateTypepriorityQueue deQueue TypeminItem minItem array 1 array 1 array currentSize percolateDown 1 returnminItem 194 向下過(guò)濾 templatevoidpriorityQueue percolateDown inthole intchild Typetmp array hole