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

1 第二部分樹 樹形結(jié)構(gòu)式處理具有層次關(guān)系的數(shù)據(jù)元素這部分將介紹樹二叉樹堆 2 第五章樹 樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林 3 樹的概念 樹的定義樹的術(shù)語樹的運(yùn)算 4 樹的定義 樹是n n 1 個(gè)結(jié)點(diǎn)的有限集合T 并且滿足 1 有一個(gè)被稱之為根 root 的結(jié)點(diǎn) 2 其余的結(jié)點(diǎn)可分為m m 0 個(gè)互不相交的集合Tl T2 Tm 這些集合本身也是一棵樹 并稱它們?yōu)楦Y(jié)點(diǎn)的子樹 Subree 每棵子樹同樣有自己的根結(jié)點(diǎn) 5 樹的概念 樹的定義樹的術(shù)語樹的運(yùn)算 6 根結(jié)點(diǎn) 葉結(jié)點(diǎn) 內(nèi)部節(jié)點(diǎn)結(jié)點(diǎn)的度和樹的度兒子結(jié)點(diǎn)父親結(jié)點(diǎn)兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)子孫結(jié)點(diǎn)結(jié)點(diǎn)所處層次樹的高度 有序樹無序樹森林 樹的術(shù)語 7 樹的概念 樹的定義樹的術(shù)語樹的運(yùn)算 8 樹的常用操作 建樹create 創(chuàng)建一棵空樹 清空clear 刪除樹中的所有結(jié)點(diǎn) 判空IsEmpty 判別是否為空樹 找根結(jié)點(diǎn)root 找出樹的根結(jié)點(diǎn) 如果樹是空樹 則返回一個(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棵子樹 構(gòu)建一棵樹MakeTree x T1 T2 Tn 構(gòu)建一棵以x為根結(jié)點(diǎn) 以T1 T2 Tn為第i棵子樹的樹 遍歷traverse 訪問樹上的每一個(gè)結(jié)點(diǎn) 9 第五章樹 樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林 10 二叉樹 二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn) 11 二叉樹的定義 二叉樹 BinaryTree 是結(jié)點(diǎn)的有限集合 它或者為空 或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左 右子樹構(gòu)成 而其左 右子樹又都是二叉樹 注意 二叉樹必須嚴(yán)格區(qū)分左右子樹 即使只有一棵子樹 也要說明它是左子樹還是右子樹 交換一棵二叉樹的左右子樹后得到的是另一棵二叉樹 12 二叉樹的基本形態(tài) a 空二叉樹 b 根和空的左右子樹 c 根和左右子樹 d 根和左子樹 e 根和右子樹 13 結(jié)點(diǎn)總數(shù)為3的所有二叉樹的不同形狀 14 一棵高度為k并具有2k 1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹 一棵二叉樹中任意一層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到了最大值 滿二叉樹 15 滿二叉樹實(shí)例 不是滿二叉樹 16 完全二叉樹 在滿二叉樹的最底層自右至左依次 注意 不能跳過任何一個(gè)結(jié)點(diǎn) 去掉若干個(gè)結(jié)點(diǎn)得到的二叉樹也被稱之為完全二叉樹 滿二叉樹一定是完全二叉樹 但完全二叉樹不一定是滿二叉樹 完全二叉樹的特點(diǎn)是 1 所有的葉結(jié)點(diǎn)都出現(xiàn)在最低的兩層上 2 對任一結(jié)點(diǎn) 如果其右子樹的高度為k 則其左子樹的高度為k或k 1 17 完全二叉樹 非完全二叉樹 18 二叉樹 二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn) 19 二叉樹的性質(zhì)1 一棵非空二叉樹的第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 命題成立 假定對于所有的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 二叉樹的性質(zhì)2 一棵高度為k的二叉樹 最多具有2k 1個(gè)結(jié)點(diǎn) 證明 這棵二叉樹中的每一層的結(jié)點(diǎn)個(gè)數(shù)必須最多 根據(jù)性質(zhì)1 第i層的結(jié)點(diǎn)數(shù)最多為等于2i 1 因此結(jié)點(diǎn)個(gè)數(shù)N最多為 22 對于一棵非空二叉樹 如果葉子結(jié)點(diǎn)數(shù)為n0 度數(shù)為2的結(jié)點(diǎn)數(shù)為n2 則有 n0 n2 1成立 二叉樹的性質(zhì)3 23 證明 設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù) n1為二叉樹中度數(shù)為1的結(jié)點(diǎn)數(shù) 二叉樹中所有結(jié)點(diǎn)均小于或等于2 所以有 n n0 n1 n2再看二叉樹中的樹枝 父結(jié)點(diǎn)和兒子結(jié)點(diǎn)之間的線段 總數(shù) 在二叉樹中 除根結(jié)點(diǎn)外 其余結(jié)點(diǎn)都有唯一的一個(gè)樹枝進(jìn)入本結(jié)點(diǎn) 性質(zhì)3證明 24 設(shè)B為二叉樹中的樹枝數(shù) 那么有下式成立 B n 1這些樹枝都是由度為1和度為2的結(jié)點(diǎn)發(fā)出的 一個(gè)度為1的結(jié)點(diǎn)發(fā)出一個(gè)樹枝 一個(gè)度為2的結(jié)點(diǎn)發(fā)出兩個(gè)樹枝 所以有 B n1 2n2因此 n0 n2 1 25 二叉樹的性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度k log2n 1 證明根據(jù)完全二叉樹的定義和性質(zhì)2可知 高度為k的完全二叉樹的第一層到第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對不等式取對數(shù) 有k 1 log2n k由于k是整數(shù) 所以有 k log2n 1 26 二叉樹的性質(zhì)5 如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)按層自上而下 從第1層到第 log2n 1層 每一層按自左至右依次編號 若設(shè)根結(jié)點(diǎn)的編號為1 則對任一編號為i的結(jié)點(diǎn) 1 i n 有 1 如果i 1 則該結(jié)點(diǎn)是二叉樹的根結(jié)點(diǎn) 如果i 1 則其父親結(jié)點(diǎn)的編號為 i 2 2 如果2i n 則編號為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn) 沒有兒子 否則 其左兒子的編號為2i 3 如果2i 1 n 則編號為i的結(jié)點(diǎn)無右兒子 否則 其右兒子的編號為2i 1 27 28 二叉樹 二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn) 29 二叉樹常用操作 建樹create 創(chuàng)建一棵空的二叉樹 清空clear 刪除二叉樹中的所有結(jié)點(diǎn) 判空IsEmpty 判別二叉樹是否為空樹 找根結(jié)點(diǎn)root 找出二叉樹的根結(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) 刪除左子樹delLeft x 刪除結(jié)點(diǎn)x的左子樹 刪除右子樹delRight x 刪除結(jié)點(diǎn)x的右子樹 構(gòu)建一棵樹MakeTree x TL TR 構(gòu)建一棵以x為根結(jié)點(diǎn) 以TL TR為左右子樹的二叉樹 遍歷traverse 訪問二叉樹上的每一個(gè)結(jié)點(diǎn) 30 二叉樹 二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn) 31 二叉樹的遍歷 二叉樹的遍歷討論的是如何訪問到樹上的每一個(gè)結(jié)點(diǎn)在線性表中 我們可以沿著后繼鏈訪問到所有結(jié)點(diǎn) 而二叉樹是有分叉的 因此在分叉處必須確定下一個(gè)要訪問的節(jié)點(diǎn) 是根結(jié)點(diǎn) 左結(jié)點(diǎn)還是右結(jié)點(diǎn)根據(jù)不同的選擇 有三種遍歷的方法 前序 中序和后序 32 前序遍歷 如果二叉樹為空 則操作為空否則訪問根結(jié)點(diǎn)前序遍歷左子樹前序遍歷右子樹 33 中序遍歷 如果二叉樹為空 則操作為空否則中序遍歷左子樹訪問根結(jié)點(diǎn)中序遍歷右子樹 34 后序遍歷 如果二叉樹為空 則操作為空否則后序遍歷左子樹后序遍歷右子樹訪問根結(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 前序 中序唯一確定一棵二叉樹 前序 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 同理 由二叉樹的后序序列和中序序列同樣可以唯一地確定一棵二叉樹但是 已知二叉樹的前序遍歷序列和后序遍歷序列卻無法確定一棵二叉樹 比如 已知一棵二叉樹的前序遍歷序列為A B 后序遍歷序列為B A 我們雖然可以很容易地得知結(jié)點(diǎn)A為根結(jié)點(diǎn) 但是無法確定結(jié)點(diǎn)B是結(jié)點(diǎn)A的左兒子還是右兒子 因?yàn)锽無論是結(jié)點(diǎn)A的右兒子還是左兒子都是符合已知條件的 38 二叉樹 二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn) 39 二叉樹的實(shí)現(xiàn) 順序?qū)崿F(xiàn)鏈接實(shí)現(xiàn) 40 完全二叉樹的順序存儲 根據(jù)編號性質(zhì) 可以省略左右孩子字段 41 普通二叉樹的順序存儲 D B A H I 將普通的樹修補(bǔ)成完全二叉樹 42 右單支樹的實(shí)例 43 順序?qū)崿F(xiàn)的特點(diǎn) 存儲空間的浪費(fèi) 一般只用于一些特殊的場合 如靜態(tài)的并且結(jié)點(diǎn)個(gè)數(shù)已知的完全二叉樹或接近完全二叉樹的二叉樹 44 二叉樹的實(shí)現(xiàn) 順序?qū)崿F(xiàn)鏈接實(shí)現(xiàn) 45 鏈接存儲結(jié)構(gòu) 標(biāo)準(zhǔn)形式 二叉鏈表 廣義標(biāo)準(zhǔn)形式 三叉鏈表 46 標(biāo)準(zhǔn)形式的實(shí)例 47 廣義標(biāo)準(zhǔn)形式的實(shí)例 48 二叉樹基本運(yùn)算的實(shí)現(xiàn) 由于二叉樹是一個(gè)遞歸的結(jié)構(gòu) 因此二叉樹中的許多運(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ù)部分 如果二叉樹是空樹 則返回一個(gè)特殊的標(biāo)記 49 clear 從遞歸的觀點(diǎn)看 一棵二叉樹由三部分組成 根結(jié)點(diǎn) 左子樹 右子樹 刪除一棵二叉樹就是刪除這三個(gè)部分 根結(jié)點(diǎn)的刪除很簡單 只要回收根結(jié)點(diǎn)的空間 把指向根結(jié)點(diǎn)的指針設(shè)為空指針 如何刪除左子樹和右子樹呢 記住左子樹也是一棵二叉樹 右子樹也是一棵二叉樹 左右子樹的刪除和整棵樹的刪除過程是一樣的 50 If 左子樹非空 遞歸刪除左子樹 If 右子樹非空 遞歸刪除右子樹 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 對左子樹調(diào)用clear函數(shù)刪除左子樹 然后將結(jié)點(diǎn)x的left置為NULL delRight x 對右子樹調(diào)用clear函數(shù)刪除右子樹 然后將結(jié)點(diǎn)x的right置為NULL makeTree x TL TR 為x申請一個(gè)結(jié)點(diǎn) 讓它的left指向TL的根結(jié)點(diǎn) right指向TR的根結(jié)點(diǎn) 52 二叉樹的遍歷 前序 訪問根結(jié)點(diǎn) If 左子樹非空 前序遍歷左子樹 If 右子樹非空 前序遍歷右子樹 其他兩種遍歷只要調(diào)整一下次序即可 53 二叉樹 二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn) 54 二叉樹類 由于二叉樹的順序?qū)崿F(xiàn)僅用于一些特殊的場合 大多數(shù)情況下 二叉樹都是用二叉鏈表實(shí)現(xiàn) 所以僅介紹用二叉鏈表實(shí)現(xiàn)的二叉樹類 55 二叉樹類的設(shè)計(jì) 標(biāo)準(zhǔn)的鏈接存儲由兩個(gè)類組成 結(jié)點(diǎn)類和樹類 和線性表的實(shí)現(xiàn)類似 這個(gè)結(jié)點(diǎn)類是樹類專用的 因此可作為樹類的私有內(nèi)嵌類 56 結(jié)點(diǎn)類Node的設(shè)計(jì) 存儲和處理樹上每一個(gè)結(jié)點(diǎn)的類 數(shù)據(jù)成員包括 結(jié)點(diǎn)的數(shù)據(jù)及左右孩子的指針 結(jié)點(diǎn)的操作包括 構(gòu)造和析構(gòu) 57 二叉樹類的設(shè)計(jì) 樹的存儲 存儲指向根結(jié)點(diǎn)的指針樹的操作 樹的標(biāo)準(zhǔn)操作增加了一個(gè)建樹的函數(shù) 58 遞歸函數(shù)的設(shè)計(jì) 對于二叉樹類的用戶來說 他并不需要知道這些操作時(shí)用遞歸函數(shù)實(shí)現(xiàn)的 對用戶來說 調(diào)用這些函數(shù)并不需要參數(shù)但遞歸函數(shù)必須有一個(gè)控制遞歸終止的參數(shù)設(shè)計(jì)時(shí) 我們將用戶需要的函數(shù)原型作為公有的成員函數(shù) 每個(gè)公有成員函數(shù)對應(yīng)一個(gè)私有的 帶遞歸參數(shù)的成員函數(shù) 公有函數(shù)調(diào)用私有函數(shù)完成相應(yīng)的功能 59 二叉樹類的定義 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 二叉樹的根結(jié)點(diǎn) 60 public BinaryTree root NULL 構(gòu)造空二叉樹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) 用遞歸的觀點(diǎn)來看 二叉樹是由根結(jié)點(diǎn)和左右子樹構(gòu)成 因此 樹的規(guī)模應(yīng)該為 左子樹的規(guī)模 右子樹的規(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) 用遞歸的觀點(diǎn)來看 二叉樹是由根結(jié)點(diǎn)和左右子樹構(gòu)成 因此 樹的高度應(yīng)該為 1 max 左子樹高度 右子樹高度 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í)現(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í)現(xiàn) 樹的刪除可以用遞歸的方法來實(shí)現(xiàn) 先遞歸刪除左右子樹 再刪除根結(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)建一棵樹 創(chuàng)建過程 先輸入根結(jié)點(diǎn)的值 創(chuàng)建根節(jié)點(diǎn)對已添加到樹上的每個(gè)結(jié)點(diǎn) 依次輸入它的兩個(gè)兒子的值 如果沒有兒子 則輸入一個(gè)特定值實(shí)現(xiàn)工具 使用一個(gè)隊(duì)列 將新加入到樹中的結(jié)點(diǎn)放入隊(duì)列依次出隊(duì) 對每個(gè)出隊(duì)的元素輸入它的兒子 75 隊(duì)列的變化 76 createTree templatevoidBinaryTree createTree Typeflag linkQueueque Node tmp Typex ldata rdata 創(chuàng)建樹 輸入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 二叉樹類的應(yīng)用 創(chuàng)建一棵由整型值組成的二叉樹求高度求規(guī)模按前序 中序和后序遍歷歸并兩棵樹 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 二叉樹 二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn) 84 二叉樹遍歷的非遞歸實(shí)現(xiàn) 遞歸是程序設(shè)計(jì)中強(qiáng)有力的工具 遞歸程序結(jié)構(gòu)清晰 明了 美觀 遞歸程序的弱點(diǎn) 它的時(shí)間 空間的效率比較低 所以在實(shí)際使用中 我們常常希望使用它的非遞歸版本二叉樹的遍歷也是如此 盡管二叉樹遍歷的遞歸函數(shù)非常簡潔 但有時(shí)我們還是希望使用速度更快的非遞歸函數(shù) 85 二叉樹遍歷的非遞歸實(shí)現(xiàn) 前序遍歷中序遍歷后序遍歷 86 前序遍歷的非遞歸實(shí)現(xiàn) 前序遍歷第一個(gè)被訪問的結(jié)點(diǎn)是根結(jié)點(diǎn) 然后訪問左子樹 最后訪問右子樹 可以設(shè)置一個(gè)棧 保存將要訪問的樹的樹根 開始時(shí) 把二叉樹的根結(jié)點(diǎn)存入棧中 然后重復(fù)以下過程 直到棧為空 從棧中取出一個(gè)結(jié)點(diǎn) 輸出根結(jié)點(diǎn)的值 然后把右子樹 左子樹放入棧中 87 前序遍歷的過程 輸出 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í)現(xiàn) 前序遍歷中序遍歷后序遍歷 90 中序遍歷的非遞歸實(shí)現(xiàn) 采用一個(gè)棧存放要遍歷的樹的樹根中序遍歷中 先要遍歷左子樹 接下去才能訪問根結(jié)點(diǎn) 因此 當(dāng)根結(jié)點(diǎn)出棧時(shí) 我們不能訪問它 而要訪問它的左子樹 此時(shí)要把樹根結(jié)點(diǎn)暫存一下 存哪里 由于左子樹訪問完后還要訪問根結(jié)點(diǎn) 因此仍可以把它存在棧中 接著左子樹也進(jìn)棧 此時(shí)執(zhí)行出棧操作 出棧的是左子樹 左子樹問結(jié)束后 再次出棧的是根結(jié)點(diǎn) 此時(shí)根結(jié)點(diǎn)可被訪問 根結(jié)點(diǎn)訪問后 訪問右子樹 則將右子樹進(jìn)棧 91 棧元素的設(shè)計(jì) 在中序遍歷中根結(jié)點(diǎn)要進(jìn)棧兩次 當(dāng)要遍歷一棵樹時(shí) 將根結(jié)點(diǎn)進(jìn)棧 根結(jié)點(diǎn)第一次出棧時(shí) 它不能被訪問 必須重新進(jìn)棧 并將左子樹也進(jìn)棧 表示接下去要訪問的是左子樹 根結(jié)點(diǎn)第二次出棧時(shí) 才能被訪問 并將右子樹進(jìn)棧 表示右子樹可以訪問了 在中序遍歷時(shí)不僅要記住需要訪問哪一棵樹 而且還必須記住根結(jié)點(diǎn)是在第幾次進(jìn)棧 92 中序遍歷的過程 輸出 B L E A C W X D 93 StNode類的定義 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í)現(xiàn) 前序遍歷中序遍歷后序遍歷 97 后序遍歷的非遞歸實(shí)現(xiàn) 將中序遍歷的非遞歸實(shí)現(xiàn)的思想進(jìn)一步延伸 可以得到后序遍歷的非遞歸實(shí)現(xiàn) 當(dāng)以后序遍歷一棵二叉樹時(shí) 先將樹根進(jìn)棧 表示要遍歷這棵樹 根結(jié)點(diǎn)第一次出棧時(shí) 根結(jié)點(diǎn)不能訪問 應(yīng)該訪問左子樹 于是 根結(jié)點(diǎn)重新入棧 并將左子樹也入棧 根結(jié)點(diǎn)第二次出棧時(shí) 根結(jié)點(diǎn)還是不能訪問 要先訪問右子樹 于是 根結(jié)點(diǎn)再次入棧 右子樹也入棧 當(dāng)根結(jié)點(diǎn)第三次出棧時(shí) 表示右子樹遍歷結(jié)束 此時(shí) 根結(jié)點(diǎn)才能被訪問 98 后序遍歷的過程 輸出 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 第五章樹 樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林 103 表達(dá)式樹 算術(shù)表達(dá)式可以表示為一棵二叉樹 如 4 2 10 4 6 2 2對這棵樹后序遍歷可得到結(jié)果設(shè)計(jì)一個(gè)類 利用表達(dá)式樹計(jì)算由四則運(yùn)算組成的表達(dá)式 104 樹的構(gòu)建過程 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) 原樹作為左子樹 5 7 9 8構(gòu)建右節(jié)點(diǎn)5 105 7 9 8下移到右節(jié)點(diǎn) 構(gòu)建根節(jié)點(diǎn) 原來的右節(jié)點(diǎn)作為它的左節(jié)點(diǎn) 7 9 8構(gòu)建右節(jié)點(diǎn)7 9 8創(chuàng)建根 原樹作為左子樹 106 8上移到根 創(chuàng)建根 原樹作為左子樹 88作為左節(jié)點(diǎn) 9 89作為右子樹 107 構(gòu)建過程總結(jié) 順序掃描中綴表達(dá)式當(dāng)掃描到的是運(yùn)算數(shù) 先檢查當(dāng)前的表達(dá)式樹是否存在 如果不存在 則表示掃描到的是第一個(gè)運(yùn)算數(shù) 將它作為樹根 如果樹存在 則將此運(yùn)算數(shù)作為前一運(yùn)算符的右孩子 如果掃描到的是 或 將它作為根結(jié)點(diǎn) 原來的樹作為它的左子樹 108 構(gòu)建過程總結(jié)續(xù) 如果掃描到的是 或 則與根結(jié)點(diǎn)比較 如果根結(jié)點(diǎn)也是 或 則根結(jié)點(diǎn)應(yīng)該先執(zhí)行 于是將當(dāng)前運(yùn)算符作為根結(jié)點(diǎn) 原來的樹作為左子樹 如果根結(jié)點(diǎn)是 或 則當(dāng)前運(yùn)算符應(yīng)該先運(yùn)算 于是將它作為右子樹的根 原來的右子樹作為它的左子樹 在遇到運(yùn)算數(shù)時(shí) 如何知道它前面的運(yùn)算符是誰 這只需要判別根結(jié)點(diǎn)有沒有右孩子 如果沒有右孩子 則運(yùn)算數(shù)是根結(jié)點(diǎn)的右運(yùn)算數(shù) 否則就是根結(jié)點(diǎn)右孩子的右運(yùn)算數(shù) 109 構(gòu)建過程 括號的處理 4 5 8 9 10遇到括號 將括號內(nèi)的子表達(dá)式構(gòu)建一棵子樹作為整個(gè)表達(dá)式的一個(gè)運(yùn)算數(shù) 8 9 10 作為根節(jié)點(diǎn) 括號內(nèi)的子樹作為左子樹 8 9 10括號內(nèi)的子表達(dá)式構(gòu)建一棵子樹作為整棵樹的右子樹 10 作為根節(jié)點(diǎn) 原樹作為左子樹 10作為右子樹 110 表達(dá)式樹類的設(shè)計(jì) 數(shù)據(jù)成員 指向樹根節(jié)點(diǎn)的指針公有成員函數(shù) 構(gòu)造函數(shù) 調(diào)用create從表達(dá)式構(gòu)建一棵樹result 計(jì)算表達(dá)式的結(jié)果 用后序遍歷過程私有成員函數(shù) Create帶有遞歸參數(shù)的result函數(shù)getToken create函數(shù)所用的子函數(shù) 用于從表達(dá)式中獲取一個(gè)語法單位 111 結(jié)點(diǎn)的設(shè)計(jì) 在表達(dá)式樹中 每個(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)的類型和值 112 calc類的定義 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類的應(yīng)用 intmain calcexp 2 3 1 2 3 6 6 2 3 5 2 2 cout exp result endl return0 120 Calc類的特點(diǎn) 使用時(shí)和基于棧實(shí)現(xiàn)的calc類完全一樣缺點(diǎn)沒有考慮表達(dá)式不正確的情況沒有考慮乘方運(yùn)算 121 第五章樹 樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林 122 字符的機(jī)內(nèi)表示 在計(jì)算機(jī)中每個(gè)字符是用一個(gè)編碼表示大多數(shù)編碼系統(tǒng)都采用等長編碼 如ASCII編碼例如在某段文本中用到了下列字符 括號中是它們出現(xiàn)的頻率 a 10 e 15 i 12 s 3 t 4 空格 13 換行 1 如采用定長編碼 7個(gè)不同的字符至少要用3位編碼 123 總存儲量 3 10 15 12 3 4 13 1 3 58 174bit 124 這個(gè)編碼可以對應(yīng)成如下的完全二叉樹 左枝為0 右枝為1 125 很顯然 將換行上移一層可以減少存儲量 不等長編碼可以減少存儲量 126 前綴編碼 字符只放在葉結(jié)點(diǎn)中字符編碼可以有不同的長度由于字符只放在葉結(jié)點(diǎn)中 所以每個(gè)字符的編碼都不可能是其他字符編碼的前綴前綴編碼可被惟一解碼 127 哈夫曼樹 哈夫曼樹是一棵最小代價(jià)的二叉樹 在這棵樹上 所有的字符都包含在葉結(jié)點(diǎn)上 要使得整棵樹的代價(jià)最小 顯然權(quán)值大的葉子應(yīng)當(dāng)盡量靠近樹根 權(quán)值小的葉子可以適當(dāng)離樹根遠(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)過了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í)現(xiàn) 為了便于找出一組符號的哈夫曼編碼 我們可以定義一個(gè)哈夫曼樹類 哈夫曼樹類的對象可以接受一組符號以及對應(yīng)的權(quán)值 并告知每個(gè)符號對應(yīng)的哈夫曼編碼 因此 哈夫曼樹類應(yīng)該有兩個(gè)公有的成員函數(shù) 構(gòu)造函數(shù) 接受一組待編碼的符號以及它們的權(quán)值 構(gòu)造一棵哈夫曼樹 GetCode函數(shù)根據(jù)保存的哈夫曼樹為每個(gè)葉結(jié)點(diǎn)生成哈夫曼編碼 135 哈夫曼樹的存儲 在哈夫曼樹中 每個(gè)要編碼的元素是一個(gè)葉結(jié)點(diǎn) 其它結(jié)點(diǎn)都是度數(shù)為2的節(jié)點(diǎn)一旦給定了要編碼的元素個(gè)數(shù) 由n0 n2 1可知哈夫曼樹的大小為2n 1哈夫曼樹可以用一個(gè)大小為2n的數(shù)組來存儲 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 值 生成過程 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 對每個(gè)結(jié)點(diǎn) 從葉子往根推進(jìn) 是左枝加0 是右枝加1 139 哈夫曼樹類 存儲設(shè)計(jì)結(jié)點(diǎn)的表示 結(jié)點(diǎn)的數(shù)據(jù) 權(quán)值和父結(jié)點(diǎn)和左右孩子的位置哈夫曼樹的存儲 一個(gè)結(jié)點(diǎn)數(shù)組以及一個(gè)整型數(shù)據(jù)成員 保存數(shù)組的大小 操作構(gòu)建一棵哈夫曼樹 構(gòu)造函數(shù)實(shí)現(xiàn) 給出節(jié)點(diǎn)數(shù)據(jù)數(shù)組 權(quán)值數(shù)組和數(shù)據(jù)個(gè)數(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 最小樹 次最小樹的權(quán)值intx y 最小樹 次最小樹的下標(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)造新的二叉樹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是追溯過程中正在處理的結(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 哈夫曼類的使用 為下列符號集生成哈夫曼編碼 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 第五章樹 樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林 149 樹和森林 樹的存儲實(shí)現(xiàn)樹的遍歷樹 森林和二叉樹 150 樹的存儲結(jié)構(gòu) 標(biāo)準(zhǔn)形式 樹中的每個(gè)結(jié)點(diǎn)除有數(shù)據(jù)字段之外 還有K個(gè)指針字段 其中K為樹的度 data son1 廣義標(biāo)準(zhǔn)形式 在標(biāo)準(zhǔn)形式的基礎(chǔ)上 再增加指向父親結(jié)點(diǎn)的指針場 son2 sonk parent 151 E g 度數(shù)K 3的樹的廣義標(biāo)準(zhǔn)存儲 值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è)鏈表 樹的節(jié)點(diǎn)由兩部分組成 存儲數(shù)據(jù)元素值的數(shù)據(jù)部分指向孩子鏈的指針如果樹的所有結(jié)點(diǎn)存放在一個(gè)數(shù)組中 這個(gè)數(shù)組稱為表頭數(shù)組 這種存儲方式稱為靜態(tài)的孩子鏈表 將樹的所有結(jié)點(diǎn)組織成一個(gè)鏈表 稱為動(dòng)態(tài)的孩子鏈表 153 154 孩子兄弟鏈表示法 實(shí)質(zhì)上是用二叉樹表示一棵樹 樹中的每個(gè)結(jié)點(diǎn)有數(shù)據(jù)字段 指向它的第一棵子樹樹根的指針字段 指向它的兄弟結(jié)點(diǎn)的指針字段 155 156 雙親表示法 通過指向父結(jié)點(diǎn)的指針將樹中所有的結(jié)點(diǎn)組織在一起在雙親表示法中 每個(gè)結(jié)點(diǎn)由兩部分組成 存儲數(shù)據(jù)元素的數(shù)據(jù)字段存儲父結(jié)點(diǎn)位置的父指針字段這種表示法對求指定結(jié)點(diǎn)的祖先的操作很方便 但對求指定結(jié)點(diǎn)的子孫則不方便 只適合某些應(yīng)用 如不相交集的存儲 157 158 樹和森林 樹的存儲實(shí)現(xiàn)樹的遍歷樹 森林和二叉樹 159 前序遍歷 訪問根結(jié)點(diǎn) 前序遍歷根結(jié)點(diǎn)的第一棵子樹 前序遍歷它的第二棵子樹 前序遍歷它的最后一棵子樹 160 后序遍歷 后序遍歷根結(jié)點(diǎn)的第一棵子樹 后序遍歷它的第二棵子樹 后序遍歷它的最后一棵子樹 訪問根結(jié)點(diǎn) 161 層次遍歷 訪問根結(jié)點(diǎn) 若第i層已被訪問 且第i 1層的結(jié)點(diǎ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í)現(xiàn)樹的遍歷樹 森林和二叉樹 164 樹 森林和二叉樹 二叉樹是一種結(jié)構(gòu)最簡單 運(yùn)算最簡便的樹形結(jié)構(gòu) 但對很多問題來講 其自然的描述形態(tài)是樹或森林 樹的孩子兄弟鏈表示法就是將一棵樹表示成二叉樹的形態(tài) 這樣就可以將二叉樹中的許多方法用在樹的處理中 165 A B C D F G E H I J 166 森林 森林通常定義為樹的集合或樹的序列 森林的存儲 存儲一個(gè)森林要包括兩方面的內(nèi)容存儲森林中的每一棵樹表示這些樹是屬于同一個(gè)森林 167 森林的二叉樹存儲 將每棵樹Ti轉(zhuǎn)換成對應(yīng)的二叉樹Bi 將Bi作為Bi 1根結(jié)點(diǎn)的的右子樹 168 169 170 總結(jié) 本章是數(shù)據(jù)結(jié)構(gòu)的重點(diǎn)之一 也是本書許多后續(xù)章節(jié)的基礎(chǔ) 本章主要介紹了樹形結(jié)構(gòu)的基本概念 詳細(xì)討論了一種重要的數(shù)據(jù)結(jié)構(gòu) 二叉樹的設(shè)計(jì)和實(shí)現(xiàn) 在此基礎(chǔ)上介紹了二叉樹的兩種應(yīng)用 表達(dá)式樹和哈夫曼樹 最后 本章還介紹了如何處理普通的樹形結(jié)構(gòu)以及森林 普通的樹形結(jié)構(gòu)和森林的處理方法是將它們轉(zhuǎn)換成二叉樹來處理 171 作業(yè) 172 第6章優(yōu)先級隊(duì)列 基本的優(yōu)先級隊(duì)列二叉堆D堆歸并優(yōu)先級隊(duì)列STL中的優(yōu)先級隊(duì)列排隊(duì)系統(tǒng)的模擬 173 基本的優(yōu)先級隊(duì)列 結(jié)點(diǎn)之間的關(guān)系是由結(jié)點(diǎn)的優(yōu)先級決定的 而不是由入隊(duì)的先后次序決定 優(yōu)先級高的先出隊(duì) 優(yōu)先級低的后出隊(duì) 這樣的隊(duì)列稱為優(yōu)先級隊(duì)列 優(yōu)先級隊(duì)列的操作與普通的隊(duì)列相同 174 優(yōu)先級隊(duì)列的簡單實(shí)現(xiàn) 利用現(xiàn)有的隊(duì)列結(jié)構(gòu) 有兩種方法可以處理優(yōu)先級入隊(duì)時(shí) 按照優(yōu)先級在隊(duì)列中尋找合適的位置 將新入隊(duì)的元素插入在此位置 出隊(duì)操作的實(shí)現(xiàn)保持不變 入隊(duì)操作的實(shí)現(xiàn)保持不變 將新入隊(duì)的元素放在隊(duì)列尾 但出隊(duì)時(shí) 在整個(gè)隊(duì)列中查找優(yōu)先級最高的元素 讓它出隊(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)先級隊(duì)列 基本的優(yōu)先級隊(duì)列二叉堆D堆歸并優(yōu)先級隊(duì)列STL中的優(yōu)先級隊(duì)列排隊(duì)系統(tǒng)的模擬 177 二叉堆 堆是一棵完全二叉樹 且滿足下述關(guān)系之一ki k2i且ki k2i 1 i 1 2 n 2 或者 ki k2i且ki k2i 1 i 1 2 n 2 其中 下標(biāo)是樹按層次遍歷的次序滿足前一條件的稱為最小化堆 例如 序列 2 3 4 5 7 10 23 29 60 是最小化堆滿足后一條件的稱為最大化堆 例如 序列 12 7 8 4 6 5 3 1 是最大化堆 178 最大化堆 最小化堆 179 二叉堆的特性 結(jié)構(gòu)性 符合完全二叉樹的結(jié)構(gòu)有序性 滿足父節(jié)點(diǎn)小于子節(jié)點(diǎn) 最小化堆 或父節(jié)點(diǎn)大于子節(jié)點(diǎn) 最大化堆 以下的討論都以最小化堆為例 180 二叉堆的存儲 可以采用順序存儲二叉堆的有序性可以很容易地通過下標(biāo)來反映 181 基于二叉堆的優(yōu)先級隊(duì)列 如果數(shù)值越小 優(yōu)先級越高 則可以用一個(gè)最小化堆存儲優(yōu)先級隊(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)先級隊(duì)列類 數(shù)據(jù)成員 用一個(gè)動(dòng)態(tài)數(shù)組成員函數(shù) 實(shí)現(xiàn)隊(duì)列類的所有操作 183 優(yōu)先級隊(duì)列類的定義 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è)新元素堆的插入是在具有最大序號的元素之后插入新的元素或結(jié)點(diǎn) 否則將違反堆的結(jié)構(gòu)性 如果新元素放入后 沒有違反堆的有序性 那么操作結(jié)束 否則 讓該節(jié)點(diǎn)向父節(jié)點(diǎn)移動(dòng) 直到滿足有序性或到達(dá)根節(jié)點(diǎn) 新節(jié)點(diǎn)的向上移動(dòng)稱為向上過濾 percolateup 186 在如下的堆中插入元素1的過程 187 188 enQueue過程 templatevoidpriorityQueue enQueue constType 189 enQueue的時(shí)間效率 最壞情況是對數(shù)的平均情況 過濾會提前結(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ū)別在于 對DeQueue操作 空結(jié)點(diǎn)是往下移動(dòng) 191 向下過濾過程 找到空結(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 向下過濾 templatevoidpriorityQueue percolateDown inthole intchild Typetmp array hole