【正文】 層肯定是滿的 ) 所以末層葉子數(shù)為 1000511=489個(gè)。 答： 易求出總層數(shù)和末層葉子數(shù)。 √ √ √ ? 性質(zhì) 4 ： 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的 深度為 ? log2n? +1 證明： 設(shè) 完全二叉樹(shù)的深度為 k 則根據(jù)第二條性質(zhì)得 2k1≤ n 2k 即 k1 ≤ log2 n k 因?yàn)? k 只能是整數(shù)，因此， k =?log2n? + 1 課堂討論： 問(wèn) : 設(shè)一棵完全二叉樹(shù)具有 1000個(gè)結(jié)點(diǎn)，則它有 個(gè)葉子結(jié)點(diǎn)，有 個(gè)度為 2的結(jié)點(diǎn)，有 個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有 個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。 ② ：滿二叉樹(shù)和 完全二叉樹(shù) 有什么區(qū)別 ？ 答： 滿二叉樹(shù)是每一層都是滿的二叉樹(shù) ， 而完全二叉樹(shù)雖然前 n1層是滿的 ， 但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn) 。 它的子樹(shù)有順序規(guī)定 ， 分為左子樹(shù)和右子樹(shù) 。 Ａ )２ k1 Ｂ ) log2k Ｃ ) ２ k－１ Ｄ )２ k 課堂練習(xí)： 1. 樹(shù)Ｔ中各結(jié)點(diǎn)的度的最大值稱為樹(shù)Ｔ的 。 3. 深度為 9的完全二叉樹(shù)中至少有 個(gè)結(jié)點(diǎn)。 這其實(shí)是順序二叉樹(shù)的含義。 （特點(diǎn)：每層都“充滿”了結(jié)點(diǎn)） 完全二叉樹(shù)： 深度為 k 的 ， 有 n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 k 的滿二叉樹(shù)中編號(hào)從 1至 n的結(jié)點(diǎn)一一對(duì)應(yīng)。 性質(zhì) 2: 深度為 k的二叉樹(shù)至多有 2k1個(gè)結(jié)點(diǎn)（ k0）。 DeleteChild(T, p, LR)。 DestroyBiTree(amp。 ClearBiTree(amp。T, definition)。e, value)。T)。 LevelOrderTraverse(T, Visit())。 InOrderTraverse(T, Visit())。 BiTreeDepth(T)。 RightSibling(T, e)。 RightChild(T, e)。 Parent(T, e)。 //至少有 20個(gè) 二叉樹(shù)的主要基本操作 ： 查 找 類 插 入 類 刪 除 類 Root(T)。 邏輯結(jié)構(gòu)： 一對(duì)二（ 1： 2） 基本特征 : ① 每個(gè)結(jié)點(diǎn)最多可有兩棵子樹(shù)（不存在度大于 2的結(jié)點(diǎn)）； ② 左子樹(shù)和右子樹(shù)次序不能顛倒（有序樹(shù)）。 本章重點(diǎn)：二叉樹(shù)的定義、性質(zhì)、表示和實(shí)現(xiàn) 線性結(jié)構(gòu) 樹(shù)型結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素 (無(wú)前驅(qū) ) 根結(jié)點(diǎn) (無(wú)前驅(qū) ) 最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼 ) 多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、一個(gè)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、多個(gè)后繼 ) 二叉樹(shù) 為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè) “ 叉 ” 的樹(shù) ？ ? 二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)； ? 可以證明，所有樹(shù)都能轉(zhuǎn)換為唯一的一棵二叉樹(shù)與其對(duì)應(yīng)，不失一般性。 二叉樹(shù) 5. 樹(shù)的運(yùn)算 要明確： 1. 普通樹(shù) （ 即多叉樹(shù) ） 若不轉(zhuǎn)化為二叉樹(shù) ， 則運(yùn)算很難實(shí)現(xiàn) 。 細(xì)節(jié)問(wèn)題：樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計(jì)？ 即應(yīng)該設(shè)計(jì)成 “ 等長(zhǎng) ” 還是 “ 不等長(zhǎng) ” ？ 缺點(diǎn)：等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）； 不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。 重大缺陷：復(fù)原困難 （ 不能唯一復(fù)原就沒(méi)有實(shí)用價(jià)值 ） 。 4. 樹(shù)的存儲(chǔ)結(jié)構(gòu) 討論 1：樹(shù)是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？ ————仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。 2. 若干術(shù)語(yǔ)（續(xù)） ——即樹(shù)的數(shù)據(jù)元素及其分支 ——結(jié)點(diǎn)掛接的子樹(shù)數(shù) （有幾個(gè)直接后繼就是幾度。T, amp。T) // 將樹(shù)清空 刪除類： DestroyTree(amp。T, amp。T) // 初始化置空樹(shù) 插入類： CreateTree(amp。 (Di,{Hi}) D是具有相同特性的數(shù)據(jù)元素的集合。其中，每個(gè)集合本身又是一棵樹(shù)，被稱作這個(gè)根的 子樹(shù) （ SubTree）。 樹(shù)（ Tree）是 n個(gè) (n≥0 )結(jié)點(diǎn)組成的有限集合 T。第 6章 樹(shù)和二叉樹(shù) 第 6章 樹(shù)和二叉樹(shù) 樹(shù)的定義和基本術(shù)語(yǔ) 二叉樹(shù) 遍歷二叉樹(shù)和線索二叉樹(shù) 樹(shù)和森林 赫夫曼樹(shù)及其應(yīng)用 特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼（ 1： n） 樹(shù)的定義和基本術(shù)語(yǔ) 1. 樹(shù)的定義 2. 若干術(shù)語(yǔ) 3. 邏輯結(jié)構(gòu) 4. 存儲(chǔ)結(jié)構(gòu) 5. 樹(shù)的運(yùn)算 1. 樹(shù)的定義 注 1： 過(guò)去許多書(shū)籍中都定義樹(shù)為 n≥1，曾經(jīng)有“空樹(shù)不是樹(shù)”的說(shuō)法，但現(xiàn)在樹(shù)的定義已修改。 注 2： 樹(shù)的定義具有 遞歸性 ，即樹(shù)的定義中還有樹(shù)。在任何一棵非空樹(shù)中 ： （ 1） 有且僅有 一個(gè)結(jié)點(diǎn)稱為根 （ root）； （ 2） 當(dāng) n1時(shí)，其余的結(jié)點(diǎn)可分為 m(m0)個(gè) 互不相交的 有限集合 T1,T2， … ， Tm。 A 只有根結(jié)點(diǎn)的樹(shù) A B C D E F G H I J K L M 有子樹(shù)的樹(shù) 根 子樹(shù) 樹(shù)的抽象數(shù)據(jù)類型定義 ADT Tree{ 數(shù)據(jù)對(duì)象 D: 數(shù)據(jù)關(guān)系 R: 基本操作 P： }ADT Tree 若 D為空集，則稱為空樹(shù)； //允許 n=0 若 D中僅含一個(gè)數(shù)據(jù)元素，則 R為空集； 否則 R={H}， H是如下二元關(guān)系： ① 在 D中存在唯一根元素 root，在 H下無(wú)前驅(qū) ②若 D{root} ≠ Φ ，則存在對(duì) D{root}的一個(gè)劃分，對(duì)任意 j ≠ k，有 Dj∩Dk= Φ，且 ∈ H... ③ 對(duì)應(yīng)于 D{root} 的劃分， H…… 有唯一一個(gè)劃分，對(duì)任意 j ≠ k，有 Hj∩Hk= Φ。 //至少有 15個(gè) 基本操作： 查 找 類 插 入 類 刪 除 類 Root(T) // 求樹(shù)的根結(jié)點(diǎn) 查找類： Value(T, cur_e) // 求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) // 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn) LeftChild(T, cur_e) // 求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) // 求當(dāng)前結(jié)點(diǎn)的右兄弟 TreeEmpty(T) // 判定樹(shù)是否為空樹(shù) TreeDepth(T) // 求樹(shù)的深度 TraverseTree( T, Visit() ) // 遍歷 InitTree(amp。T, definition) // 按定義構(gòu)造樹(shù) Assign(T, cur_e, value) // 給當(dāng)前結(jié)點(diǎn)賦值 InsertChild(amp。p, i, c) // 將以 c為根的樹(shù)插入為結(jié)點(diǎn) p的第 i棵子樹(shù) ClearTree(amp。T) // 銷毀樹(shù)的結(jié)構(gòu) DeleteChild(amp。p, i) // 刪除結(jié)點(diǎn) p的第 i棵子樹(shù) 樹(shù)的表示法有幾種： ? 圖形表示法 ? 嵌套集合表示法 ? 廣義表表示法 ? 凹入表示法 ? 左孩子－右兄弟表示法 這些表示法的示意圖參見(jiàn)教材 P120圖 廣義表表示法 ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 根作為由子樹(shù)森林組成的表的名字寫(xiě)在表的左邊 左孩子－右兄弟表示法 A B C D E F G H I J K L M 數(shù)據(jù) 左孩子 右兄弟 ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 2. 若干術(shù)語(yǔ) ——即上層的那個(gè)結(jié)點(diǎn) (直接前驅(qū) ) ——即下層結(jié)點(diǎn)的子樹(shù)的根 (直接后繼 ) ——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟） ——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親） ——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn) ——即該結(jié)點(diǎn)下層子樹(shù)中的任一結(jié)點(diǎn) A B C G E I D H F J M L K 根 葉子 森林 有序樹(shù) 無(wú)序樹(shù) ——即根結(jié)點(diǎn) (沒(méi)有前驅(qū) ) ——即終端結(jié)點(diǎn) (沒(méi)有后繼 ) ——指 m棵不相交的樹(shù)的集合 (例如刪除 A后的子樹(shù)個(gè)數(shù) ) 雙親 孩子 兄弟 堂兄弟 祖先 子孫 ——結(jié)點(diǎn)各子樹(shù)從左至右有序，不能互換（左為第一） ——結(jié)點(diǎn)各子樹(shù)可互換位置。） 結(jié)點(diǎn) 結(jié)點(diǎn)的度 結(jié)點(diǎn)的層次 終端結(jié)點(diǎn) 分支結(jié)點(diǎn) 樹(shù)的度 樹(shù)的深度 (或高度 ) A B C G E I D H F J M L K ——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層） ——即度為 0的結(jié)點(diǎn)，即葉子 ——即度不為 0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)） ——所有結(jié)點(diǎn)度中的最大值（ Max{各結(jié)點(diǎn)的度 }） ——指所有結(jié)點(diǎn)中最大的層數(shù)（ Max{各結(jié)點(diǎn)的層次 }） 問(wèn)：右上圖中的結(jié)點(diǎn)數(shù)＝ ；樹(shù)的度＝ ；樹(shù)的深度＝ 13 3 4 A B C D E F G H I J K L M 結(jié)點(diǎn) A的度： 3 結(jié)點(diǎn) B的度： 2 結(jié)點(diǎn) M的度： 0 葉子： K， L， F， G， M， I， J 結(jié)點(diǎn) A的孩子： B， C， D 結(jié)點(diǎn) B的孩子： E， F 結(jié)點(diǎn) I的雙親： D 結(jié)點(diǎn) L的雙親： E 結(jié)點(diǎn) B， C， D為兄弟 結(jié)點(diǎn) K， L為兄弟 樹(shù)的度： 3 結(jié)點(diǎn) A的層次： 1 結(jié)點(diǎn) M的層次： 4 樹(shù)的深度： 4 結(jié)點(diǎn) F， G為堂兄弟 結(jié)點(diǎn) A是結(jié)點(diǎn) F， G的祖先 3. 樹(shù)的邏輯結(jié)構(gòu) (特點(diǎn) )： 一對(duì)多（ 1:n），有多個(gè)直接后繼（如家譜樹(shù)、目錄樹(shù)等等），但只有一個(gè)根結(jié)點(diǎn)，且子樹(shù)之間互不相交。 討論 3：樹(shù)的鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？ 可規(guī)定為：從上至下 、 從左至右將樹(shù)的結(jié)點(diǎn)依次存入內(nèi)存 。 討論 2：樹(shù)的順序存儲(chǔ)方案應(yīng)該怎樣制定？ 可用多重鏈表：一個(gè)前驅(qū)指針， n個(gè)后繼指針。 解決思路：先研究最簡(jiǎn)單、最有規(guī)律的樹(shù)狀結(jié)構(gòu)，然后設(shè)法把一般的樹(shù)轉(zhuǎn)化為簡(jiǎn)單樹(shù)。 2. 二叉樹(shù)的運(yùn)算仍然是插入 、 刪除 、 修改 、 查找 、排序等 ， 但這些操作必須建立在 對(duì)樹(shù)結(jié)點(diǎn)能夠 “ 遍歷 ” 的基礎(chǔ)上 ！ （ 遍歷 —— 指每個(gè)結(jié)點(diǎn)都被訪問(wèn)且僅訪問(wèn)一次 ， 不遺漏不重復(fù) ） 。 二叉樹(shù)的定義 二叉樹(shù)的性質(zhì) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) （二叉樹(shù)的運(yùn)算見(jiàn) ） 二叉樹(shù)的定義 定義：是 n（ n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成 。 二叉樹(shù)的五種基本形態(tài)： root 空樹(shù) 只含根結(jié)點(diǎn) root root root L R R 右子樹(shù)為空樹(shù) L 左子樹(shù)為空樹(shù) 左右子樹(shù)均不為空樹(shù) 二叉樹(shù)的抽象數(shù)據(jù)類型定義（見(jiàn)教材 P121122） ADT BinaryTree{ 數(shù)據(jù)對(duì)象 D: 數(shù)據(jù)關(guān)系 R: 基本操作 P： }ADT BinaryTree 若 D=Φ，則 R= Φ ； 若 D≠Φ，則 R= {H}；存在二元關(guān)系： ① root 唯一 //關(guān)于根的說(shuō)明 ② Dl∩Dr= Φ //關(guān)于子樹(shù)不相交的說(shuō)明 ③ …… // 關(guān)于二元關(guān)系的說(shuō)明 ④ …… // 關(guān)于左子樹(shù)和右子樹(shù)的說(shuō)明 D是具有相同特性的數(shù)據(jù)元素的集合。 Value(T, e)。 LeftChild(T, e)。 LeftSibling(T, e)。 BiTreeEmpty(T)。 PreOrderTraverse(T, Visit())。 PostOrderTraverse(T, Visit())。 InitBiTree(amp。 Assign(T, amp。 CreateBiTree(amp。 InsertChild(T, p, LR, c)。T)。T)。 二叉樹(shù)的性質(zhì) (3+2) 討論 1：第 i層的結(jié)點(diǎn)數(shù)至多是多少？ （利用二叉樹(shù)的特性可輕松求出）