第6章樹和二叉樹A

1、1 （共（共4題）：題）：4.8 4.10 4. 30 4.31 （共（共2題）：題）：5.18 5.30 下周一交下周一交 2 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 3 第第1章章 緒論緒論 第第2章章 線性表線性表 第第3章章 棧和隊(duì)列棧和隊(duì)列 第第4章章 串串 第第5章章 數(shù)組和廣義表數(shù)組和廣義表 第第6 6章章 樹和二叉樹樹和二叉樹 第第7章章 圖圖 第第9章章 查找查找 第第10章章 排序排序 目目 錄錄 4 第第6 6章章 樹和二叉樹樹和二叉樹（Tree & Binary Tree） 6.1 樹的基本概念樹的基本概念 6.2 二叉樹二叉樹 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和

2、線索二叉樹 6.4 樹和森林樹和森林 6.5 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用 特點(diǎn)：特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè) 直接后繼。直接后繼。（一對(duì)多或（一對(duì)多或1:1:n n） 二叉樹的定義、二叉樹的定義、 性質(zhì)和存儲(chǔ)結(jié)構(gòu)性質(zhì)和存儲(chǔ)結(jié)構(gòu) 二叉樹的運(yùn)算二叉樹的運(yùn)算 5 6.16.1 樹的基本概念 6.1.1 樹的定義樹的定義 6.1.2 若干術(shù)語若干術(shù)語 6.1.3 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 6.1.4 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 6.1.5 樹的運(yùn)算樹的運(yùn)算 6 注注1：過去許多書籍中都定義樹為過去許多書籍中都定義樹為n1，曾經(jīng)有，曾經(jīng)有“空樹不是空樹不是 樹樹

3、”的說法，但現(xiàn)在樹的定義已修改。的說法，但現(xiàn)在樹的定義已修改。 注注2：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。 由一個(gè)或多個(gè)由一個(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í)，其余的結(jié)點(diǎn)分為時(shí)，其余的結(jié)點(diǎn)分為m m(m0)(m0)個(gè)個(gè) 互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每個(gè)集合本身又是棵樹，。每個(gè)集合本身又是棵樹， 被稱作這個(gè)根的被稱作這個(gè)根的子樹子樹 。 7 即上層的那個(gè)結(jié)點(diǎn)即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū)直接前驅(qū)) 即

4、下層結(jié)點(diǎn)的子樹的根即下層結(jié)點(diǎn)的子樹的根(直接后繼直接后繼) 同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟） 即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親） 即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn) 即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn) A BC GEI D HFJ FLK 根根 葉子葉子 森林森林 有序樹有序樹 無序樹無序樹 即根結(jié)點(diǎn)即根結(jié)點(diǎn)(沒有前驅(qū)沒有前驅(qū)) 即終端結(jié)點(diǎn)即終端結(jié)點(diǎn)(沒有后繼沒有后繼) 指指m棵不相交的樹的集棵不相交的樹的集 合合(例如刪除例如刪除A后的子樹個(gè)數(shù)后的

5、子樹個(gè)數(shù)) 雙親雙親 孩子孩子 兄弟兄弟 堂兄弟堂兄弟 祖先祖先 子孫子孫 結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一） 結(jié)點(diǎn)各子樹可互換位置。結(jié)點(diǎn)各子樹可互換位置。 8 即樹的數(shù)據(jù)元素即樹的數(shù)據(jù)元素 結(jié)點(diǎn)掛接的子樹數(shù)結(jié)點(diǎn)掛接的子樹數(shù) 結(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)分支結(jié)點(diǎn) 樹的度樹的度 樹的深度樹的深度 (或高度或高度) A BC GEI D HFJ FLK 從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層） 即度為即度為0的結(jié)點(diǎn)，即葉子的結(jié)點(diǎn)，即葉子 即度不為即度不為0的結(jié)點(diǎn)（也

6、稱為內(nèi)部結(jié)點(diǎn)）的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)） 所有結(jié)點(diǎn)度中的最大值（所有結(jié)點(diǎn)度中的最大值（Max各結(jié)點(diǎn)的度各結(jié)點(diǎn)的度） 指所有結(jié)點(diǎn)中最大的層數(shù)（指所有結(jié)點(diǎn)中最大的層數(shù)（Max各結(jié)點(diǎn)的層次各結(jié)點(diǎn)的層次） 問：?jiǎn)枺河疑蠄D中的結(jié)點(diǎn)數(shù)右上圖中的結(jié)點(diǎn)數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4 （有幾個(gè)直接后繼就是幾度，亦稱（有幾個(gè)直接后繼就是幾度，亦稱“次數(shù)次數(shù)”） 9 自學(xué)：樹的抽象數(shù)據(jù)類型定義自學(xué)：樹的抽象數(shù)據(jù)類型定義（見教材（見教材P118-119P118-119） ADT Tree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D: 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R: 基本操作基本操作 P： ADT Tree D是具有相同特

7、性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹；為空集，則稱為空樹；/允許允許n=0 若若D中僅含一個(gè)數(shù)據(jù)元素，則中僅含一個(gè)數(shù)據(jù)元素，則R為空集；為空集； 其他情況下的其他情況下的R存在二元關(guān)系：存在二元關(guān)系： root 唯一唯一 /關(guān)于根的說明關(guān)于根的說明 DjDk= /關(guān)于子樹不相交的說明關(guān)于子樹不相交的說明 /關(guān)于數(shù)據(jù)元素的說明關(guān)于數(shù)據(jù)元素的說明 /至少有至少有15個(gè)，如求樹深，求某結(jié)點(diǎn)的雙親個(gè)，如求樹深，求某結(jié)點(diǎn)的雙親 10 一對(duì)多（一對(duì)多（1:n1:n），），有多個(gè)直接后繼（如家譜有多個(gè)直接后繼（如家譜 樹、目錄樹等等），但只有一個(gè)根結(jié)點(diǎn)，樹、目錄樹等

8、等），但只有一個(gè)根結(jié)點(diǎn)， 且且子樹之間互不相交。子樹之間互不相交。 討論討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？樹是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？ 特點(diǎn)：特點(diǎn)： 仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。 11 討論討論3：樹的樹的鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？方案應(yīng)該怎樣制定？ 復(fù)原困難復(fù)原困難 可用多重鏈表：可用多重鏈表：一個(gè)前趨指針，一個(gè)前趨指針，n n個(gè)后繼指針。個(gè)后繼指針。 細(xì)節(jié)問題：細(xì)節(jié)問題： 樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計(jì)？樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計(jì)？ 即應(yīng)該設(shè)計(jì)成即應(yīng)該設(shè)計(jì)成“等長(zhǎng)等長(zhǎng)”還是還是“不等長(zhǎng)不等長(zhǎng)”？ 缺點(diǎn)：缺點(diǎn)： 等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的

9、度不一定相同）；等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）； 不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。 先研究最簡(jiǎn)單、最有規(guī)律的樹，然先研究最簡(jiǎn)單、最有規(guī)律的樹，然 后設(shè)法把一般的樹轉(zhuǎn)化為簡(jiǎn)單樹。后設(shè)法把一般的樹轉(zhuǎn)化為簡(jiǎn)單樹。 可規(guī)定為：可規(guī)定為： 從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。 重大缺陷：重大缺陷： 解決思路：解決思路： 不能唯一復(fù)原就沒有實(shí)用價(jià)值！不能唯一復(fù)原就沒有實(shí)用價(jià)值！ 討論討論2：樹的樹的順序存儲(chǔ)順序存儲(chǔ)方案應(yīng)該怎樣制定？方案應(yīng)該怎樣制定？ 補(bǔ)充：樹的補(bǔ)充：樹的5種表示法：種表示法： v

10、 圖形表示法圖形表示法 v 嵌套集合表示法嵌套集合表示法 v 廣義表表示法廣義表表示法 v 凹入表示法凹入表示法 v 左孩子右兄弟表示法左孩子右兄弟表示法 13 教師教師學(xué)生學(xué)生其他人員其他人員 20012001級(jí)級(jí) 20022002級(jí)級(jí) 20032003級(jí)級(jí)20042004級(jí)級(jí) 華中科技大學(xué)華中科技大學(xué) 計(jì)算機(jī)系計(jì)算機(jī)系電信系電信系自控系自控系 葉子葉子 根根 子樹子樹 14 15 ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 約定：約定： 根根作為由子樹森林組成的作為由子樹森林組成的表的名字寫在表的左邊表的名字寫在表的左

11、邊 16 又稱目錄表示法又稱目錄表示法 17 datalink 1 link 2 .link n. 樹結(jié)點(diǎn)的結(jié)構(gòu)：樹結(jié)點(diǎn)的結(jié)構(gòu)： 困惑困惑：構(gòu)造樹的結(jié)點(diǎn)時(shí)構(gòu)造樹的結(jié)點(diǎn)時(shí) 應(yīng)當(dāng)開多少個(gè)鏈域應(yīng)當(dāng)開多少個(gè)鏈域? ? 18 data 左孩子左孩子 右兄弟右兄弟 多叉樹轉(zhuǎn)為多叉樹轉(zhuǎn)為 了二叉樹了二叉樹 19 要明確：要明確： 1. 普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難 實(shí)現(xiàn)。實(shí)現(xiàn)。 2. 二叉樹的運(yùn)算仍然是插入、刪除、修改、查找、排序二叉樹的運(yùn)算仍然是插入、刪除、修改、查找、排序 等，但這些操作必須建立在等，但這些操作必須建立在對(duì)樹結(jié)點(diǎn)能夠?qū)浣Y(jié)點(diǎn)

12、能夠“遍歷遍歷”的的 基礎(chǔ)上！基礎(chǔ)上！ 本章重點(diǎn)：本章重點(diǎn)： 二叉樹的表示和實(shí)現(xiàn)二叉樹的表示和實(shí)現(xiàn) 20 6.2 二叉樹二叉樹 為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè) “ “叉叉” ” 的樹？的樹？ 二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)； 可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹， 不失一般性。不失一般性。 6.2.1 二叉樹的定義二叉樹的定義 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu) 注：二叉樹的運(yùn)算見注：二叉樹的運(yùn)算見6.36.3節(jié)節(jié)遍歷遍歷 21 定義：

13、定義：是是n（n0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩 棵互不相交的、分別稱為棵互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對(duì)二（一對(duì)二（1:2） 基本特征基本特征: 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2 2的結(jié)點(diǎn)）；的結(jié)點(diǎn)）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。 基本形態(tài)：基本形態(tài)： 一般一般 的樹的樹 有幾有幾 種？種？ 22 二叉樹的抽象數(shù)據(jù)類型定義二叉樹的抽象數(shù)據(jù)類型定義（見教材（見教材P P121-122121-122） AD

14、T BinaryTree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D: 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R: 基本操作基本操作 P： ADT BinaryTree D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D=，則，則R= ； 若若D，則，則R= H；存在二元關(guān)系：；存在二元關(guān)系： root 唯一唯一 /關(guān)于根的說明關(guān)于根的說明 DjDk= /關(guān)于子樹不相交的說明關(guān)于子樹不相交的說明 /關(guān)于數(shù)據(jù)元素的說明關(guān)于數(shù)據(jù)元素的說明 /關(guān)于左子樹和右子樹的說明關(guān)于左子樹和右子樹的說明 /至少有至少有20個(gè)，如返回某結(jié)點(diǎn)的左孩子，個(gè)，如返回某結(jié)點(diǎn)的左孩子， 或中序遍歷，等等或中序遍歷，等等 23 討論討論1 1：第

15、：第i i層的結(jié)點(diǎn)數(shù)最多是多少？層的結(jié)點(diǎn)數(shù)最多是多少？ （利用二進(jìn)制性質(zhì)可輕松求出）（利用二進(jìn)制性質(zhì)可輕松求出） 性質(zhì)性質(zhì)1: 1: 性質(zhì)性質(zhì)2: 2: 再提問：第再提問：第i i層上至少有層上至少有 個(gè)結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)？1 1 討論討論2 2：深度為：深度為k k的二叉樹，最多有多少個(gè)結(jié)點(diǎn)？的二叉樹，最多有多少個(gè)結(jié)點(diǎn)？ （利用二進(jìn)制性質(zhì)可輕松求出）（利用二進(jìn)制性質(zhì)可輕松求出） 24 性質(zhì)性質(zhì)3: 3: 對(duì)于任何一棵二叉樹，若對(duì)于任何一棵二叉樹，若2 2度的結(jié)點(diǎn)數(shù)有度的結(jié)點(diǎn)數(shù)有n n2 2個(gè)，個(gè)， 則葉子數(shù)（則葉子數(shù)（n n0 0）必定為必定為n n2 21 1 （即（即n0=n2+1） 二叉樹中

16、全部結(jié)點(diǎn)數(shù)二叉樹中全部結(jié)點(diǎn)數(shù)nn0+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)數(shù)二叉樹中全部結(jié)點(diǎn)數(shù)nB+1 ( ( 總分支數(shù)根結(jié)點(diǎn)總分支數(shù)根結(jié)點(diǎn) ) ) （除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支） 總分支數(shù)總分支數(shù)B= n1+2n2 (1(1度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有1 1個(gè)直接后繼，個(gè)直接后繼，2 2度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有2 2個(gè)個(gè)) ) n0+n1+n2= n1+2n2 +1, 即即n0=n2+1 討論討論3 3：二叉樹的葉子數(shù)和度為：二叉樹的葉子數(shù)和度為2 2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？

17、的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？ 25 3. 3. 深度為深度為9 9的二叉樹中至少有的二叉樹中至少有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 ) )9 9 ) )8 8 ) ) ) )9 91 1 2.2.深度為的二叉樹的結(jié)點(diǎn)總數(shù)，最多為深度為的二叉樹的結(jié)點(diǎn)總數(shù)，最多為 個(gè)。個(gè)。 ) )k-1 k-1 ) log) log2 2k k ) ) k k ) )k k 1. 1. 樹中各結(jié)點(diǎn)的度的最大值稱為樹的樹中各結(jié)點(diǎn)的度的最大值稱為樹的 。 ) ) 高度高度 ) ) 層次層次 ) ) 深度深度 ) ) 度度 D C C 課堂練習(xí)：課堂練習(xí)： 26 證明：證明：根據(jù)性質(zhì)根據(jù)性質(zhì)2 2，深度為深度為k k的二叉樹最多只有的二叉

18、樹最多只有2 2k k-1-1個(gè)結(jié)點(diǎn)，且個(gè)結(jié)點(diǎn)，且 完全二叉樹的定義是與同深度的滿二叉樹前面編號(hào)相同，即它完全二叉樹的定義是與同深度的滿二叉樹前面編號(hào)相同，即它 的總結(jié)點(diǎn)數(shù)的總結(jié)點(diǎn)數(shù)n n位于位于k k層和層和k-1k-1層滿二叉樹容量之間，層滿二叉樹容量之間， 即即 2 2k-1 k-1-1n2 -1n2k k-1 -1 或或2 2k-1 k-1n2 n2k k 三邊同時(shí)取對(duì)數(shù)，于是有：三邊同時(shí)取對(duì)數(shù)，于是有：k-1logk-1log2 2nk nk 因?yàn)橐驗(yàn)閗 k是整數(shù)，所以是整數(shù)，所以 k=k= loglog2 2n n +1 +1 可根據(jù)歸納法證明。可根據(jù)歸納法證明。 對(duì)于兩種特殊形式

19、的二叉樹（對(duì)于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹），還），還 特別具備以下特別具備以下2 2個(gè)性質(zhì)：個(gè)性質(zhì)： 27 完全二叉樹：完全二叉樹：深度為深度為k 的的、有有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與 深度為深度為k 的滿二叉樹中編號(hào)從的滿二叉樹中編號(hào)從1至至n的結(jié)的結(jié) 點(diǎn)一一對(duì)應(yīng)。點(diǎn)一一對(duì)應(yīng)。 A O B C GE K D J F IHNML 深度為深度為4 4的滿二叉樹的滿二叉樹 完全二叉樹完全二叉樹 A B C GE I D H F J 為何要研究為何要研究 這兩種特殊這兩種特殊 形式？形式？ 滿二叉樹：滿二叉樹：一棵深度為一棵深度為k 且有且有2k -1個(gè)結(jié)點(diǎn)的二叉樹。個(gè)結(jié)點(diǎn)的二叉樹。 （特點(diǎn)：每層都（特點(diǎn)：每層都“充滿充滿”了結(jié)點(diǎn)）了結(jié)點(diǎn)） 劉解釋：完全二叉樹的特點(diǎn)是只有最后一層葉子不滿，劉解釋：完全二叉樹的特點(diǎn)是只有最