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

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