ch6-1樹和二叉樹

1、1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容：數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容：26.1 樹的基本樹的基本概念概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用特點(diǎn)：特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼。直接后繼。（一對多或（一對多或1:n1:n）二叉樹的定義、二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹的運(yùn)算二叉樹的運(yùn)算第第6 6章章 樹和二叉樹樹和二叉樹（Tree & Binary TreeTree & Binary Tree）36.1 樹的基本概念樹的基本概念一、

2、樹的定義一、樹的定義二、若干術(shù)語二、若干術(shù)語三、邏輯結(jié)構(gòu)三、邏輯結(jié)構(gòu)四、存儲(chǔ)結(jié)構(gòu)四、存儲(chǔ)結(jié)構(gòu)五、樹的運(yùn)算五、樹的運(yùn)算數(shù)據(jù)元素之間是一種層次關(guān)系數(shù)據(jù)元素之間是一種層次關(guān)系4一、一、 樹的定義樹的定義注注1：過去許多書籍中都定義樹為過去許多書籍中都定義樹為n1，曾經(jīng)有，曾經(jīng)有“空樹不是樹空樹不是樹”的說法，但現(xiàn)在樹的定義已的說法，但現(xiàn)在樹的定義已修改。修改。注注2：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。由由n n個(gè)個(gè)( (n0n0) )結(jié)點(diǎn)組成的有限集合結(jié)點(diǎn)組成的有限集合T T，有且僅有，有且僅有一一個(gè)結(jié)點(diǎn)稱為根個(gè)結(jié)點(diǎn)稱為根（rootroot），），當(dāng)當(dāng)n1n1時(shí)，

3、其余的結(jié)點(diǎn)分為時(shí)，其余的結(jié)點(diǎn)分為m m(m0)(m0)個(gè)個(gè)互不相交互不相交的有限集合的有限集合T T1 1,T,T2 2，T Tm m。每個(gè)。每個(gè)集合本身又是棵樹，被稱作這個(gè)根的集合本身又是棵樹，被稱作這個(gè)根的子樹子樹 。遞歸定義：遞歸定義：5ABCDEFGHIJMKLA( )T1T3T2樹根例如例如: :B(E, F(K, L), C(G), D(H, I, J(M)6二、二、 若干術(shù)語若干術(shù)語上層的那個(gè)結(jié)點(diǎn)上層的那個(gè)結(jié)點(diǎn)( (直接前驅(qū)直接前驅(qū)) )下層結(jié)點(diǎn)的子樹的根下層結(jié)點(diǎn)的子樹的根( (直接后繼直接后繼) )同一雙親的孩子之間互稱兄弟同一雙親的孩子之間互稱兄弟從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)

4、點(diǎn)從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)葉子節(jié)點(diǎn)葉子節(jié)點(diǎn): :根結(jié)點(diǎn)根結(jié)點(diǎn)( (沒有前驅(qū)沒有前驅(qū)) )雙親雙親:孩子孩子:兄弟兄弟:祖先祖先:子孫子孫:樹的數(shù)據(jù)元素及若干指向其子樹的分支樹的數(shù)據(jù)元素及若干指向其子樹的分支結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree):結(jié)點(diǎn)結(jié)點(diǎn): :結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。根（根（rootroot）: :終端結(jié)點(diǎn)終端結(jié)點(diǎn)( (沒有后繼沒有后繼),),即度為即度為0 0的節(jié)點(diǎn)的節(jié)點(diǎn)分支節(jié)點(diǎn)分支節(jié)點(diǎn): : 即度不為即度不為0 0的結(jié)點(diǎn)的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)，非終端結(jié)點(diǎn)）（也稱為內(nèi)部結(jié)點(diǎn)，非終端結(jié)點(diǎn)）7結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次

5、:堂兄弟堂兄弟:樹的度樹的度: :樹的深度樹的深度: :( (或高度或高度) )從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）雙親位于同一層的結(jié)點(diǎn)雙親位于同一層的結(jié)點(diǎn)所有結(jié)點(diǎn)度中的最大值（所有結(jié)點(diǎn)度中的最大值（MaxMax各結(jié)點(diǎn)各結(jié)點(diǎn) 的度的度 ）指所有結(jié)點(diǎn)中最大的層次（指所有結(jié)點(diǎn)中最大的層次（MaxMax各結(jié)各結(jié) 點(diǎn)的層次點(diǎn)的層次 ）問：上圖中的結(jié)點(diǎn)數(shù)問：上圖中的結(jié)點(diǎn)數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4EFBAGKLMHIJCDB B、C C、D D是是A A的孩子。的孩子。 A A 是是B B、C C 、D D的雙親。的雙親。 結(jié)點(diǎn)結(jié)點(diǎn)H

6、 H、I I、 J J互為兄弟結(jié)點(diǎn)?；樾值芙Y(jié)點(diǎn)。12348() 有確定的根；有確定的根；() 樹根和子樹根之間為有向關(guān)系。樹根和子樹根之間為有向關(guān)系。有向樹：有向樹：有序樹：有序樹： 子樹之間存在確定的次序關(guān)系。子樹之間存在確定的次序關(guān)系。無序樹：無序樹：子樹之間不存在確定的次序關(guān)系。子樹之間不存在確定的次序關(guān)系。任何一棵非空樹是一個(gè)二元組任何一棵非空樹是一個(gè)二元組 Tree = Tree = （rootroot，F(xiàn) F）其中：其中：root root 被稱為根結(jié)點(diǎn)，被稱為根結(jié)點(diǎn)， F F 被稱為子樹森林被稱為子樹森林指指m m棵棵互不相交的互不相交的樹的集合樹的集合森林：森林：9三、樹的邏

7、輯結(jié)構(gòu)三、樹的邏輯結(jié)構(gòu) 特點(diǎn)：特點(diǎn)：線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無后繼無后繼) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無前驅(qū)無前驅(qū)) )多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )一對多一對多（1:n1:n），有多個(gè)直接后繼（如家譜），有多個(gè)直接后繼（如家譜樹、目錄樹、網(wǎng)頁鏈接等等），但只有樹、目錄樹、網(wǎng)頁鏈接等等），但只有一一個(gè)根結(jié)點(diǎn)個(gè)根結(jié)點(diǎn)，且，且子樹之間互不相交

8、。子樹之間互不相交。10討論討論1 1：樹是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？：樹是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。 討論討論2 2：樹的：樹的順序存儲(chǔ)順序存儲(chǔ)方案應(yīng)該怎樣制定？方案應(yīng)該怎樣制定？可規(guī)定為：可規(guī)定為：從上至下、從左至右將樹的結(jié)點(diǎn)依次存從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。入內(nèi)存。重大缺陷：重大缺陷： 復(fù)原困難復(fù)原困難討論討論3：樹的：樹的鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？方案應(yīng)該怎樣制定？可用多重鏈表：可用多重鏈表：一個(gè)前趨指針，一個(gè)前趨指針，n n個(gè)后繼指針。個(gè)后繼指針。11細(xì)節(jié)問題細(xì)節(jié)問題: :樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)

9、計(jì)？樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計(jì)？ 即應(yīng)該設(shè)計(jì)成即應(yīng)該設(shè)計(jì)成“等長等長”還是還是“不等長不等長”？缺點(diǎn)缺點(diǎn): :等長結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）；等長結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）； 不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。先研究最簡單、最有規(guī)律的樹，然先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。解決思路：解決思路： 因?yàn)闃涫且环N非線性結(jié)構(gòu)，所以不能簡單地用一因?yàn)闃涫且环N非線性結(jié)構(gòu)，所以不能簡單地用一維數(shù)組或單鏈表來存儲(chǔ)樹。為了存儲(chǔ)樹，必須把樹維數(shù)組或單鏈表來存儲(chǔ)樹。為了存儲(chǔ)樹，必須把樹

10、中每個(gè)結(jié)點(diǎn)之間存在的關(guān)系反映在存儲(chǔ)結(jié)構(gòu)之中，中每個(gè)結(jié)點(diǎn)之間存在的關(guān)系反映在存儲(chǔ)結(jié)構(gòu)之中，才能如實(shí)的表現(xiàn)一棵樹。才能如實(shí)的表現(xiàn)一棵樹。 補(bǔ)充：樹的補(bǔ)充：樹的4 4種表示法：種表示法：v 圖形表示法圖形表示法v 嵌套集合表示法嵌套集合表示法v 廣義表表示法廣義表表示法v 凹入表示法凹入表示法13圖形表示法圖形表示法教師教師學(xué)生學(xué)生其他人員其他人員20102010級級 20112011級級 20122012級級20132013級級武漢理工大學(xué)武漢理工大學(xué)計(jì)算機(jī)系計(jì)算機(jī)系數(shù)學(xué)系數(shù)學(xué)系自控系自控系葉子葉子根根子樹子樹14嵌套集合表示法嵌套集合表示法15( A ( B ( E ( K, L ), F ),

11、 C ( G ), D ( H ( M ), I, J ) ) 約定：約定：根根作為由子樹森林組成的作為由子樹森林組成的表的名字寫在表的左邊表的名字寫在表的左邊廣義表表示法廣義表表示法16凹入表示法凹入表示法又稱目錄表示法又稱目錄表示法17五、樹的運(yùn)算五、樹的運(yùn)算 本章重點(diǎn)：本章重點(diǎn)：二叉樹的表示和實(shí)現(xiàn)二叉樹的表示和實(shí)現(xiàn)1. 1. 普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難實(shí)現(xiàn)。很難實(shí)現(xiàn)。2. 2. 二叉樹的運(yùn)算仍然是插入、刪除、修改、查找孩二叉樹的運(yùn)算仍然是插入、刪除、修改、查找孩子或者雙親、排序等，但這些操作必須建立在子或者雙親、排序等，但這些

12、操作必須建立在對對樹結(jié)點(diǎn)能夠樹結(jié)點(diǎn)能夠“遍歷遍歷”的基礎(chǔ)上！的基礎(chǔ)上！186.2 6.2 二叉樹二叉樹一、一、 二叉樹的定義二叉樹的定義二、二、 二叉樹的性質(zhì)二叉樹的性質(zhì)三、三、 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)注：二叉樹的運(yùn)算見注：二叉樹的運(yùn)算見6.36.3節(jié)節(jié)遍歷遍歷為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè) “叉叉” 的樹？的樹？（1 1）二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)；）二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)；（2 2）可以證明所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹。）可以證明所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹。19一、二叉樹的定義一、二叉樹的定義定義：定義：是是n（n0）個(gè)結(jié)點(diǎn)的有

13、限集合，由一個(gè)根結(jié)）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右左子樹和右子樹子樹的二叉樹組成的二叉樹組成 。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對二（一對二（1:2） 基本特征基本特征: : 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2 2的的結(jié)點(diǎn)）；結(jié)點(diǎn)）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。由此定義可以看出，一個(gè)二叉樹中的每個(gè)結(jié)點(diǎn)只能含由此定義可以看出，一個(gè)二叉樹中的每個(gè)結(jié)點(diǎn)只能含有有0 0、 1 1或或2 2個(gè)孩子，而且每個(gè)孩子有左右之分。個(gè)孩子，而且每個(gè)孩子有左右之分。把位于左邊的孩子叫做

14、把位于左邊的孩子叫做左孩子左孩子，位于右邊的孩子叫做位于右邊的孩子叫做右孩子右孩子。 二叉樹或?yàn)榭諛淇諛?；或是由一個(gè)根結(jié)根結(jié)點(diǎn)點(diǎn)加上兩棵兩棵分別稱為左子樹左子樹和右子樹的、互不相交的互不相交的二叉樹二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹21二叉樹的二叉樹的5 5種基本形態(tài)：種基本形態(tài)： 有有5種種（1 1）左右子樹不為空（）左右子樹不為空（2)2)只有左子樹（只有左子樹（3 3）只有右子樹（）只有右子樹（4 4）只有根節(jié)點(diǎn)（）只有根節(jié)點(diǎn)（5 5）空樹）空樹22 二叉樹的基本操作二叉樹的基本操作（1 1）構(gòu)造一棵二叉樹）構(gòu)造一棵二叉樹T T InitBiTreeInitBiTree (

15、&T) (&T)（2 2）清空以）清空以T T為根的二叉樹為根的二叉樹ClearBiTree(&TClearBiTree(&T) )（3 3）判斷二叉樹）判斷二叉樹T T是否為空是否為空 BiTreeEmpty(TBiTreeEmpty(T) )（4 4）獲取給定結(jié)點(diǎn)）獲取給定結(jié)點(diǎn)e e的左孩子和右孩子的左孩子和右孩子 LeftChild(T,eLeftChild(T,e) )，RightChild(T,eRightChild(T,e) )（5 5）獲取給定結(jié)點(diǎn)）獲取給定結(jié)點(diǎn)e e的雙親的雙親 Parent(T,eParent(T,e) )（6 6）遍歷二叉樹）

16、遍歷二叉樹 Traverse(TTraverse(T) )23l性質(zhì)性質(zhì)1: 在二叉樹的第在二叉樹的第i層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i1)。 證明：證明： 用數(shù)學(xué)歸納法。用數(shù)學(xué)歸納法。 1) 當(dāng)當(dāng)i=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。結(jié)論成立。 2) 設(shè)設(shè)i=k時(shí)結(jié)論成立，即第時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。個(gè)。 現(xiàn)證明當(dāng)現(xiàn)證明當(dāng)i=k+1時(shí)，時(shí)， 結(jié)論成立：結(jié)論成立： 因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為2，則第，則第k+1層的結(jié)點(diǎn)層的結(jié)點(diǎn)總數(shù)最多為第總數(shù)最多

17、為第k層上結(jié)點(diǎn)最大數(shù)的層上結(jié)點(diǎn)最大數(shù)的2倍，即倍，即22k-1=2(k+1)-1，故結(jié)論成立。故結(jié)論成立。 度為度為m的樹中第的樹中第i層上至多有層上至多有mi-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), (i1)。二、二叉樹的性質(zhì)二、二叉樹的性質(zhì) (3+2)24l性質(zhì)性質(zhì)2: 深度為深度為k的二叉樹至多有的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k1）。 證明：因?yàn)樯疃葹樽C明：因?yàn)樯疃葹閗的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二的二叉樹的結(jié)點(diǎn)總數(shù)至多為叉樹的結(jié)點(diǎn)總數(shù)至多為 kikikii111122層上的最大結(jié)點(diǎn)

18、個(gè)數(shù)第深度為深度為k的的m叉樹至多有叉樹至多有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。11kmm101111.1kkikimmmmmm25l 性質(zhì)性質(zhì)3: 3: 對任意一棵二叉樹，若終端結(jié)點(diǎn)數(shù)（度為對任意一棵二叉樹，若終端結(jié)點(diǎn)數(shù)（度為0 0的節(jié)的節(jié)點(diǎn)數(shù)）為點(diǎn)數(shù)）為n0，度為，度為2 2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則，則n0=n2+1。 證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹中度為為二叉樹中度為1 1的結(jié)點(diǎn)總數(shù)，的結(jié)點(diǎn)總數(shù)，設(shè)二叉樹中分支數(shù)目為設(shè)二叉樹中分支數(shù)目為B 。 n=n0+n1+n2 ( (葉子數(shù)葉子數(shù)1 1度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)2 2度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)) ) 除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對應(yīng)一

19、個(gè)進(jìn)入它的分支：除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對應(yīng)一個(gè)進(jìn)入它的分支： n=B+1 二叉樹中的分支都是由度為二叉樹中的分支都是由度為1和度為和度為2的結(jié)點(diǎn)發(fā)出的結(jié)點(diǎn)發(fā)出 B=n1+2n2( ( 總分支數(shù)根結(jié)點(diǎn)總分支數(shù)根結(jié)點(diǎn) ) )(1(1度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有1 1個(gè)直接后繼，個(gè)直接后繼，2 2度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有2 2個(gè)個(gè)直接后繼直接后繼) )26l滿二叉樹滿二叉樹： 深度為深度為k且有且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。 滿二叉樹的順序表示，即從二叉樹的根開始，滿二叉樹的順序

20、表示，即從二叉樹的根開始， 層間層間從上到下，從上到下， 層內(nèi)從左到右，逐層進(jìn)行編號(hào)（層內(nèi)從左到右，逐層進(jìn)行編號(hào)（1， 2， ， n）。）。12345678910111213141527l完全二叉樹完全二叉樹： 深度為深度為k，結(jié)點(diǎn)數(shù)為，結(jié)點(diǎn)數(shù)為n的二叉樹，的二叉樹，如果其結(jié)點(diǎn)如果其結(jié)點(diǎn)1n的的位置序號(hào)分別與滿二叉樹的結(jié)點(diǎn)位置序號(hào)分別與滿二叉樹的結(jié)點(diǎn)1n的位置序號(hào)一一對的位置序號(hào)一一對應(yīng)，則為完全二叉樹，應(yīng)，則為完全二叉樹， 滿二叉樹必為完全二叉樹，滿二叉樹必為完全二叉樹， 而完全二叉樹不一定而完全二叉樹不一定是滿二叉樹。是滿二叉樹。 12345678910111213141528l 性質(zhì)性質(zhì)

21、4：具有具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1或或 log2(n+1) 。 證明：設(shè)證明：設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)，根據(jù)性質(zhì)性質(zhì)2有有 2k-1-1n 2k-1 可得可得 2k-1n 2k， 即即 k-1log2n k 因?yàn)橐驗(yàn)閗是整數(shù)，所以是整數(shù)，所以k-1= log2n ，k= log2n +1,故結(jié)論成立。故結(jié)論成立。 又或者：又或者：2k-1n +12k k-1 log2(n+1) k k= log2(n+1) 123456789101112131415 3.23.2 =3; =3; 3.23.2 =4=4

22、29l性質(zhì)性質(zhì)5:對完全二叉樹中編號(hào)為對完全二叉樹中編號(hào)為i的結(jié)點(diǎn)的結(jié)點(diǎn)(1in,n1,n為為結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù))有：有：(1)(1)若若i=1,i=1,則結(jié)點(diǎn)則結(jié)點(diǎn)i i是二叉樹的根，無雙親。是二叉樹的根，無雙親。 若若i1,i1,則它的雙親結(jié)點(diǎn)的編號(hào)為則它的雙親結(jié)點(diǎn)的編號(hào)為 i/2i/2 。當(dāng)當(dāng)i i為偶數(shù)為偶數(shù)時(shí)時(shí), ,其雙親結(jié)點(diǎn)的編號(hào)為其雙親結(jié)點(diǎn)的編號(hào)為i/2,i/2,它是雙親結(jié)點(diǎn)的左孩子結(jié)它是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn)點(diǎn), ,當(dāng)當(dāng)i i為奇數(shù)時(shí)為奇數(shù)時(shí), ,其雙親結(jié)點(diǎn)的編號(hào)為其雙親結(jié)點(diǎn)的編號(hào)為(i-1)/2,(i-1)/2,它是雙它是雙親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。 A B C D E

23、 H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完完 全全 二二 叉叉 樹樹 30(2)若編號(hào)為若編號(hào)為i的結(jié)點(diǎn)有左孩子結(jié)點(diǎn)的結(jié)點(diǎn)有左孩子結(jié)點(diǎn),則其左孩子結(jié)點(diǎn)則其左孩子結(jié)點(diǎn)的編號(hào)為的編號(hào)為2i；若編號(hào)為；若編號(hào)為i的結(jié)點(diǎn)有右孩子結(jié)點(diǎn)的結(jié)點(diǎn)有右孩子結(jié)點(diǎn),則其則其右孩子結(jié)點(diǎn)的編號(hào)為右孩子結(jié)點(diǎn)的編號(hào)為(2i+1)。當(dāng)當(dāng)2in，則結(jié)點(diǎn)，則結(jié)點(diǎn)i無左孩子，無左孩子則結(jié)點(diǎn)無左孩子，無左孩子則結(jié)點(diǎn)i為葉為葉子結(jié)點(diǎn)；當(dāng)子結(jié)點(diǎn)；當(dāng)2i+1n，則結(jié)點(diǎn)無右孩子。，則結(jié)點(diǎn)無右孩子。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 1 0 11 完完 全全 二二

24、 叉叉 樹樹 L L121231(3)(3)若若n n為奇數(shù)為奇數(shù), ,則每個(gè)分支結(jié)點(diǎn)都既有左孩子結(jié)點(diǎn)則每個(gè)分支結(jié)點(diǎn)都既有左孩子結(jié)點(diǎn), ,也有右孩子結(jié)點(diǎn)；也有右孩子結(jié)點(diǎn)；若若n n為偶數(shù)為偶數(shù), ,則編號(hào)最大的分支結(jié)則編號(hào)最大的分支結(jié)點(diǎn)點(diǎn)( (編號(hào)為編號(hào)為n/2)n/2)只有左孩子結(jié)點(diǎn)只有左孩子結(jié)點(diǎn), ,沒有右孩子結(jié)點(diǎn)沒有右孩子結(jié)點(diǎn), ,其余分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)。其余分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 1 0 11 完完 全全 二二 叉叉 樹樹 L L121232討論：討論：滿二叉樹和完全二叉樹有什么區(qū)別？滿二叉樹

25、和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個(gè)也不少的樹，而完全二叉樹答：滿二叉樹是葉子一個(gè)也不少的樹，而完全二叉樹雖然前雖然前k-1k-1層是滿的，但最底層卻允許在右邊缺少連層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿二叉樹是完全二叉樹的一個(gè)特例。續(xù)若干個(gè)結(jié)點(diǎn)。滿二叉樹是完全二叉樹的一個(gè)特例。為何要研究這兩為何要研究這兩種特殊形式？種特殊形式？333. 3. 深度為深度為9 9的二叉樹中至少有的二叉樹中至少有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度為的二叉樹的結(jié)點(diǎn)總數(shù)，最多為深度為的二叉樹的結(jié)點(diǎn)總數(shù)，最多為 個(gè)。個(gè)。 ) )k-1k-1

26、) log) log2 2k k ) ) k k ) )k k1. 1. 樹中各結(jié)點(diǎn)的度的最大值稱為樹的樹中各結(jié)點(diǎn)的度的最大值稱為樹的 。 ) ) 高度高度 ) ) 層次層次 ) ) 深度深度 ) ) 度度DCC課堂練習(xí)：課堂練習(xí)：34 一棵完全二叉樹有一棵完全二叉樹有1000個(gè)結(jié)點(diǎn)，則它必有個(gè)結(jié)點(diǎn)，則它必有 個(gè)個(gè)葉子結(jié)點(diǎn)，有葉子結(jié)點(diǎn)，有 個(gè)度為個(gè)度為2的結(jié)點(diǎn)，有的結(jié)點(diǎn)，有 個(gè)結(jié)點(diǎn)只個(gè)結(jié)點(diǎn)只有非空左子樹，有有非空左子樹，有 個(gè)結(jié)點(diǎn)只有非空右子樹。個(gè)結(jié)點(diǎn)只有非空右子樹。例：例：0 0分析題意：已知分析題意：已知n=1000,n=1000,求求n n0 0和和n n2 2, ,還要判斷末葉子是還要

27、判斷末葉子是掛在左邊還是右邊？掛在左邊還是右邊？答案：答案：因?yàn)樽詈笠粋€(gè)結(jié)點(diǎn)編號(hào)因?yàn)樽詈笠粋€(gè)結(jié)點(diǎn)編號(hào)10001000是偶數(shù)，所以它必為編號(hào)為是偶數(shù)，所以它必為編號(hào)為500500的的節(jié)點(diǎn)的左子樹。因此，度為節(jié)點(diǎn)的左子樹。因此，度為1 1的節(jié)點(diǎn)數(shù)為的節(jié)點(diǎn)數(shù)為1 1個(gè)，即個(gè)，即n1=1n1=1，有，有1 1個(gè)個(gè)結(jié)點(diǎn)只有非空左子樹結(jié)點(diǎn)只有非空左子樹全部葉子數(shù)全部葉子數(shù)n n0 0 , ,則根據(jù)性質(zhì)則根據(jù)性質(zhì)3 3，度為，度為2 2的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù)n n2 2n n0 01 1。由：由：1000=n1000=n0 0+n+n2 2+1 +1 故：故：n n0 0=500, n=500, n2 2=499

28、.=499.請注意：請注意：葉子結(jié)點(diǎn)總數(shù)葉子結(jié)點(diǎn)總數(shù)末層葉子數(shù)！末層葉子數(shù)！50049935三、三、 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)1 1、順序存儲(chǔ)、順序存儲(chǔ)對完全二叉樹的結(jié)點(diǎn)對完全二叉樹的結(jié)點(diǎn)按按“自上而下、從左自上而下、從左至右至右”編號(hào)，用一組編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。連續(xù)的存儲(chǔ)單元存儲(chǔ)。將編號(hào)為將編號(hào)為i i的結(jié)點(diǎn)存儲(chǔ)的結(jié)點(diǎn)存儲(chǔ)在在i-1i-1號(hào)單元中。號(hào)單元中。012345678#define MAX_TREE_SIZE 100 #define MAX_TREE_SIZE 100 / / 二叉樹的最大結(jié)點(diǎn)數(shù)二叉樹的最大結(jié)點(diǎn)數(shù)typedeftypedef TElemTypeTE

29、lemType SqBiTreeMAX_TREE_SIZESqBiTreeMAX_TREE_SIZE; ; / 0/ 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreeSqBiTree btbt; ;79563412836討論：討論：不是完全二叉樹怎么辦？不是完全二叉樹怎么辦？答：答：一律轉(zhuǎn)為完全二叉樹！一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上方法很簡單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)虛結(jié)點(diǎn)”，其，其內(nèi)容為空。內(nèi)容為空。01234567815ABECD缺點(diǎn)缺點(diǎn)：浪費(fèi)空間；浪費(fèi)空間； 插入、刪除不便插入、刪除不便 37ABCD(a) 單支二叉樹ABCD(b) 順 序 存 儲(chǔ) 結(jié) 構(gòu)13715 A B C D E H I J K F G