【正文】 。 證： 設(shè)此二叉樹(shù)的深度為 k，則根據(jù)性質(zhì) 2及完全二叉樹(shù)的定義 得到： 2k1 1 n = 2k 1 或 2k1 = n 2k 取對(duì)數(shù)得到： k 1 log2n k ∵ k是整數(shù)， ∴ k＝ ?log2n? ＋ 1。 18 二叉樹(shù) 數(shù)據(jù)結(jié)構(gòu) 性質(zhì) 4： 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 ?log2n? ＋ 1。滿二叉樹(shù)是完全二叉樹(shù)的特例。 完全二叉樹(shù)： 如果深度為 k、有 n個(gè)結(jié)點(diǎn)的二叉樹(shù)中每個(gè)結(jié)點(diǎn)能夠與深度為 k的順序編號(hào)的滿二叉樹(shù)從 1到 n標(biāo)號(hào)的結(jié)點(diǎn)相對(duì)應(yīng)，則稱這樣的二叉樹(shù)為完全二叉樹(shù)，如下圖 (b)所示。 則： B = n0+n1+n21 又 B = n1+2*n2 ∴ n1+2*n2 = n0+n1+n21 ∴ n0 = n2 + 1 ∴ 原命題成立。 性質(zhì) 3： 設(shè)二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為 n0， 度為 2的結(jié)點(diǎn)數(shù)為 n2，則有 n0=n2+1。 16 二叉樹(shù) 數(shù)據(jù)結(jié)構(gòu) 性質(zhì) 2： 深度為 K的 二叉樹(shù)至多有 2k 1個(gè)結(jié)點(diǎn) 。 2) 設(shè) k = i1 時(shí)成立 。 15 數(shù)據(jù)結(jié)構(gòu) D C H E F B A 1層：結(jié)點(diǎn)個(gè)數(shù) 211=20 個(gè) 2層：結(jié)點(diǎn)個(gè)數(shù) 221=21 個(gè) 3層：結(jié)點(diǎn)個(gè)數(shù) 231=22 個(gè) 二叉樹(shù)的性質(zhì) 性質(zhì) 1： 在二叉樹(shù)的第 i層上至多有 2i1個(gè)結(jié)點(diǎn)。 二叉樹(shù)結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)，即使只有一棵子樹(shù)也要進(jìn)行區(qū)分，說(shuō)明它是左子樹(shù)，還是右子樹(shù)。T, amp。T) // 將樹(shù)清空 DestroyTree(amp。T, amp。T) // 初始化置空樹(shù) CreateTree(amp。 數(shù)據(jù)關(guān)系 R：若 D為空集，則稱為空樹(shù)； 若 D僅有一個(gè)元素， R為空集，否則 R = {H}, H具有以下二元關(guān)系： (1) 在 D中存在唯一的稱為根的元素 root，它在關(guān)系 H中沒(méi)有前驅(qū)； (2) 若 D{root} != ，則存在 D{root}的一個(gè)劃分 D1,D2,…,Dm (m0)，對(duì)任意 j!=k，有 Dj Dk= ,且對(duì)于任意的 i, 唯一存在 數(shù)據(jù)元素 xi Di，有 root,xi H； (3) 對(duì)應(yīng)于 D{root}的劃分， H{root,x1, …, root, xm} 有唯一的 一個(gè)劃分 H1,…Hm, 對(duì)任意的 j!=k有 Hj Hk= ,對(duì)任意的 i, Hi 是 Di上的二元關(guān)系， (Di,{Hi})是一顆符合本定義的樹(shù)，成為根 root的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有 0個(gè)或多個(gè)直接后繼。數(shù)據(jù)結(jié)構(gòu) 樹(shù)的定義和基本術(shù)語(yǔ) 二叉樹(shù) 遍歷二叉樹(shù)和線索二叉樹(shù) 樹(shù)和森林 赫夫曼樹(shù)及其與樹(shù)的應(yīng)用 第六章 樹(shù)和二叉樹(shù) 1 數(shù)據(jù)結(jié)構(gòu) 樹(shù)的定義和基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 樹(shù)的定義和基本術(shù)語(yǔ) 樹(shù)的定義 ： 樹(shù)是由 n(n?0)個(gè)結(jié)點(diǎn)組成的有限集合。如果 n=0，稱為空樹(shù)；如果 n0，則： ? 有一個(gè)特定的稱之為 根 (root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi) 有直接前驅(qū)； ? 除根以外的其它結(jié)點(diǎn)劃分為 m (m ? 0)個(gè)互不相交的有限集合T0,T1,… ,Tm1，每個(gè)集合又是一棵樹(shù)，并且稱之為根的 子樹(shù) 。 A B C E F G H I J K L M D 5 數(shù)據(jù)結(jié)構(gòu) A B C E F G H I J K L M D ROOT SUBTREE1 SUBTREE2 SUBTREE3 6 樹(shù)的定義和基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu) 凹入表表示 : A B E K L F C G D H M I J AB C DGEFHK L I JM嵌套集合表示 : 廣義表表示 : A( B(E(K, L) , F), C(G), D(H(M), I, J) ) 7 樹(shù)的定義和基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu) 例：英國(guó)王室家譜 8 樹(shù)的定義和基本術(shù)語(yǔ) 伊 麗 莎 白 女 王安 德 魯 王 子 愛(ài) 德 華 王 子查 爾 斯 王 子 安 妮 公 主威 廉王 子哈 利王 子比 阿特 利絲公 主歐 吉妮公 主路 易斯公 主彼 得菲 利浦 斯扎 拉菲 利浦 斯數(shù)據(jù)結(jié)構(gòu) ? 結(jié)點(diǎn) (node)：數(shù)據(jù)元素及其分支 ? 結(jié)點(diǎn)的度 (degree)：結(jié)點(diǎn)擁有的子樹(shù)的個(gè)數(shù) ? 樹(shù)的度：樹(shù)中結(jié)點(diǎn)的度的最大值 ? 分支 (branch)結(jié)點(diǎn)：度不為 0的結(jié)點(diǎn) (非終端結(jié)點(diǎn) ) ? 葉子 (leaf)結(jié)點(diǎn)：度為 0的結(jié)點(diǎn) （ 終端結(jié)點(diǎn) ） ? 子 (child)結(jié)點(diǎn)：結(jié)點(diǎn)子樹(shù)的根 ? 雙親 (parent)結(jié)點(diǎn)：子結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn) ? 兄弟 (sibling)結(jié)點(diǎn)：同一雙親的子結(jié)點(diǎn)互稱兄弟結(jié)點(diǎn) ? 結(jié)點(diǎn)的層次 (level)：根為第一層；子結(jié)點(diǎn)層次比雙親結(jié)點(diǎn)的層次加 1 ? 樹(shù)的深度 (depth)：樹(shù)中結(jié)點(diǎn)的最大層次 ? 有序樹(shù)：子樹(shù)從左到右有序（不能互換） ? 無(wú)序樹(shù)：子樹(shù)無(wú)序 ? 森林 (forest)： m（ m≥0） 棵互不相交的樹(shù)的集合 9 樹(shù)的定義和基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu) 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的祖先 10 樹(shù)的定義和基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu) ADT Tree { 數(shù)據(jù)對(duì)象 D： D是具有相同特性的數(shù)據(jù)元素的集合。 基本操作： …… } ?? ?? ?? ? 樹(shù)的定義和基本術(shù)語(yǔ) 11 數(shù)據(jù)結(jié)構(gòu) 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() ) // 遍歷 基本操作 : 查找類 12 樹(shù)的定義和基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu) InitTree(amp。T, definition) // 按定義構(gòu)造樹(shù) Assign(T, cur_e, value) // 給當(dāng)前結(jié)點(diǎn)賦值 InsertChild(amp。p, i, c) // 將以 c為根的樹(shù)插入為 T樹(shù)中 結(jié)點(diǎn) p的第 i棵子樹(shù) 插入類： 13 刪除類： ClearTree(amp。T) // 銷毀樹(shù)的結(jié)構(gòu) DeleteChild(amp。p, i) // 刪除結(jié)點(diǎn) p的第 i棵子樹(shù) 樹(shù)的定義和基本術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu) 14 樹(shù)的定義和基本術(shù)語(yǔ) 邏輯關(guān)系 位置 線性結(jié)構(gòu) 樹(shù)型結(jié)構(gòu) 開(kāi)始結(jié)點(diǎn) 一個(gè)表首數(shù)據(jù)元素 (無(wú)前驅(qū) ) 一個(gè)根結(jié)點(diǎn) (無(wú)前驅(qū) ) 最后結(jié)點(diǎn) 一個(gè)表尾數(shù)據(jù)元素 (無(wú)后繼 ) 多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼 ) 中間結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)只有 一個(gè)前驅(qū)和一個(gè)后繼 每個(gè)結(jié)點(diǎn)有一個(gè)前驅(qū)和多個(gè)后繼 數(shù)據(jù)結(jié)構(gòu) 二叉樹(shù) B C D E F L 二叉樹(shù)示例： 二叉樹(shù)的定義 一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左、右子樹(shù)的，互不相交的二叉樹(shù)組成。這是二叉樹(shù)與樹(shù)的最主要的差別。 證： 1) k = 1 時(shí)成立 。 3) 則 k = i 時(shí)， 第 i層上至多有 2*2i2 = 2i1 個(gè)結(jié)點(diǎn)； ∴ 原命題成立。 證： 利用性質(zhì) 1，將第 1層至第 k層的最多的結(jié)點(diǎn)數(shù)進(jìn)行相加， 則： 1 + 2 + 22 + ………… + 2k2 + 2k1 = 2k 1 ∴ 原命題成立。 證： 設(shè)度為 1的結(jié)點(diǎn)數(shù)為 n1， 樹(shù)枝的總數(shù)為 B。 17 二叉樹(shù) 1 2 3 4 5 數(shù)據(jù)結(jié)構(gòu) 滿二叉樹(shù)： 深度為 k且有 2k1個(gè)結(jié)點(diǎn)的二叉樹(shù)，如下圖 (a)所示。圖 (c)、 (d)是 2棵非完全二叉樹(shù)。 1 2 3 4 5 6 (a) 7 1 2 3 4 5 6 (b) 1 2 3 4 5 (c) 6 1 2 3 4 (d) 5 完全二叉樹(shù) 的所有葉子結(jié)點(diǎn)都出現(xiàn)在第 k層或 k1層。 符號(hào) ?x? 表示不大于 x的最大整數(shù)。 性質(zhì) 5： 如果對(duì)一棵有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)（從上到下，從左到右 ),則對(duì)任一結(jié)點(diǎn) i（ 1=i=n),有： （ 1）如果 i＝ 1，則結(jié)點(diǎn) i無(wú)雙親，是二叉樹(shù)的根；如果 i1，則其雙親是結(jié)點(diǎn) ?i/2? 。 （ 3）如果 2i＋ 1n，則結(jié)點(diǎn) i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn) 2i＋ 1。 證： 對(duì)于 i＝ 1，由完全二叉樹(shù)的定義， 其左孩子是結(jié)點(diǎn) 2，若 2n，即不存在結(jié)點(diǎn) 2，此時(shí)結(jié)點(diǎn) i無(wú)孩子。 對(duì)于 i1，假設(shè)第 j層上的某個(gè)結(jié)點(diǎn)編號(hào)為 i(2j1=i2j1),且2i＋ 1n，其左孩子為 2i，右孩子為 2i＋ 1； 則編號(hào)為 i＋ 1的結(jié)點(diǎn)是編號(hào)為 i的結(jié)點(diǎn)的右兄弟或堂兄弟；