【正文】 1 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 2 第 6章 樹和二叉樹（ Tree amp。 Binary Tree ） 樹的基本概念 二叉樹 遍歷二叉樹和線索二叉樹 樹和森林 赫夫曼樹及其應(yīng)用 3 樹的基本概念 1. 樹的定義 2. 若干術(shù)語 3. 邏輯結(jié)構(gòu) 4. 存儲結(jié)構(gòu) 5. 樹的運算 4 1. 樹的定義 注 1： 過去許多書籍中都定義樹為 n≥1，曾經(jīng)有“空樹不是樹”的說法，但現(xiàn)在樹的定義已修改。 注 2： 樹的定義具有 遞歸性 ，即樹中還有樹。 由一個或多個 (n≥0 )結(jié)點組成的有限集合 T，有且僅有 一個結(jié)點稱為根 （ root）， 當(dāng) n1時，其余的結(jié)點分為 m(m≥0) 個 互不相交 的有限集合 T1,T2， … ， Tm。每個集合本身又是棵樹，被稱作這個根的 子樹 。 5 樹的表示法有幾種： ? 圖形表示法 ? 嵌套集合表示法 ? 廣義表表示法 ? 目錄表示法 6 樹的抽象數(shù)據(jù)類型定義 （見教材 P118119） ADT Tree{ 數(shù)據(jù)對象 D: 數(shù)據(jù)關(guān)系 R: 基本操作 P： }ADT Tree 若 D為空集，則稱為空樹； //允許 n=0 若 D中僅含一個數(shù)據(jù)元素，則 R為空集； 其他情況下的 R存在二元關(guān)系： ① root 唯一 //關(guān)于根的說明 ② Dj∩Dk= Φ //關(guān)于子樹不相交的說明 ③ …… //關(guān)于子樹的子樹不相交的說明 D是具有相同特性的數(shù)據(jù)元素的集合。 7 樹的基本概念 1. 樹的定義 2. 若干術(shù)語 3. 邏輯結(jié)構(gòu) 4. 存儲結(jié)構(gòu) 5. 樹的運算 8 2. 若干術(shù)語 ——即上層的那個結(jié)點 (直接前驅(qū) ) ——即下層結(jié)點的子樹的根 (直接后繼 ) ——同一雙親下的同層結(jié)點（孩子之間互稱兄弟） ——即雙親位于同一層的結(jié)點（但并非同一雙親） ——即從根到該結(jié)點所經(jīng)分支的所有結(jié)點 ——即該結(jié)點下層子樹中的任一結(jié)點 A B C G E I D H F J M L K 根 葉子 森林 有序樹 無序樹 ——即根結(jié)點 (沒有前驅(qū) ) ——即終端結(jié)點 (沒有后繼 ) ——指 m棵不相交的樹的集合 (例如刪除 A后的子樹個數(shù) ) 雙親 孩子 兄弟 堂兄弟 祖先 子孫 ——結(jié)點各子樹從左至右有序，不能互換（左為第一） ——結(jié)點各子樹可互換位置。 9 2. 若干術(shù)語（續(xù)） ——即樹的數(shù)據(jù)元素 ——結(jié)點掛接的子樹數(shù)（有幾個直接后繼就是幾度，亦稱“次數(shù)”） 結(jié)點 結(jié)點的度 結(jié)點的層次 終端結(jié)點 分支結(jié)點 樹的度 樹的深度 (或高度 ) A B C G E I D H F J M L K ——從根到該結(jié)點的層數(shù)（根結(jié)點算第一層） ——即度為 0的結(jié)點，即葉子 ——即度不為 0的結(jié)點（也稱為內(nèi)部結(jié)點） ——所有結(jié)點度中的最大值（ Max{各結(jié)點的度 }） ——指所有結(jié)點中最大的層數(shù)（ Max{各結(jié)點的層次 }） 問： 右上圖中的結(jié)點數(shù)＝ ；樹的度＝ ；樹的深度＝ 13 3 4 10 樹的基本概念 1. 樹的定義 2. 若干術(shù)語 3. 邏輯結(jié)構(gòu) 4. 存儲結(jié)構(gòu) 5. 樹的運算 11 3. 樹的邏輯結(jié)構(gòu) (特點 )： 一對多（ 1:n），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點，且 子樹之間互不相交 。 12 樹的基本概念 1. 樹的定義 2. 若干術(shù)語 3. 邏輯結(jié)構(gòu) 4. 存儲結(jié)構(gòu) 5. 樹的運算 13 4. 樹的存儲結(jié)構(gòu) 討論 1： 樹是非線性結(jié)構(gòu)，該怎樣存儲？ ————仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健? 14 討論 3： 樹的 鏈?zhǔn)酱鎯?方案應(yīng)該怎樣制定？ 可規(guī)定為： 從上至下 、 從左至右 將樹的結(jié)點依次存入內(nèi)存 。 重大缺陷： 復(fù)原困難 （ 不能唯一復(fù)原就沒有實用價值 ） 。 討論 2： 樹的 順序存儲 方案應(yīng)該怎樣制定？ 可用多重鏈表： 一個前趨指針， n個后繼指針。 細(xì)節(jié)問題： 樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？ 即應(yīng)該設(shè)計成 “ 等長 ” 還是 “ 不等長 ” ？ 缺點： 等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）； 不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。 解決思路： 先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。 15 樹的基本概念 1. 樹的定義 2. 若干術(shù)語 3. 邏輯結(jié)構(gòu) 4. 存儲結(jié)構(gòu) 5. 樹的運算 16 5. 樹的運算 要明確： 1. 普通樹 （ 即多叉樹 ） 若不轉(zhuǎn)化為二叉樹 ， 則運算很難實現(xiàn) 。 2. 二叉樹的運算仍然是插入 、 刪除 、 修改 、 查找 、排序等 ， 但這些操作必須建立在 對樹結(jié)點能夠“ 遍歷 ” 的基礎(chǔ)上 ！ （ 遍歷 ——指每個結(jié)點都被訪問且僅訪問一次 ，不遺漏不重復(fù) ） 。 17 第 6章 樹和二叉樹（ Tree amp。 Binary Tree ） 樹的基本概念 二叉樹 遍歷二叉樹和線索二叉樹 樹和森林 赫夫曼樹及其應(yīng)用 18 二叉樹 為何要重點研究每結(jié)點最多只有兩個 “ 叉 ” 的樹 ？ ? 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強； ? 可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹。 1. 二叉樹的定義 2. 二叉樹的性質(zhì) 3. 二叉樹的存儲結(jié)構(gòu) 19 1. 二叉樹的定義 定義： 是 n（ n≥0）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為 左子樹和右子樹 的二叉樹組成 。 邏輯結(jié)構(gòu)： 一對二（ 1： 2） 基本特征 : ① 每個結(jié)點最多只有兩棵子樹（不存在度大于 2的結(jié)點）； ② 左子樹和右子樹次序不能顛倒（有序樹）。 基本形態(tài)： 問：具有 3個結(jié)點的二叉樹可能有幾種不同形態(tài)？普通樹呢？ 5種 /2種 20 二叉樹的抽象數(shù)據(jù)類型定義 （見教材 P121122） ADT BinaryTree{ 數(shù)據(jù)對象 D: 數(shù)據(jù)關(guān)系 R: 基本操作 P： }ADT BinaryTree 若 D=Φ，則 R= Φ ； 若 D≠Φ，則 R= {H}；存在二元關(guān)系： ① root 唯一 //關(guān)于根的說明 ② Dj∩Dk= Φ //關(guān)于子樹不相交的說明 ③ …… //關(guān)于根和左右子樹有唯一聯(lián)系的說明 ④ …… //關(guān)于左子樹和右子樹的說明 D是具有相同特性的數(shù)據(jù)元素的集合。 21 二叉樹 1. 二叉樹的定義 2. 二叉樹的性質(zhì) 3. 二叉樹的存儲結(jié)構(gòu) 22 2. 二叉樹的性質(zhì) (3+2) 討論 1：第 i層的結(jié)點數(shù)至多是多少？ （利用二進(jìn)制性質(zhì)可輕松求出） 性質(zhì) 1: 在二叉樹的第 i層上至多有 2i1個結(jié)點（ i0）。 性質(zhì) 2: 深度為 k的二叉樹至多有 2k1個結(jié)點（ k0）。 2i1個 提問：第 i層上至少有 個結(jié)點？ 1 討論 2：深度為 k的二叉樹，至多有多少個結(jié)點？ （利用二進(jìn)制性質(zhì)可輕松求出） 2k1 提問：深度為 k時至少有 個結(jié)點？ k 23 討論 3：二叉樹的葉子數(shù)和度為 2的結(jié)點數(shù)之間有關(guān)系嗎？ 性質(zhì) 3: 對于任何一棵二叉樹，若 2度的結(jié)點數(shù)有 n2個，則葉子數(shù)（ n0） 必定為 n2＋ 1 （即 n0=n2+1） 證明： ∵ 二叉樹中全部結(jié)點數(shù) n＝ n0+n1+n2(葉子數(shù)＋ 1度結(jié)點數(shù)＋ 2度結(jié)點數(shù) ) 又 ∵ 二叉樹中全部結(jié)點數(shù) n＝ B+1 ( 總分支數(shù)＋根結(jié)點 ) （ 除根結(jié)點外 ， 每個結(jié)點必有一個直接前趨 ， 即一個分支 ） 而 總分支數(shù) B= n1+2n2 (1度結(jié)點必有 1個直接后繼 ， 2度結(jié)點必有 2個 ) 三式聯(lián)立可得： n0+n1+n2= n1+2n2 +1, 即 n0=n2+1 實際意義： 葉子數(shù)＝ 2度結(jié)點數(shù)＋ 1 A B C G E I D H F J 24 對于兩種特殊形式的二叉樹（ 滿二叉樹和完全二叉樹 ），還特別具備以下 2個性質(zhì)： 性質(zhì) 4: 具有 n個結(jié)點的完全二叉樹的深度必為 log2n ＋ 1 性質(zhì) 5: 對完全二叉樹，若從上至下、從左至右編號，則編號為 i 的結(jié)點，其左孩子編號必為 2i，其右孩子編號必為 2i＋ 1；其雙親的編號必為 i/2（ i＝ 1 時為根 ,除外 ）。 證明：根據(jù)性質(zhì) 2，深度為 k的二叉樹最多只有 2k1個結(jié)點，且完全二