【正文】 點(diǎn)與父結(jié)點(diǎn)間有且只有一個(gè)分支 ， 即除根外每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)分支 ，因此二叉樹總的分支數(shù)為 n1。 i=1 h ? （ 第 i層上的最大結(jié)點(diǎn)數(shù) ） h i=1 = ? 2i1 = 2h1 證明： 由性質(zhì)一可見，深度為 h的二叉樹的最大結(jié)點(diǎn)數(shù)為： 下一頁 上一頁 停止放映 [第 19頁 /91] 包含 n(n0)個(gè)結(jié)點(diǎn)的二叉樹總的分支數(shù)為 n1。由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為 2， 故第 i層上的最大結(jié)點(diǎn)數(shù)為第 i1層上的最大結(jié)點(diǎn)數(shù)的 2倍 ， 即 2 2i2 = 2i1。 利用歸納法證明： – i=1時(shí) ， 只有一個(gè)結(jié)點(diǎn) ， 對(duì)的； – 假設(shè)對(duì)所有的 j， 1? j ? i， 命題成立 ， 即在第 j層上 ， 至多有 2j1 個(gè)結(jié)點(diǎn) 。 O O O O O O O O O O O O O O （ a） 平衡二叉樹 （ b） 非平衡二叉樹 下一頁 上一頁 停止放映 [第 16頁 /91] 二叉排序樹定義 二叉排序樹 或者是空二叉樹； 或者是： 左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 右子樹上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值； 左 、 右子樹本身又是一棵二叉排序樹 。 下一頁 上一頁 停止放映 [第 15頁 /91] 平衡二叉樹 二叉樹上任一結(jié)點(diǎn)的左子樹深度減去右子樹深度的差值 ， 稱為該結(jié)點(diǎn)的平衡因子 。 （ a） 滿二叉樹 （ b） 非滿二叉樹 O O O O O O O O O O O O O 下一頁 上一頁 停止放映 [第 14頁 /91] 完全二叉樹 ?從滿二叉樹葉子所在的層次中，自右向左連續(xù)刪除若干葉子所得到的二叉樹被稱為完全二叉樹。 下一頁 上一頁 停止放映 [第 12頁 /91] 特殊二叉樹 滿二叉樹 完全二叉樹 平衡二叉樹 二叉排序樹 下一頁 上一頁 停止放映 [第 13頁 /91] 滿二叉樹 ?當(dāng)二叉樹每個(gè)分支結(jié)點(diǎn)的度都是 2， 且所有葉子結(jié)點(diǎn)都在同一層上 ， 則稱其為滿二叉樹 。 – 左 、 右子樹分別又是一棵二叉樹 。 – 每個(gè)結(jié)點(diǎn)至多只有兩個(gè)子樹 。 R 是在 D上某個(gè)兩元關(guān)系的集合 ,且滿足 : – D中存在唯一稱為根的數(shù)據(jù)元素 ,沒有前趨 。 ? 森林 ：由零棵或有限棵互不相交的樹組成的集合。 ? 有序樹和無序樹 ：將樹中各結(jié)點(diǎn)的子樹看成自左向右有序的 ， 則稱該樹為有序樹 。 依次類推 ， 子結(jié)點(diǎn)的層次總比父結(jié)點(diǎn)多一層 。 下一頁 上一頁 停止放映 [第 7頁 /91] ? 兄弟結(jié)點(diǎn) ：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互為兄弟結(jié)點(diǎn) 。 ? 分支結(jié)點(diǎn) ：至少有一個(gè)非空子樹的結(jié)點(diǎn) 。 ? 樹的度 ：樹中所有結(jié)點(diǎn)的度的最大值 。 G A C F D E B 樹的一般形式 下一頁 上一頁 停止放映 [第 5頁 /91] 樹結(jié)構(gòu)舉例 C1（ 章 ） BOOK ? (節(jié) ) C1 C2 C3 ? ? ? C2 ? ? ? ? ? ? ? C3 書目錄 目錄樹 樹結(jié)構(gòu) 下一頁 上一頁 停止放映 [第 6頁 /91] 與樹相關(guān)的術(shù)語 ? 結(jié)點(diǎn) ： 在樹結(jié)構(gòu)中一般把 數(shù)據(jù)元素及其若干指向子樹的分支稱為結(jié)點(diǎn) 。 2）除根以外的集合可被劃分為 m個(gè)不相交的子集T1， T2， … ， Tm，其中每個(gè)子集都是樹。若 n=0，則稱其為空樹。 下一頁 上一頁 停止放映 [第 3頁 /91] 樹的邏輯結(jié)構(gòu) 樹是一種數(shù)據(jù)結(jié)構(gòu) ， 可用二元組表示為： Tree=（ D， R） 其中： D 是具有相同特性的數(shù)據(jù)元素的集合； R 是數(shù)據(jù)元素間邏輯關(guān)系的集合 ， 且滿足： – 在 D中存在唯一的稱為根的數(shù)據(jù)元素 ， 沒有前趨； – D中其余數(shù)據(jù)元素都有且只有一個(gè)前趨； – D中所有元素 ， 或有若干個(gè)互不相同的后繼（ 子樹 ） ， 或無后繼 （ 葉結(jié)點(diǎn) ） ； 則稱 Tree為樹 。下一頁 上一頁 停止放映 第 2章 非線性數(shù)據(jù)結(jié)構(gòu) 樹和圖 西安交通大學(xué)計(jì)教中心 下一頁 上一頁 停止放映 [第 2頁 /91] 樹形結(jié)構(gòu) 樹形結(jié)構(gòu)是以分支關(guān)系來定義的層次結(jié)構(gòu) 。在客觀世界中樹形結(jié)構(gòu)廣泛存在 ， 并應(yīng)用于： – 人類社會(huì)的族譜 、 家譜 、 行政區(qū)域劃分管理； – 各種社會(huì)組織機(jī)構(gòu)； – 在計(jì)算機(jī)領(lǐng)域中 ， 用樹表示源程序的語法結(jié)構(gòu)； – 在 OS中 ， 文件系統(tǒng) 、 目錄等組織結(jié)構(gòu)也是用樹來表示的 。 下一頁 上一頁 停止放映 [第 4頁 /91] 樹的遞歸定義 : 樹是由 n個(gè)具有相同特性的數(shù)據(jù)元素組成的集合。一棵非空樹 T必須滿足： 1）其中有一個(gè)特定的元素稱為 T的根 root。它們稱為根 root的子樹。 ? 結(jié)點(diǎn)的度 ：結(jié)點(diǎn)擁有的非空子樹的個(gè)數(shù) 。 ? 葉子結(jié)點(diǎn) ：度為 0的結(jié)點(diǎn) 。 ? 孩子結(jié)點(diǎn)和父結(jié)點(diǎn) ：某結(jié)點(diǎn)所有子樹的根結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn) ， 同時(shí)該結(jié)點(diǎn)也稱為其孩子結(jié)點(diǎn)的父結(jié)點(diǎn) 。 ? 結(jié)點(diǎn)的層次 ：根結(jié)點(diǎn)的層次為 1,其子結(jié)點(diǎn)的層次為 2。 ? 樹的深度 ：樹中結(jié)點(diǎn)所在的最大層次 。 否則稱為無序樹 。 下一頁 上一頁 停止放映 [第 8頁 /91] 二叉樹的定義 二叉樹是另一種樹形結(jié)構(gòu)： Binary_Tree =( D,R) 其中 : D 是具有相同性質(zhì)的數(shù)據(jù)元素的集合 。 – D中其余元素都有且僅有一個(gè)前趨 。 – D中元素 ,或有兩個(gè)互不相交后繼 ,或無后繼 。 下一頁 上一頁 停止放映 [第 9頁 /91] 二叉樹的五種基本形態(tài) （ a） （ b） （ c） （ d） （ e） O 空結(jié)點(diǎn) O 單個(gè)結(jié)點(diǎn) O O 右子樹為空的二叉樹 O O 左子樹為空的二叉樹 左、右子樹非空的二叉樹 O O O 下一頁 上一頁 停止放映 [第 10頁 /91] 二叉樹與樹的區(qū)別 ? 表達(dá)形式 （ 對(duì) 3個(gè)結(jié)點(diǎn) ） 普通樹 二叉樹 （ 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 有五種不同形式 下一頁 上一頁 停止放映 [第 11頁 /91] 二叉樹與樹的區(qū)別（二） ? 觀念 – 二叉樹的子樹有順序關(guān)系 ， 分左子樹和右子樹 ， 而樹則無此區(qū)分 ； – 二叉樹的分支度一定為 0、 1或 2，而樹的度可大于 2。 ?若 k為二叉樹 T的深度 ， 且 T中共有 2k1個(gè)結(jié)點(diǎn)（ k ? 1） ， 則稱 T為滿二叉樹 。 （ a） 完全二叉樹 （ b） 非完全二叉樹 O O O O O O O O O O O 葉結(jié)點(diǎn)只可能出現(xiàn)在層次最大的兩層上。 任意結(jié)點(diǎn)左 、 右子樹的深度之差的絕對(duì)值 ?1 ，這樣的樹稱為平衡二叉樹 。 10 5 7 11 14 18 15 15 14 18 5 10 12 13 7 （ a）二叉排序樹 （ b）非二叉排序樹 下一頁 上一頁 停止放映 [第 17頁 /91] 二叉樹的性質(zhì)一 ? 二叉樹的第 i層上至多有 2i1個(gè)結(jié)點(diǎn) （ i ? 1） 。 – 由歸納假設(shè) ， 第 i1層上至多有 2i2 個(gè)結(jié)點(diǎn) 。 下一頁 上一頁 停止放映 [第 18頁 /91] 二叉樹的性質(zhì)二 深度為 h的二叉樹上至多含 2h1個(gè)結(jié)點(diǎn) (h≥1)。 二叉樹的性質(zhì)三 證明： 二叉樹中除了根結(jié)點(diǎn)之外每個(gè)元素有且只有一個(gè)父結(jié)點(diǎn) 。 O O O O O O O O O O O O O 下一頁 上一頁 停止放映 [第 20頁 /91] 任意二叉樹，若含有 n0個(gè)葉結(jié)點(diǎn)、 n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式 n0=n2+1 。又因?yàn)槌Y(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都有一個(gè)分支進(jìn)入。即結(jié)點(diǎn)總數(shù)為： 1 + n1 + 2n2 （ 23） 由（ 22）和（ 23）兩式可知： n0=n2+1 下一頁 上一頁 停止放映 [第 21頁 /91] 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 [log2(n)]+1。 下一頁 上一頁 停止放映 [第 22頁 /91] 若對(duì)含 n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下 、 從左至右進(jìn)行 1至 n的編號(hào) ， 則對(duì)二叉樹中任意一個(gè)編號(hào)為 i的結(jié)點(diǎn)： ① 若 i=1， 則該結(jié)點(diǎn)是二叉樹的根 ， 無父結(jié)點(diǎn) 。 否則 ， 編號(hào)為 2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)； ③ 若 2i+1n， 則該結(jié)點(diǎn)無右孩子 。 證明：通過對(duì) i進(jìn)行歸納即可得證。 第 i個(gè)結(jié)點(diǎn)的左子結(jié)點(diǎn)就存放在第 2*i的位置 。 下一頁 上一頁 停止放映 [第 24頁 /91] 二叉樹的鏈?zhǔn)酱鎯?chǔ) 結(jié)點(diǎn)定義： struct BinTreeNode { ElemType data。 }。 // 定義根結(jié)點(diǎn)指針 這里 leftChild和 rightChild分別為某一結(jié)點(diǎn)指向其左孩子和右孩子的指針 。 下一頁 上一頁 停止放映 [第 25頁 /91] 二叉樹的鏈?zhǔn)酱鎯?chǔ) A B C ∧ ∧ D ∧ ∧ E ∧ ∧ 利用這種結(jié)點(diǎn)形式存儲(chǔ)的樹一般稱為二叉鏈表。 為了能夠訪問二叉樹，必須保留指向根結(jié)點(diǎn)的指針 。 下一頁 上一頁 停止放映 [第 26頁 /91] 二叉樹的遍歷 ? 遍歷 （ Traversing） 是樹形結(jié)構(gòu)的一種重要運(yùn)算 ， 即按一定的次序系統(tǒng)地訪問結(jié)構(gòu)中的所有結(jié)點(diǎn) ， 使每個(gè)結(jié)點(diǎn)