1第5章數(shù)組和廣義表（Arrays&Lists）5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5.4廣義表的定義5.5廣義表的存儲結(jié)構(gòu)22、廣義表特點：有次序性有長度有深度可遞歸可共享一個直接前驅(qū)和一個直接后繼＝表中元素個數(shù)＝表中括號的重數(shù)自己可以作為自己的子表可以為其他廣義表所共享特別提示：任何一個非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。3介紹兩種特殊的基本操作：GetHead(L)——取表頭(可能是原子或列表);GetTail(L)——取表尾(一定是列表)

。廣義表的抽象數(shù)據(jù)類型定義見教材P107-10841.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))55.5廣義表的存儲結(jié)構(gòu)由于廣義表的元素可以是不同結(jié)構(gòu)（原子或列表），難以用順序存儲結(jié)構(gòu)表示，通常用鏈?zhǔn)浇Y(jié)構(gòu)，每個元素用一個結(jié)點表示。1.原子結(jié)點：通常設(shè)2個域valuetag=0標(biāo)志域數(shù)值域注意：列表的“元素”還可以是列表，故結(jié)點有兩種形式：2.表結(jié)點：通常設(shè)3個域tphptag=1

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

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

右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)))15

樹的抽象數(shù)據(jù)類型定義（見教材P118-119）ADTTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTTree若D為空集，則稱為空樹；//允許n=0若D中僅含一個數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關(guān)系：

①root唯一//關(guān)于根的說明

②Dj∩Dk=Φ//關(guān)于子樹不相交的說明

③……//關(guān)于數(shù)據(jù)元素的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有15個162.若干術(shù)語——即上層的那個結(jié)點(直接前驅(qū))——即下層結(jié)點的子樹的根(直接后繼)——同一雙親下的同層結(jié)點（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點（但并非同一雙親）——即從根到該結(jié)點所經(jīng)分支的所有結(jié)點——即該結(jié)點下層子樹中的任一結(jié)點ABCGEIDHFJMLK

根葉子森林有序樹無序樹——即根結(jié)點(沒有前驅(qū))——即終端結(jié)點(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點各子樹從左至右有序，不能互換（左為第一）——結(jié)點各子樹可互換位置。172.若干術(shù)語（續(xù)）——即樹的數(shù)據(jù)元素——結(jié)點掛接的子樹數(shù)（有幾個直接后繼就是幾度，亦稱“次數(shù)”）結(jié)點結(jié)點的度結(jié)點的層次終端結(jié)點分支結(jié)點樹的度樹的深度(或高度)ABCGEIDHFJMLK——從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）——即度為0的結(jié)點，即葉子——即度不為0的結(jié)點（也稱為內(nèi)部結(jié)點）——所有結(jié)點度中的最大值（Max{各結(jié)點的度}）——指所有結(jié)點中最大的層數(shù)（Max{各結(jié)點的層次}）問：右上圖中的結(jié)點數(shù)＝；樹的度＝；樹的深度＝1334183.樹的邏輯結(jié)構(gòu)

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

討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？————仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健?/p>

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

即應(yīng)該設(shè)計成“等長”還是“不等長”？缺點：等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）；不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。解決思路：先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。二叉樹205.樹的運算

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

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

問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？普通樹呢？

5種/2種23二叉樹的抽象數(shù)據(jù)類型定義（見教材P121-122）ADTBinaryTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：

①root唯一//關(guān)于根的說明

②Dj∩Dk=Φ

//關(guān)于子樹不相交的說明

③……

//關(guān)于數(shù)據(jù)元素的說明

④……

//關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個242.二叉樹的性質(zhì)(3+2)討論1：第i層的結(jié)點數(shù)至多是多少？

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

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

個結(jié)點？1討論2：深度為k的二叉樹，至多有多少個結(jié)點？

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

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

(總分支數(shù)＋根結(jié)點)

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

n1+2n2+1,

即n0=n2+1實際意義：葉子數(shù)＝2度結(jié)點數(shù)＋1ABCGEIDHFJ26對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備以下2個性質(zhì)：性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為[log2n]＋1性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i

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

（特點：每層都“充滿”了結(jié)點）完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)。AOBCGEKDJFIHNML深度為4的滿二叉樹深度為4的完全二叉樹ABCGEIDHFJ為何要研究這兩種特殊形式？因為它們在順序存儲方式下可以復(fù)原！

劉解釋：完全二叉樹的特點就是，只有最后一層葉子不滿，且全部集中在左邊。

這其實是順序二叉樹的含義。在圖論概念中的“完全二叉樹”是指n1=0的情況。283.深度為9的二叉樹中至少有

個結(jié)點。

Ａ)２9

Ｂ)２8

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

個。

Ａ)２k-1

Ｂ)log2kＣ)２k－１Ｄ)２k課堂練習(xí)：1.樹Ｔ中各結(jié)點的度的最大值稱為樹Ｔ的

。

Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度課堂討論：①二叉樹是不是樹的特殊情況？答：不是！雖然二叉樹也屬于一種樹結(jié)構(gòu)，但它是另外單獨定義的一種樹，并非一般樹的特例。它的子樹有順序規(guī)定，分為左子樹和右子樹。不能隨意顛倒。②：滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。√√√294.二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGE