【文章內(nèi)容簡介】 樹是 n個結(jié)點(diǎn)的有限集合 T，當(dāng) n=0時，稱為空樹；當(dāng) n0時， T滿足如下條件：在任一棵非空樹中： （ 1）有且僅有一個稱為根的結(jié)點(diǎn)。 （ 2）其余結(jié)點(diǎn)可分為 M個互不相交的子集合，而且這些子集中的每一個本身又是一棵樹，也稱為根的子樹。 J I A C B D H G F E K L M 2．樹的實例 樹可表示具有分枝結(jié)構(gòu)關(guān)系的對象 例 1．家族族譜 設(shè)某家庭有 13個成員 A、 B、 C、 D、 E、 F、 G、 H、I、 J、 K、 L、 M，他們之間的關(guān)系可用樹表示： J I A C B D H G F E K L M 計算機(jī)中樹是常用的數(shù)據(jù)組織形式 盡管有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。 例 2 計算機(jī)的文件系統(tǒng) 不論是 DOS文件系統(tǒng)還是 window文件系統(tǒng)，所有的文件都是用樹的形式來組織的。 文件夾 1 文件夾 n 文件 1 文件 2 文件夾 11 文件夾 12 文件 11 文件 12 C盤 樹的 基本術(shù)語 樹的結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指 向子樹的分支； 孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn) 的孩子， B、 C是 A的孩子； 雙親結(jié)點(diǎn)： B 結(jié)點(diǎn)是 A 結(jié)點(diǎn)的孩子，則 A 結(jié)點(diǎn)是 B 結(jié)點(diǎn)的雙親； 兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)， H、 I、 J互為兄弟； 堂兄結(jié)點(diǎn) ： 同一層上結(jié)點(diǎn)， E、 F、 G、 H、 I、 J、 互為堂兄弟； J I A C B D H G F E K L M 樹的 基本術(shù)語 結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次定義為 1；根的孩子為第二層，依此類推； 樹的深度： 樹中所有結(jié)點(diǎn)的層次的最大值 結(jié)點(diǎn)的度： 結(jié)點(diǎn)子樹的個數(shù) 樹的度： 樹中結(jié)點(diǎn)度的最大值。 葉子結(jié)點(diǎn) ：度為 0 的結(jié)點(diǎn)； 分枝結(jié)點(diǎn)： 度不為 0的結(jié)點(diǎn)； J I A C B D H G F E K L M 一 二叉樹的概念 1 二叉樹的定義 二叉樹： 或為空樹，或由根及兩顆互不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。 A F G E D C B 一 二叉樹的概念 二叉樹 說明 1）二叉樹中每個結(jié)點(diǎn)最多有兩個子樹； 既：二叉樹每個結(jié)點(diǎn)度小于等于 2。 2）左、右子樹不能顛倒 ——有序樹 。 3）二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念 。 (a)、 (b)是不同的二叉樹， (a)的左子樹有四個結(jié)點(diǎn) ， (b)的左子樹有兩個結(jié)點(diǎn) (a) (b) G E D C B A F G E D C B F A 2． 二叉樹的基本形態(tài) φ (a)空樹 (b)只有根 (c) 右子樹空 (e) 左子樹空 (d) 左、右子樹非空 二、 二叉樹的性質(zhì) 性質(zhì) 1: 在二叉樹的第 i層上至多有 2i1個結(jié)點(diǎn) (i≥1)。 性質(zhì) 2: 深度為 k的二叉樹至多有 2k1個結(jié)點(diǎn) （ k≥1） 。 性質(zhì) 3: 對任意一棵二叉樹 T， 若葉結(jié)點(diǎn)數(shù)為 n0， 而其度為 2的結(jié)點(diǎn)數(shù)為 n2， 則 n0=n2+1 。 兩種特殊的二叉樹 滿二叉樹：深度為 k的二叉樹，如有 2k1個結(jié)點(diǎn)則稱為滿二叉樹； A G F E D C B A C B K=3的滿二叉樹 K=2的滿二叉樹 滿二叉樹的順序表示： 從二叉樹的根開始 ， 從上到下 ， 從左到右 ， 逐層進(jìn)行編號 （ 1， 2， …， n） 。 例如圖 （ a） 所示的滿二叉樹的順序表示為 : (1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11， 12， 13， 14， 15)。 8 9 10 11 12 134 52136 714 15 8 9 10 11 12 134 52136 714( a ) 滿二叉樹 ( b ) 完全二叉樹 完全二叉樹： 深度為 k， 結(jié)點(diǎn)數(shù)為 n的二叉樹 ， 如果其結(jié)點(diǎn) 1~n的位置序號分別與滿二叉樹的結(jié)點(diǎn) 1~n的位置序號一一對應(yīng) ， 則為完全二叉樹 ， 如上圖 (b)所示 。 滿二叉樹必為完全二叉樹， 而完全二叉樹不一定是滿二叉樹。 性質(zhì) 4：具有 n個結(jié)點(diǎn)的完全二叉樹的深度為 ［ log2n］ +1。 性質(zhì) 5: 對于有 n個結(jié)點(diǎn)的完全二叉樹 ， 按照從上到下 、 從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從 1開始順序編號 ， 則對于任意的序號為 i的結(jié)點(diǎn)有： （ 1） 如 i=1， 則序號為 i的結(jié)點(diǎn)是根結(jié)點(diǎn) ， 無雙親結(jié)點(diǎn)； 如i1， 則序號為 i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號為 ［ i/2］ （ 下取整 ） （ 2） 如 2in， 則序號為 i的結(jié)點(diǎn)無左孩子；如 2i≤n， 則序號為 i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號為 2i。 （ 3） 如 2i＋ 1n， 則序號為 i的結(jié)點(diǎn)無右孩子；如 2i＋ 1≤n， 則序號為 i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號為 2i＋ 1。 二叉樹 存儲結(jié)構(gòu) 二叉鏈表 二叉鏈表中每個結(jié)點(diǎn)包含三個域：數(shù)據(jù)域、左指針域、右指針域 A F E D C B 二叉鏈表圖示 ∧ D A B ∧ C ∧ ∧ E ∧ ∧ F ∧ 若一個二叉樹含有 n個結(jié)點(diǎn) ， 則它的二叉鏈表中必含有2n個指針域 ， 其中必有 n+1個空的指針域 。 二、二叉樹的遍歷（必考） 遍歷 ： 按某種順序訪問二叉樹的每個結(jié)點(diǎn)，而且每個結(jié)點(diǎn)僅被訪問一次。 訪問： 含義很廣，可以是對結(jié)點(diǎn)的各種處理 ，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。 如何訪問二叉樹的每個結(jié)點(diǎn)， 而且每個結(jié)點(diǎn)僅被訪問一次？ 二叉樹的遍歷方法（必考） 二叉樹由根、左子樹、右子樹三部分組成 二叉樹的遍歷 可以分解為：訪問根，遍歷 左子樹 和 遍歷 右子樹 令 ： L： 遍歷左子樹 T： 訪問根結(jié)點(diǎn) R： 遍歷右子樹 約定先左后右 , 有三種遍歷方法： T L R前序遍歷、 L T R中序遍歷 、 L R T后序遍歷。 A F G E D C B 先序遍歷 （ T L R） 若二叉樹非空 （ 1）訪問根結(jié)點(diǎn)； （ 2）先序遍歷左子樹； （ 3）先序遍歷右子樹 ； 先序遍歷序列 ： A,B,D,E,G,C,F 例：先 序遍歷右圖所示的二叉樹 （ 1）訪問根結(jié)點(diǎn) A （ 2）先序遍歷左子樹：即按 T L R 的順序遍歷 左子樹 （ 3）先序遍歷右子樹：即按 T L R 的順序遍歷 右子樹 A F G E D C B 中序遍歷（ L T R） 若二叉樹非空 （ 1）中序遍歷左子樹 （ 2）訪問根結(jié)點(diǎn) （ 3）中序遍歷右子樹 中序遍歷序列 ： D,B,G,E,A,C,F 例： 中序遍歷右圖所示的二叉樹 （ 1）中序遍歷左子樹：即按 L T R 的順序遍歷 左子樹 （ 2）訪問根結(jié)點(diǎn) A （ 3）中序遍歷右子樹：即按 L T R 的順序遍歷 右子樹 A F G E D C B 后序遍歷（ L R T） 若二叉樹非空 （ 1）后序遍歷左子樹 （ 2）后序遍歷右子樹 （ 3）訪問根結(jié)點(diǎn) 后序遍歷序列： D,G,E,B,F,C,A 例：后 序遍歷右圖所示的二叉樹 （ 1）后序遍歷左子樹：即按 L R T 的順序遍歷 左子樹 （ 2）后序遍歷右子樹：即按 L R T 的順序遍歷 右子樹 （ 3）訪問根結(jié)點(diǎn) A A F G E D C B 后序遍歷序列 ： a,b,c,d,,*,+,e,f,/, 中序遍歷序列 ： a,+,b,*,c,,d,,e,/,f 例： 中序遍歷、 后 序 遍歷下圖所示的二叉樹 e d c b f a + * / 例 :已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和 DBGEACHF，則該二叉樹的后序遍歷為 ? A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG B 二叉樹 1 二叉樹： 或為空樹，或由根及兩顆互不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹； 2 二叉樹可以用鏈?zhǔn)浇Y(jié)構(gòu)存儲； 3 遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)點(diǎn)，每個結(jié)點(diǎn)僅被訪問一次。 4 二叉樹的遍歷可以分解為：訪問根，遍歷 左子樹和 遍歷 右子樹，常用的三種遍歷算法： 先序遍歷、中序遍歷、后序遍歷； 5 查找 查找的基本概念 查找 （ 列 ） 表：由同一類型的數(shù)據(jù)元素 （ 或記錄 ） 構(gòu)成的集合 ， 可利用任意數(shù)據(jù)結(jié)構(gòu)實現(xiàn) 。 關(guān)鍵字： 數(shù)據(jù)元素的某個 （ 幾個 ） 數(shù)據(jù)項的值 。 如果一個數(shù)據(jù)項可以 唯一標(biāo)識列表中的一個數(shù)據(jù)元素 ， 則稱其為關(guān)鍵字 。 查找： 根據(jù)給定的關(guān)鍵字值 ， 在特定的查找 （ 列 ） 表中確定一個其關(guān)鍵字與給定值相同的數(shù)據(jù)元素 ， 并返回該數(shù)據(jù)元素在列表中的位置 。 若找到相應(yīng)的數(shù)據(jù)元素 ， 稱查找成功 ， 否則稱查找失敗 5． 2 線性表的查找 順序查找 最簡單的查找方法 順序查找的基本思想 從表的一端開始 ， 順序掃描線性表 ， 依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和待找的值Ｋ相比較 ， 若相等 ， 則查找成功 ， 若整個表掃描完畢 ， 仍末找到關(guān)鍵字等于Ｋ的元素 ， 則查找失敗 。 順序查找既適用于順序表 ， 也適用于鏈表 。 若用順序表 ，查找可從前往后掃描 ， 也可從后往前掃描 ， 但若采用單鏈表 ，則只能從前往后掃描 。 另外 ， 順序查找的表中元素可以是無序的 。 順序查找算法的性能 。 假設(shè)列表長度為 n， 那么查找第 i個數(shù)據(jù)元素時需進(jìn)行 ni+1次比較 ， 即 Ci=ni+1。 又假設(shè)查找每個數(shù)據(jù)元素的概率相等 ， 即 Pi=1/n， 則順序查找算法的平均查找長度為： ? ??? ?????????niniiniii ninnCnCPA SL1 11)1(21)1(11順序查找的特點(diǎn) 順序查找的 優(yōu)點(diǎn)是算法簡單 ，對查找表結(jié)構(gòu)無任何要求，無論是用向量還是用鏈表來存放結(jié)點(diǎn)，也無論結(jié)點(diǎn)之間是否按關(guān)鍵字有序或無序排，它都同樣適用。 順序查找的缺點(diǎn)是 查找效率低 ，當(dāng) n 較大時，不宜采用順序查找 。 查找 （ 折半查找 ） 高效率的查找方法。要求表中元素按關(guān)鍵字有序(升序或降序 )。假設(shè)表中元素為升序排列。 二分查找的基本思想是： 首先將表 中間位置記錄的關(guān)鍵字與查找關(guān)鍵字 比較，如果兩者相等，則查找成功； 否則利用中間位置記錄 將表分成前、后兩個子表， 如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字， 則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。 重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。 例如 ， 假設(shè)給定有序表中關(guān)鍵字為： {05,13,19,21,37,56,64,74,80,88,92}， 查找 K=21的情況： [ 05 1 3 19 21 37 56 64 74 80 88 92 ] l ow hi g ( a) 初始情形 0 1 2 3 4 5 6 7 8 9 10 [ 05 1 3 19 21 37 ] 56