數(shù)據(jù)結(jié)構(gòu)課程之樹(shù)和二叉樹(shù)課件

第5章數(shù)組和廣義表（Arrays&Lists）5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)1第5章數(shù)組和廣義表（Arrays&Lists）5.2、廣義表特點(diǎn)：有次序性有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)＝表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享特別提示：任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。22、廣義表特點(diǎn)：有次序性一個(gè)直接前驅(qū)和一個(gè)直接后繼特別提示：介紹兩種特殊的基本操作：GetHead(L)——取表頭(可能是原子或列表);GetTail(L)——取表尾(一定是列表)。廣義表的抽象數(shù)據(jù)類(lèi)型定義見(jiàn)教材P107-1083廣義表的抽象數(shù)據(jù)類(lèi)型定義見(jiàn)教材P107-10831.GetTail【(b,k,p,h)】＝

;2.GetHead【((a,b),(c,d))】＝

;3.GetTail【((a,b),(c,d))】＝

;4.GetTail【GetHead【((a,b),(c,d))】】＝

;例：求下列廣義表操作的結(jié)果（嚴(yán)題集5.10②）(k,p,h)（b）5.GetTail【（e）】＝

;6.GetHead【(())】＝

.7.GetTail【(())】＝

.()(a,b)()()((c,d))41.GetTail【(b,k,p,h)】＝5.5廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表的元素可以是不同結(jié)構(gòu)（原子或列表），難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常用鏈?zhǔn)浇Y(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示。1.原子結(jié)點(diǎn)：通常設(shè)2個(gè)域valuetag=0標(biāo)志域數(shù)值域注意：列表的“元素”還可以是列表，故結(jié)點(diǎn)有兩種形式：2.表結(jié)點(diǎn)：通常設(shè)3個(gè)域tphptag=1

標(biāo)志域表頭指針表尾指針指向子表指向下一結(jié)點(diǎn)55.5廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表的元素可以是不同結(jié)構(gòu)（原②C=(a,(b,c,d))1^110a0b0d0c1^1例：①E=(a,E)0a1^1第4-5章自測(cè)卷習(xí)題解答6②C=(a,(b,c,d))1^11數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容7數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容7第6章樹(shù)和二叉樹(shù)（Tree&BinaryTree）6.1樹(shù)的基本概念6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.5赫夫曼樹(shù)及其應(yīng)用特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼（1：n）8第6章樹(shù)和二叉樹(shù)（Tree&BinaryTre6.1

樹(shù)的基本概念1. 樹(shù)的定義2. 若干術(shù)語(yǔ)3. 邏輯結(jié)構(gòu)4. 存儲(chǔ)結(jié)構(gòu)5. 樹(shù)的運(yùn)算96.1樹(shù)的基本概念1. 樹(shù)的定義91.樹(shù)的定義注1：過(guò)去許多書(shū)籍中都定義樹(shù)為n≥1，曾經(jīng)有“空樹(shù)不是樹(shù)”的說(shuō)法，但現(xiàn)在樹(shù)的定義已修改。注2：樹(shù)的定義具有遞歸性，即樹(shù)中還有樹(shù)。由一個(gè)或多個(gè)(n≥0)結(jié)點(diǎn)組成的有限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱(chēng)為根（root），當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)分為m(m≥0)個(gè)互不相交的有限集合T1,T2，…，Tm。每個(gè)集合本身又是棵樹(shù)，被稱(chēng)作這個(gè)根的子樹(shù)。101.樹(shù)的定義注1：過(guò)去許多書(shū)籍中都定義樹(shù)為n≥1，曾樹(shù)的表示法有幾種：圖形表示法嵌套集合表示法廣義表表示法目錄表示法左孩子－右兄弟表示法這些表示法的示意圖參見(jiàn)教材P120樹(shù)的抽象數(shù)據(jù)類(lèi)型定義參見(jiàn)教材P118-11911樹(shù)的表示法有幾種：圖形表示法這些表示法的示意圖參見(jiàn)教材P12圖形表示法：教師學(xué)生其他人員99級(jí)2000級(jí)2001級(jí)2002級(jí)……華中科技大學(xué)計(jì)算機(jī)系電信系自控系……葉子根子樹(shù)12圖形表示法：教師學(xué)生其他人員99級(jí)2000級(jí)2001級(jí)200廣義表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J))根作為由子樹(shù)森林組成的表的名字寫(xiě)在表的左邊datalink1link2...linkn麻煩問(wèn)題：應(yīng)當(dāng)開(kāi)設(shè)多少個(gè)鏈域?13廣義表表示法(A(B(E(K,L),F左孩子－右兄弟表示法ABCDEFGHIJKLM數(shù)據(jù)左孩子

右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)))14左孩子－右兄弟表示法ABCDEFGHIJKLM數(shù)據(jù)左孩子樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P118-119）ADTTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTTree若D為空集，則稱(chēng)為空樹(shù)；//允許n=0若D中僅含一個(gè)數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關(guān)系：①root唯一//關(guān)于根的說(shuō)明②Dj∩Dk=Φ//關(guān)于子樹(shù)不相交的說(shuō)明③……//關(guān)于數(shù)據(jù)元素的說(shuō)明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有15個(gè)15樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P118-119）ADTTr2.若干術(shù)語(yǔ)——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹(shù)的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱(chēng)兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)——即該結(jié)點(diǎn)下層子樹(shù)中的任一結(jié)點(diǎn)ABCGEIDHFJMLK根葉子森林有序樹(shù)無(wú)序樹(shù)——即根結(jié)點(diǎn)(沒(méi)有前驅(qū))——即終端結(jié)點(diǎn)(沒(méi)有后繼)——指m棵不相交的樹(shù)的集合(例如刪除A后的子樹(shù)個(gè)數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點(diǎn)各子樹(shù)從左至右有序，不能互換（左為第一）——結(jié)點(diǎn)各子樹(shù)可互換位置。162.若干術(shù)語(yǔ)——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))ABCG2.若干術(shù)語(yǔ)（續(xù)）——即樹(shù)的數(shù)據(jù)元素——結(jié)點(diǎn)掛接的子樹(shù)數(shù)（有幾個(gè)直接后繼就是幾度，亦稱(chēng)“次數(shù)”）結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹(shù)的度樹(shù)的深度(或高度)ABCGEIDHFJMLK——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）——即度為0的結(jié)點(diǎn)，即葉子——即度不為0的結(jié)點(diǎn)（也稱(chēng)為內(nèi)部結(jié)點(diǎn)）——所有結(jié)點(diǎn)度中的最大值（Max{各結(jié)點(diǎn)的度}）——指所有結(jié)點(diǎn)中最大的層數(shù)（Max{各結(jié)點(diǎn)的層次}）問(wèn)：右上圖中的結(jié)點(diǎn)數(shù)＝；樹(shù)的度＝；樹(shù)的深度＝1334172.若干術(shù)語(yǔ)（續(xù)）——即樹(shù)的數(shù)據(jù)元素結(jié)點(diǎn)樹(shù)的度ABC3.樹(shù)的邏輯結(jié)構(gòu)

(特點(diǎn))：一對(duì)多（1:n），有多個(gè)直接后繼（如家譜樹(shù)、目錄樹(shù)等等），但只有一個(gè)根結(jié)點(diǎn)，且子樹(shù)之間互不相交。4.樹(shù)的存儲(chǔ)結(jié)構(gòu)

討論1：樹(shù)是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？————仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。

183.樹(shù)的邏輯結(jié)構(gòu)(特點(diǎn))：一對(duì)多（1:n），有多個(gè)直接討論3：樹(shù)的鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？可規(guī)定為：從上至下、從左至右將樹(shù)的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒(méi)有實(shí)用價(jià)值）。討論2：樹(shù)的順序存儲(chǔ)方案應(yīng)該怎樣制定？可用多重鏈表：一個(gè)前趨指針，n個(gè)后繼指針。細(xì)節(jié)問(wèn)題：樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)類(lèi)型樣式該如何設(shè)計(jì)？

即應(yīng)該設(shè)計(jì)成“等長(zhǎng)”還是“不等長(zhǎng)”？缺點(diǎn)：等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）；不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類(lèi)型）。解決思路：先研究最簡(jiǎn)單、最有規(guī)律的樹(shù)，然后設(shè)法把一般的樹(shù)轉(zhuǎn)化為簡(jiǎn)單樹(shù)。二叉樹(shù)19討論3：樹(shù)的鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？可規(guī)定為：從上至下、從5.樹(shù)的運(yùn)算

要明確：1.普通樹(shù)（即多叉樹(shù)）若不轉(zhuǎn)化為二叉樹(shù)，則運(yùn)算很難實(shí)現(xiàn)。2.二叉樹(shù)的運(yùn)算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在對(duì)樹(shù)結(jié)點(diǎn)能夠“遍歷”的基礎(chǔ)上！（遍歷——指每個(gè)結(jié)點(diǎn)都被訪問(wèn)且僅訪問(wèn)一次，不遺漏不重復(fù)）。本章重點(diǎn)：二叉樹(shù)的表示和實(shí)現(xiàn)205.樹(shù)的運(yùn)算要明確：本章重點(diǎn)：二叉樹(shù)的表示和實(shí)現(xiàn)206.2二叉樹(shù)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹(shù)？二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性。1. 二叉樹(shù)的定義2. 二叉樹(shù)的性質(zhì)3. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（二叉樹(shù)的運(yùn)算見(jiàn)6.3節(jié)）216.2二叉樹(shù)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”1.二叉樹(shù)的定義定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。邏輯結(jié)構(gòu)：一對(duì)二（1：2）

基本特征:①每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（不存在度大于2的結(jié)點(diǎn)）；②左子樹(shù)和右子樹(shù)次序不能顛倒（有序樹(shù)）。基本形態(tài)：

問(wèn)：具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)可能有幾種不同形態(tài)？普通樹(shù)呢？

5種/2種221.二叉樹(shù)的定義定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P121-122）ADTBinaryTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說(shuō)明②Dj∩Dk=Φ//關(guān)于子樹(shù)不相交的說(shuō)明③……//關(guān)于數(shù)據(jù)元素的說(shuō)明

④……

//關(guān)于左子樹(shù)和右子樹(shù)的說(shuō)明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個(gè)23二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P121-122）ADTB2.二叉樹(shù)的性質(zhì)(3+2)討論1：第i層的結(jié)點(diǎn)數(shù)至多是多少？

（利用二進(jìn)制性質(zhì)可輕松求出）

性質(zhì)1:在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>0）。性質(zhì)2:深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k>0）。2i-1個(gè)提問(wèn)：第i層上至少有

個(gè)結(jié)點(diǎn)？1討論2：深度為k的二叉樹(shù)，至多有多少個(gè)結(jié)點(diǎn)？

（利用二進(jìn)制性質(zhì)可輕松求出）2k-1提問(wèn)：深度為k時(shí)至少有

個(gè)結(jié)點(diǎn)？k242.二叉樹(shù)的性質(zhì)(3+2)討論1：第i層的結(jié)點(diǎn)數(shù)至討論3：二叉樹(shù)的葉子數(shù)和度為2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)3:對(duì)于任何一棵二叉樹(shù)，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）證明：∵二叉樹(shù)中全部結(jié)點(diǎn)數(shù)n＝n0+n1+n2(葉子數(shù)＋1度結(jié)點(diǎn)數(shù)＋2度結(jié)點(diǎn)數(shù))又∵二叉樹(shù)中全部結(jié)點(diǎn)數(shù)n＝B+1

(總分支數(shù)＋根結(jié)點(diǎn))（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）而總分支數(shù)B=n1+2n2(1度結(jié)點(diǎn)必有1個(gè)直接后繼，2度結(jié)點(diǎn)必有2個(gè))三式聯(lián)立可得：n0+n1+n2=

n1+2n2+1,即n0=n2+1實(shí)際意義：葉子數(shù)＝2度結(jié)點(diǎn)數(shù)＋1ABCGEIDHFJ25討論3：二叉樹(shù)的葉子數(shù)和度為2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)3:對(duì)于兩種特殊形式的二叉樹(shù)（滿(mǎn)二叉樹(shù)和完全二叉樹(shù)），還特別具備以下2個(gè)性質(zhì)：性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為[log2n]＋1性質(zhì)5:對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為i

的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必為2i＋1；其雙親的編號(hào)必為i/2（i＝1時(shí)為根,除外）。證明：根據(jù)性質(zhì)2，深度為k的二叉樹(shù)最多只有2k-1個(gè)結(jié)點(diǎn)，且完全二叉樹(shù)的定義是與同深度的滿(mǎn)二叉樹(shù)前面編號(hào)相同，即它的總結(jié)點(diǎn)數(shù)n位于k層和k-1層滿(mǎn)二叉樹(shù)容量之間，即2k-1-1<n≤2k-1或2k-1≤n<2k三邊同時(shí)取對(duì)數(shù)，于是有：k-1≤log2n<k因?yàn)閗是整數(shù)，所以k=[log2n]+1可根據(jù)歸納法證明。26對(duì)于兩種特殊形式的二叉樹(shù)（滿(mǎn)二叉樹(shù)和完全二叉樹(shù)），還特別具備滿(mǎn)二叉樹(shù)：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。

（特點(diǎn)：每層都“充滿(mǎn)”了結(jié)點(diǎn)）完全二叉樹(shù)：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。AOBCGEKDJFIHNML深度為4的滿(mǎn)二叉樹(shù)深度為4的完全二叉樹(shù)ABCGEIDHFJ為何要研究這兩種特殊形式？因?yàn)樗鼈冊(cè)陧樞虼鎯?chǔ)方式下可以復(fù)原！

劉解釋?zhuān)和耆鏄?shù)的特點(diǎn)就是，只有最后一層葉子不滿(mǎn)，且全部集中在左邊。

這其實(shí)是順序二叉樹(shù)的含義。在圖論概念中的“完全二叉樹(shù)”是指n1=0的情況。27滿(mǎn)二叉樹(shù)：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。

3.深度為9的二叉樹(shù)中至少有

個(gè)結(jié)點(diǎn)。

Ａ)２9Ｂ)２8Ｃ)９Ｄ)２9－12.深度為k的二叉樹(shù)的結(jié)點(diǎn)總數(shù)，最多為

個(gè)。

Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k課堂練習(xí)：1.樹(shù)Ｔ中各結(jié)點(diǎn)的度的最大值稱(chēng)為樹(shù)Ｔ的

。

Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度課堂討論：①二叉樹(shù)是不是樹(shù)的特殊情況？答：不是！雖然二叉樹(shù)也屬于一種樹(shù)結(jié)構(gòu)，但它是另外單獨(dú)定義的一種樹(shù)，并非一般樹(shù)的特例。它的子樹(shù)有順序規(guī)定，分為左子樹(shù)和右子樹(shù)。不能隨意顛倒。②：滿(mǎn)二叉樹(shù)和完全二叉樹(shù)有什么區(qū)別？答：滿(mǎn)二叉樹(shù)是葉子一個(gè)也不少的樹(shù)，而完全二叉樹(shù)雖然前n-1層是滿(mǎn)的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例?！獭獭?83.深度為9的二叉樹(shù)中至少有個(gè)結(jié)點(diǎn)。2.深度為k4.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)按二叉樹(shù)的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問(wèn)：順序存儲(chǔ)后能否復(fù)原成唯一對(duì)應(yīng)的二叉樹(shù)形狀？答：若是完全/滿(mǎn)二叉樹(shù)則可以做到唯一復(fù)原。而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)5）例如，對(duì)應(yīng)[2]的兩個(gè)孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。T[0]一般不用294.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)A[1]ABCGEID討論：不是完全二叉樹(shù)怎么辦？答：一律轉(zhuǎn)為完全二叉樹(shù)！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便

30討論：不是完全二叉樹(shù)怎么辦？答：一律轉(zhuǎn)為完全二叉樹(shù)！A[1]二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_childright_childdataleft_childright_child二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)類(lèi)型定義：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;一般從根結(jié)點(diǎn)開(kāi)始存儲(chǔ)。

（相應(yīng)地，訪問(wèn)樹(shù)中結(jié)點(diǎn)時(shí)也只能從根開(kāi)始）注：如果需要倒查某結(jié)點(diǎn)的雙親，可以再增加一個(gè)雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。31二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_例：

ABECD^AB^D^C^^E^32例：ABECD^AB^D^C^^E^32第5章數(shù)組和廣義表（Arrays&Lists）5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)33第5章數(shù)組和廣義表（Arrays&Lists）5.2、廣義表特點(diǎn)：有次序性有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)＝表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享特別提示：任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。342、廣義表特點(diǎn)：有次序性一個(gè)直接前驅(qū)和一個(gè)直接后繼特別提示：介紹兩種特殊的基本操作：GetHead(L)——取表頭(可能是原子或列表);GetTail(L)——取表尾(一定是列表)。廣義表的抽象數(shù)據(jù)類(lèi)型定義見(jiàn)教材P107-10835廣義表的抽象數(shù)據(jù)類(lèi)型定義見(jiàn)教材P107-10831.GetTail【(b,k,p,h)】＝

;2.GetHead【((a,b),(c,d))】＝

;3.GetTail【((a,b),(c,d))】＝

;4.GetTail【GetHead【((a,b),(c,d))】】＝

;例：求下列廣義表操作的結(jié)果（嚴(yán)題集5.10②）(k,p,h)（b）5.GetTail【（e）】＝

;6.GetHead【(())】＝

.7.GetTail【(())】＝

.()(a,b)()()((c,d))361.GetTail【(b,k,p,h)】＝5.5廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表的元素可以是不同結(jié)構(gòu)（原子或列表），難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常用鏈?zhǔn)浇Y(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示。1.原子結(jié)點(diǎn)：通常設(shè)2個(gè)域valuetag=0標(biāo)志域數(shù)值域注意：列表的“元素”還可以是列表，故結(jié)點(diǎn)有兩種形式：2.表結(jié)點(diǎn)：通常設(shè)3個(gè)域tphptag=1

標(biāo)志域表頭指針表尾指針指向子表指向下一結(jié)點(diǎn)375.5廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表的元素可以是不同結(jié)構(gòu)（原②C=(a,(b,c,d))1^110a0b0d0c1^1例：①E=(a,E)0a1^1第4-5章自測(cè)卷習(xí)題解答38②C=(a,(b,c,d))1^11數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容39數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容7第6章樹(shù)和二叉樹(shù)（Tree&BinaryTree）6.1樹(shù)的基本概念6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.5赫夫曼樹(shù)及其應(yīng)用特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼（1：n）40第6章樹(shù)和二叉樹(shù)（Tree&BinaryTre6.1

樹(shù)的基本概念1. 樹(shù)的定義2. 若干術(shù)語(yǔ)3. 邏輯結(jié)構(gòu)4. 存儲(chǔ)結(jié)構(gòu)5. 樹(shù)的運(yùn)算416.1樹(shù)的基本概念1. 樹(shù)的定義91.樹(shù)的定義注1：過(guò)去許多書(shū)籍中都定義樹(shù)為n≥1，曾經(jīng)有“空樹(shù)不是樹(shù)”的說(shuō)法，但現(xiàn)在樹(shù)的定義已修改。注2：樹(shù)的定義具有遞歸性，即樹(shù)中還有樹(shù)。由一個(gè)或多個(gè)(n≥0)結(jié)點(diǎn)組成的有限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱(chēng)為根（root），當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)分為m(m≥0)個(gè)互不相交的有限集合T1,T2，…，Tm。每個(gè)集合本身又是棵樹(shù)，被稱(chēng)作這個(gè)根的子樹(shù)。421.樹(shù)的定義注1：過(guò)去許多書(shū)籍中都定義樹(shù)為n≥1，曾樹(shù)的表示法有幾種：圖形表示法嵌套集合表示法廣義表表示法目錄表示法左孩子－右兄弟表示法這些表示法的示意圖參見(jiàn)教材P120樹(shù)的抽象數(shù)據(jù)類(lèi)型定義參見(jiàn)教材P118-11943樹(shù)的表示法有幾種：圖形表示法這些表示法的示意圖參見(jiàn)教材P12圖形表示法：教師學(xué)生其他人員99級(jí)2000級(jí)2001級(jí)2002級(jí)……華中科技大學(xué)計(jì)算機(jī)系電信系自控系……葉子根子樹(shù)44圖形表示法：教師學(xué)生其他人員99級(jí)2000級(jí)2001級(jí)200廣義表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J))根作為由子樹(shù)森林組成的表的名字寫(xiě)在表的左邊datalink1link2...linkn麻煩問(wèn)題：應(yīng)當(dāng)開(kāi)設(shè)多少個(gè)鏈域?45廣義表表示法(A(B(E(K,L),F左孩子－右兄弟表示法ABCDEFGHIJKLM數(shù)據(jù)左孩子

右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)))46左孩子－右兄弟表示法ABCDEFGHIJKLM數(shù)據(jù)左孩子樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P118-119）ADTTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTTree若D為空集，則稱(chēng)為空樹(shù)；//允許n=0若D中僅含一個(gè)數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關(guān)系：①root唯一//關(guān)于根的說(shuō)明②Dj∩Dk=Φ//關(guān)于子樹(shù)不相交的說(shuō)明③……//關(guān)于數(shù)據(jù)元素的說(shuō)明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有15個(gè)47樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P118-119）ADTTr2.若干術(shù)語(yǔ)——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹(shù)的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱(chēng)兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)——即該結(jié)點(diǎn)下層子樹(shù)中的任一結(jié)點(diǎn)ABCGEIDHFJMLK根葉子森林有序樹(shù)無(wú)序樹(shù)——即根結(jié)點(diǎn)(沒(méi)有前驅(qū))——即終端結(jié)點(diǎn)(沒(méi)有后繼)——指m棵不相交的樹(shù)的集合(例如刪除A后的子樹(shù)個(gè)數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點(diǎn)各子樹(shù)從左至右有序，不能互換（左為第一）——結(jié)點(diǎn)各子樹(shù)可互換位置。482.若干術(shù)語(yǔ)——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))ABCG2.若干術(shù)語(yǔ)（續(xù)）——即樹(shù)的數(shù)據(jù)元素——結(jié)點(diǎn)掛接的子樹(shù)數(shù)（有幾個(gè)直接后繼就是幾度，亦稱(chēng)“次數(shù)”）結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹(shù)的度樹(shù)的深度(或高度)ABCGEIDHFJMLK——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）——即度為0的結(jié)點(diǎn)，即葉子——即度不為0的結(jié)點(diǎn)（也稱(chēng)為內(nèi)部結(jié)點(diǎn)）——所有結(jié)點(diǎn)度中的最大值（Max{各結(jié)點(diǎn)的度}）——指所有結(jié)點(diǎn)中最大的層數(shù)（Max{各結(jié)點(diǎn)的層次}）問(wèn)：右上圖中的結(jié)點(diǎn)數(shù)＝；樹(shù)的度＝；樹(shù)的深度＝1334492.若干術(shù)語(yǔ)（續(xù)）——即樹(shù)的數(shù)據(jù)元素結(jié)點(diǎn)樹(shù)的度ABC3.樹(shù)的邏輯結(jié)構(gòu)

(特點(diǎn))：一對(duì)多（1:n），有多個(gè)直接后繼（如家譜樹(shù)、目錄樹(shù)等等），但只有一個(gè)根結(jié)點(diǎn)，且子樹(shù)之間互不相交。4.樹(shù)的存儲(chǔ)結(jié)構(gòu)

討論1：樹(shù)是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？————仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。

503.樹(shù)的邏輯結(jié)構(gòu)(特點(diǎn))：一對(duì)多（1:n），有多個(gè)直接討論3：樹(shù)的鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？可規(guī)定為：從上至下、從左至右將樹(shù)的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒(méi)有實(shí)用價(jià)值）。討論2：樹(shù)的順序存儲(chǔ)方案應(yīng)該怎樣制定？可用多重鏈表：一個(gè)前趨指針，n個(gè)后繼指針。細(xì)節(jié)問(wèn)題：樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)類(lèi)型樣式該如何設(shè)計(jì)？

即應(yīng)該設(shè)計(jì)成“等長(zhǎng)”還是“不等長(zhǎng)”？缺點(diǎn)：等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）；不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類(lèi)型）。解決思路：先研究最簡(jiǎn)單、最有規(guī)律的樹(shù)，然后設(shè)法把一般的樹(shù)轉(zhuǎn)化為簡(jiǎn)單樹(shù)。二叉樹(shù)51討論3：樹(shù)的鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？可規(guī)定為：從上至下、從5.樹(shù)的運(yùn)算

要明確：1.普通樹(shù)（即多叉樹(shù)）若不轉(zhuǎn)化為二叉樹(shù)，則運(yùn)算很難實(shí)現(xiàn)。2.二叉樹(shù)的運(yùn)算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在對(duì)樹(shù)結(jié)點(diǎn)能夠“遍歷”的基礎(chǔ)上?。ū闅v——指每個(gè)結(jié)點(diǎn)都被訪問(wèn)且僅訪問(wèn)一次，不遺漏不重復(fù)）。本章重點(diǎn)：二叉樹(shù)的表示和實(shí)現(xiàn)525.樹(shù)的運(yùn)算要明確：本章重點(diǎn)：二叉樹(shù)的表示和實(shí)現(xiàn)206.2二叉樹(shù)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹(shù)？二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性。1. 二叉樹(shù)的定義2. 二叉樹(shù)的性質(zhì)3. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（二叉樹(shù)的運(yùn)算見(jiàn)6.3節(jié)）536.2二叉樹(shù)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”1.二叉樹(shù)的定義定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。邏輯結(jié)構(gòu)：一對(duì)二（1：2）

基本特征:①每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（不存在度大于2的結(jié)點(diǎn)）；②左子樹(shù)和右子樹(shù)次序不能顛倒（有序樹(shù)）。基本形態(tài)：

問(wèn)：具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)可能有幾種不同形態(tài)？普通樹(shù)呢？

5種/2種541.二叉樹(shù)的定義定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P121-122）ADTBinaryTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說(shuō)明②Dj∩Dk=Φ//關(guān)于子樹(shù)不相交的說(shuō)明③……//關(guān)于數(shù)據(jù)元素的說(shuō)明

④……

//關(guān)于左子樹(shù)和右子樹(shù)的說(shuō)明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個(gè)55二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P121-122）ADTB2.二叉樹(shù)的性質(zhì)(3+2)討論1：第i層的結(jié)點(diǎn)數(shù)至多是多少？

（利用二進(jìn)制性質(zhì)可輕松求出）

性質(zhì)1:在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>0）。性質(zhì)2:深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k>0）。2i-1個(gè)提問(wèn)：第i層上至少有

個(gè)結(jié)點(diǎn)？1討論2：深度為k的二叉樹(shù)，至多有多少個(gè)結(jié)點(diǎn)？

（利用二進(jìn)制性質(zhì)可輕松求出）2k-1提問(wèn)：深度為k時(shí)至少有

個(gè)結(jié)點(diǎn)？k562.二叉樹(shù)的性質(zhì)(3+2)討論1：第i層的結(jié)點(diǎn)數(shù)至討論3：二叉樹(shù)的葉子數(shù)和度為2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)3:對(duì)于任何一棵二叉樹(shù)，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）證明：∵二叉樹(shù)中全部結(jié)點(diǎn)數(shù)n＝n0+n1+n2(葉子數(shù)＋1度結(jié)點(diǎn)數(shù)＋2度結(jié)點(diǎn)數(shù))又∵二叉樹(shù)中全部結(jié)點(diǎn)數(shù)n＝B+1

(總分支數(shù)＋根結(jié)點(diǎn))（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）而總分支數(shù)B=n1+2n2(1度結(jié)點(diǎn)必有1個(gè)直接后繼，2度結(jié)點(diǎn)必有2個(gè))三式聯(lián)立可得：n0+n1+n2=

n1+2n2+1,即n0=n2+1實(shí)際意義：葉子數(shù)＝2度結(jié)點(diǎn)數(shù)＋1ABCGEIDHFJ57討論3：二叉樹(shù)的葉子數(shù)和度為2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)3:對(duì)于兩種特殊形式的二叉樹(shù)（滿(mǎn)二叉樹(shù)和完全二叉樹(shù)），還特別具備以下2個(gè)性質(zhì)：性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為[log2n]＋1性質(zhì)5:對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為i

的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必為2i＋1；其雙親的編號(hào)必為i/2（i＝1時(shí)為根,除外）。證明：根據(jù)性質(zhì)2，深度為k的二叉樹(shù)最多只有2k-1個(gè)結(jié)點(diǎn)，且完全二叉樹(shù)的定義是與同深度的滿(mǎn)二叉樹(shù)前面編號(hào)相同，即它的總結(jié)點(diǎn)數(shù)n位于k層和k-1層滿(mǎn)二叉樹(shù)容量之間，即2k-1-1<n≤2k-1或2k-1≤n<2k三邊同時(shí)取對(duì)數(shù)，于是有：k-1≤log2n<k因?yàn)閗是整數(shù)，所以k=[log2n]+1可根據(jù)歸納法證明。58對(duì)于兩種特殊形式的二叉樹(shù)（滿(mǎn)二叉樹(shù)和完全二叉樹(shù)），還特別具備滿(mǎn)二叉樹(shù)：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。

（特點(diǎn)：每層都“充滿(mǎn)”了結(jié)點(diǎn)）完全二叉樹(shù)：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。AOBCGEKDJFIHNML深度為4的滿(mǎn)二叉樹(shù)深度為4的完全二叉樹(shù)ABCGEIDHFJ為何要研究這兩種特殊形式？因?yàn)樗鼈冊(cè)陧樞虼?/p>