【正文】 下一頁(yè) 上一頁(yè) 停止放映 第 1 頁(yè) 本單元涉及的內(nèi)容 第 3章 、 樹(shù)形結(jié)構(gòu)及基本概念 、 二叉樹(shù) 、 二叉樹(shù)的遍歷 、 森林與二叉樹(shù)的轉(zhuǎn)換 (P81~P90) 下一頁(yè) 上一頁(yè) 停止放映 第 2 頁(yè) 樹(shù)形結(jié)構(gòu) ? 樹(shù)形結(jié)構(gòu)是以分支關(guān)系來(lái)定義的層次結(jié)構(gòu) 。 在客觀世界中樹(shù)形結(jié)構(gòu)廣泛存在 ， 如： 族譜 、家譜 、 行政機(jī)構(gòu)管理 A B C D E F K L G H I J M 下一頁(yè) 上一頁(yè) 停止放映 第 3 頁(yè) 樹(shù)的定義 （邏輯結(jié)構(gòu)） ? 樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)： Tree=（ D， R） 其中： D 是具有相同特性的數(shù)據(jù)元素的集合； R 是 D上邏輯關(guān)系的集合 ， 且滿足： – 在 D中存在唯一的稱為根的數(shù)據(jù)元素 ， 沒(méi)有前趨； – D中其余數(shù)據(jù)元素都有且只有一個(gè)前趨； – D中所有元素 ， 或有若干個(gè)互不相同的后繼 （ 子樹(shù) ） ， 或無(wú)后繼 （ 葉結(jié)點(diǎn) ） ； 則稱 Tree為樹(shù) 。 下一頁(yè) 上一頁(yè) 停止放映 第 4 頁(yè) 樹(shù)的定義 （遞歸結(jié)構(gòu)） ? 樹(shù)是一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T， 有一個(gè)特定結(jié)點(diǎn)稱為根 ， 其余結(jié)點(diǎn)分為 m（ m?0） 個(gè)互不相交的集合T1， T2， … ,Tm。 每個(gè)集合又是一棵樹(shù) ， 被稱為這個(gè)根的子樹(shù) 。 ? 樹(shù)是一種遞歸結(jié)構(gòu) 。 下一頁(yè) 上一頁(yè) 停止放映 第 5 頁(yè) 書(shū)目錄 目錄樹(shù) 樹(shù)結(jié)構(gòu) C1（ 章 ） BOOK ? (節(jié) ) C1 C2 C3 ? ? ? C2 ? ? ? ? ? ? ? C3 樹(shù)結(jié)構(gòu)舉例 下一頁(yè) 上一頁(yè) 停止放映 第 6 頁(yè) 樹(shù)的表示形式 (1) 一般形式 (2) 嵌套形式 (3) 凹入形式 (4) 廣義表形式 下一頁(yè) 上一頁(yè) 停止放映 第 7 頁(yè) 樹(shù)的表示 (一般形式 ) A B C D E F K L G H I J M A (a) (b) (a)只有根結(jié)點(diǎn)的樹(shù) (b)一般的樹(shù) 下一頁(yè) 上一頁(yè) 停止放映 第 8 頁(yè) 結(jié)點(diǎn)（ Node） ? 結(jié)點(diǎn) 包括一個(gè)數(shù)據(jù)元素及若干個(gè)指向其它子樹(shù)的分支；例如 ， A， B， C， D等 。 ? 結(jié)點(diǎn)度 結(jié)點(diǎn)擁有的子樹(shù)數(shù)；例如 ， A的度為 3。 ? 根結(jié)點(diǎn) 無(wú)前趨結(jié)點(diǎn)；例如 ， A結(jié)點(diǎn) 。 ? 支結(jié)點(diǎn) 度不為 0的結(jié)點(diǎn)為支結(jié)點(diǎn)；如 B， C， D等 。 ? 葉結(jié)點(diǎn) 無(wú)后繼結(jié)點(diǎn)；如 K， L， M。 ? 樹(shù)的度 樹(shù)中結(jié)點(diǎn)的最大度數(shù)； 該述樹(shù)的度為 3。 A B C D E F K L G H I J M 下一頁(yè) 上一頁(yè) 停止放映 第 9 頁(yè) 基本術(shù)語(yǔ) （二） ? 子結(jié)點(diǎn) 某結(jié)點(diǎn)子樹(shù)的根為該結(jié)點(diǎn)的子結(jié)點(diǎn)；例如 ， 結(jié)點(diǎn) A的子結(jié)點(diǎn)為 B， C， D。 ? 父結(jié)點(diǎn) 相對(duì)于某結(jié)點(diǎn)子樹(shù)的根 ， 稱該結(jié)點(diǎn)為子樹(shù)根的父結(jié)點(diǎn)；例如子結(jié)點(diǎn) C， B， D的父結(jié)點(diǎn)為 A。 ? 兄弟結(jié)點(diǎn) 同一父親的孩子之間互為兄弟結(jié)點(diǎn)（ Sibling） ； H， I， J互為兄弟 。 ? 路徑 結(jié)點(diǎn)的序列 n1， n2， … ,nk(K?1)是一條路徑 . ? 長(zhǎng)度 長(zhǎng)度等于路徑中結(jié)點(diǎn)數(shù) 1. 下一頁(yè) 上一頁(yè) 停止放映 第 10 頁(yè) 基本術(shù)語(yǔ) （三） ? 層數(shù) 根節(jié)點(diǎn)的層數(shù)為 1， 其它節(jié)點(diǎn)的層數(shù)等于父節(jié)點(diǎn)的層數(shù)加 1。 ? 樹(shù)的深度 節(jié)點(diǎn)的最大層數(shù)值 。 ? 森林 0棵或多棵互不相交的樹(shù)的集合 。 對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)而言 ， 其子樹(shù)的集合即為森林 。 ? 有序數(shù) 如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有順序的 （ 即不能互換 ） ， 則稱該樹(shù)為有序樹(shù) 。 否則 ， 稱為無(wú)序樹(shù) 。 下一頁(yè) 上一頁(yè) 停止放映 第 11 頁(yè) 樹(shù)的操作 ? PARENT（ n， T） 得到樹(shù)中 n的父親結(jié)點(diǎn)； ? ROOT（ T） 求樹(shù)的根 ， 返回樹(shù)根的位置 。 ? CHILD（ T， x， i） 求樹(shù) T中結(jié)點(diǎn) x的第 i個(gè)孩子結(jié)點(diǎn) 。 ? CREATE（ x， T1， T2， … ,Tk) 生成一個(gè)結(jié)點(diǎn) x,下帶子樹(shù) T1,T2,… ,Tk。 ? DELETE(x,i) 刪除結(jié)點(diǎn) x的第 i個(gè)子樹(shù) 。 ? TRAVERSE（ T） 遍歷樹(shù) T。 按次序依此訪問(wèn)樹(shù)中各個(gè)結(jié)點(diǎn) ， 且使每個(gè)結(jié)點(diǎn)只能被訪問(wèn)一次 。 下一頁(yè) 上一頁(yè) 停止放映 第 12 頁(yè) 二、二叉樹(shù) ? 二叉樹(shù)定義 （ 一 ） 定義 n個(gè)結(jié)點(diǎn)的集合 （ n?0） T 的度 ? 2 T = 所有子樹(shù)都有左 、 右之分 （ 次序不能任意顛到 ） 下一頁(yè) 上一頁(yè) 停止放映 第 13 頁(yè) 二叉樹(shù)的定義（二） ? 二叉樹(shù)是另一種樹(shù)形結(jié)構(gòu)： Binary_Tree =( D,R) 其中 : D 是具有相同性質(zhì)的數(shù)據(jù)元素的集合 。 R 是在 D上某個(gè)兩元關(guān)系的集合 ,且滿足 : – D中存在唯一稱為根的數(shù)據(jù)元素 ,沒(méi)有前趨 。 – D中其余元素都有且僅有一個(gè)前趨 。 – 每個(gè)結(jié)點(diǎn)至多只有兩個(gè)子樹(shù) 。 – D中元素 ,或有兩個(gè)互不相交后繼 ,或無(wú)后繼 。 – 左 、 右子樹(shù)分別又是一棵二叉樹(shù) 。 下一頁(yè) 上一頁(yè) 停止放映 第 14 頁(yè) 二叉樹(shù)的五種基本形態(tài) （ a） （ b） （ c） （ d） （ e） O 空結(jié)點(diǎn) O 單個(gè)結(jié)點(diǎn) O O 右子樹(shù)為空 的二叉樹(shù) O O 左子樹(shù)為空 的二叉樹(shù) O O O 左、右子樹(shù) 非空的二叉樹(shù) 下一頁(yè) 上一頁(yè) 停止放映 第 15 頁(yè) 二叉樹(shù)與樹(shù)的區(qū)別 ? 表達(dá)形式 （ 對(duì) 3個(gè)結(jié)點(diǎn) ） 普通樹(shù) 二叉樹(shù) （ a） （ b） （ c） （ d） （ e） O O O O O O 有兩種不同形式 （ a） （ b） O O O O O O O O O O O O O O O 有五種不同形式 下一頁(yè) 上一頁(yè) 停止放映 第 16 頁(yè) 二叉樹(shù)與樹(shù)的區(qū)別 （二） – 二叉樹(shù)是一種特定的樹(shù)結(jié)構(gòu) ， 但不是普通樹(shù)的特殊情況； – 二叉樹(shù)可以為空；而樹(shù)則不能為空； – 二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)分左子樹(shù)和右子樹(shù) ， 而樹(shù)則無(wú)此區(qū)分 。 下一頁(yè) 上一頁(yè) 停止放映 第 17 頁(yè) 二叉樹(shù)的性質(zhì) ? 性質(zhì)一 二叉樹(shù)的第 i層上至多有 2i1 個(gè)結(jié)點(diǎn) （ i ? 1） 。 利用歸納法證明： – i=1時(shí) ， 只有一個(gè)結(jié)點(diǎn) ， 對(duì)的； – 假設(shè)對(duì)所有的 j， 1? j ? i， 命題成立 ， 即在第 j層上 ， 至多有 2j1 個(gè)結(jié)點(diǎn) 。 – 由歸納假設(shè) ， 第 i1層上至多有 2i2 個(gè)結(jié)點(diǎn) 。 由于二叉樹(shù)的每個(gè)結(jié)點(diǎn)的度至多為 2， 故第 i層上的最大結(jié)點(diǎn)數(shù)為第 i1層上的最大 結(jié)點(diǎn)數(shù)的 2倍 ， 即 2*2i2 = 2i1。 下一頁(yè) 上一頁(yè) 停止放映 第 18 頁(yè) 二叉樹(shù)的性質(zhì)（二） ? 性質(zhì)二 深度為 k的二叉樹(shù)上最多含有 2k1個(gè)結(jié)點(diǎn) （ k ? 1） 。 由性質(zhì)一可見(jiàn) ， 深度為 k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為： ? （ 第 i層上的最大結(jié)點(diǎn)數(shù) ） = ? 2i1 = 2k 1 k i=1 i=1 k 下一頁(yè) 上一頁(yè) 停止放映 第 19 頁(yè) 驗(yàn)證二叉樹(shù)的性質(zhì) 1 2 3 8 6 5 7 4 10 9 11 12 13 14 15 ?該二叉樹(shù)的第 3層有 231 個(gè)結(jié)點(diǎn) . ?該二叉樹(shù)深度為 4,最多有 24 1 個(gè)結(jié)點(diǎn) . 下一頁(yè) 上一頁(yè) 停止放映 第 20 頁(yè) 二叉鏈表存儲(chǔ)結(jié)構(gòu) data leftp rightp 左指針 數(shù)據(jù) 右指針 A B C D E F G A B D C E F G ^ ^ ^ ^ ^ ^ ^ ^ 特點(diǎn) : 找子易 , 找父難 . 下一頁(yè) 上一頁(yè) 停止放映 第 21 頁(yè) 三叉鏈表存儲(chǔ)結(jié)構(gòu)