西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

精心整理

第一章緒論

1、數(shù)據(jù)結(jié)構(gòu)的主要研究?jī)?nèi)容

①數(shù)據(jù)的邏輯結(jié)構(gòu)一數(shù)據(jù)關(guān)系之間的邏輯關(guān)系

②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

2、數(shù)據(jù)邏輯結(jié)構(gòu)的種類：集合、線性表、樹(shù)和圖的性質(zhì)和特點(diǎn)。

。集合結(jié)構(gòu)中的元素是各自獨(dú)立的，元素之間沒(méi)有聯(lián)系

線性結(jié)構(gòu)中的元素是一個(gè)接一個(gè)串聯(lián)起來(lái)的，它有一個(gè)頭元素和一個(gè)尾元素，

其余為中間元素；每個(gè)中間元素既有前驅(qū)元素，又有后繼元素

在樹(shù)結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)只有后繼結(jié)點(diǎn)，而沒(méi)有前驅(qū)結(jié)點(diǎn)；除樹(shù)根結(jié)點(diǎn)外，每個(gè)

結(jié)點(diǎn)都有唯---個(gè)前驅(qū)結(jié)點(diǎn)，又稱為是父結(jié)點(diǎn)或雙親結(jié)點(diǎn)

在圖結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)或稱頂點(diǎn)都可以有任意多個(gè)前驅(qū)結(jié)點(diǎn)和任意多個(gè)后繼結(jié)

點(diǎn)。

。樹(shù)結(jié)構(gòu)是圖結(jié)構(gòu)的特例，線性結(jié)構(gòu)是樹(shù)結(jié)構(gòu)的特例。為了區(qū)別于線性結(jié)構(gòu)，時(shí)

常把樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)稱為非線性結(jié)構(gòu)。

3、數(shù)據(jù)結(jié)構(gòu)的二元組定義，能根據(jù)給出的二元組來(lái)判斷數(shù)據(jù)的邏輯結(jié)構(gòu)類型。

。集合結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為：

K={A,B,C,D,E,F,G}

R={}

線性結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為：

K={A,B,C,D,E,F,G}

R={<A,B>,<B,C>,<C,D>,<D,E>,<E,F>,<F,G>}

精心整理

。樹(shù)結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為：

K={A,B,C,D,E,F,G}

R={<A,B>,<A,C>,<A,D>,<C,E>,<C,F>,<D,G>}

圖結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為：

K={A,B,C,D,E,F,G}

R={〈A,B>,<A,C>,<A,G>,<D,G>,<D,F>,<C,E>,<C,F>,<G,F>}

4、了解數(shù)據(jù)的幾種存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）及它們各自的性質(zhì)和特點(diǎn)。

（1）順序的方法：將邏輯上相鄰的元素存儲(chǔ)到物理上相鄰的存儲(chǔ)位置.常用于線性

的數(shù)據(jù)結(jié)構(gòu).

（2）鏈?zhǔn)浇Y(jié)構(gòu)：給結(jié)點(diǎn)附加一個(gè)指針字段，指出其后繼節(jié)點(diǎn)的位置，即存放結(jié)點(diǎn)的

存儲(chǔ)單元分為兩部分：

數(shù)據(jù)項(xiàng)指針項(xiàng)

（3）散列（hashing）結(jié)構(gòu)：散列的方法是用結(jié)點(diǎn)的關(guān)鍵字值直接計(jì)算出結(jié)點(diǎn)的存

儲(chǔ)地址。這個(gè)取值函數(shù)也稱為散列函數(shù)。

5、數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和總的數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系

邏輯結(jié)構(gòu)相同，但存儲(chǔ)結(jié)構(gòu)不同，則認(rèn)為是不同的數(shù)據(jù)結(jié)構(gòu)。如順序表和鏈

表具有相同的邏輯結(jié)構(gòu)，但存儲(chǔ)結(jié)構(gòu)分別為順序結(jié)構(gòu)和鏈表結(jié)構(gòu)

6、算法的設(shè)計(jì)要求有那些，會(huì)結(jié)合實(shí)際的語(yǔ)言設(shè)計(jì)來(lái)說(shuō)明這些要求

1）正確性：對(duì)于合法的輸入產(chǎn)生符合要求的輸出；

2）可讀性：算法應(yīng)該易讀、便于交流，這也是保證算法正確性的前提；添加注釋

也是一種增加可讀性的辦法；

3）健壯性：當(dāng)輸入非法時(shí)，算法還能做出適當(dāng)?shù)姆磻?yīng)而不會(huì)崩潰，如輸出錯(cuò)誤信

息；算法中應(yīng)該考慮適當(dāng)?shù)腻e(cuò)誤處理；

4)效率高且內(nèi)存消耗小：效率高指運(yùn)行時(shí)間短。存儲(chǔ)指算法執(zhí)行過(guò)程中所需的最大

存儲(chǔ)空間。

7、了解時(shí)間復(fù)雜度的概念、時(shí)間復(fù)雜度的度量、時(shí)間復(fù)雜度的類型，能對(duì)實(shí)際的程

序分析它的時(shí)間復(fù)雜度。

算法的時(shí)間復(fù)雜度是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度。

把算法中包含簡(jiǎn)單操作次數(shù)的多少叫做該算法的時(shí)間復(fù)雜度，或者叫做時(shí)間復(fù)雜性,

用它來(lái)衡量一個(gè)算法的運(yùn)行時(shí)間性能或稱計(jì)算性能

平均復(fù)雜度(TheAverageCase)：所有可能輸入.數(shù)據(jù)集的期望值.

最壞情況復(fù)雜度(TheWorstCase)：估算最壞情況下時(shí)間復(fù)雜度的一個(gè)上

界.這也是通常所指的復(fù)雜度.

最好復(fù)雜度(TheBestCase):在最理想輸入情況下的時(shí)間復(fù)雜度。

第二章線性表

1、了解并掌握線性表的定義及性質(zhì)

線性表是線性結(jié)構(gòu)的一種表現(xiàn)形式，即是具有相同屬性數(shù)據(jù)元素的一個(gè)有限序列，

序列中的元素是一個(gè)接一個(gè)在邏輯上是有序的，序列中元素的個(gè)數(shù)就是該線性表的

長(zhǎng)度.

存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素

存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素

除起點(diǎn)元素之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)

除終點(diǎn)元素之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼

起點(diǎn)元素只有后繼沒(méi)有前驅(qū)，終點(diǎn)元素只有前驅(qū)沒(méi)有后繼

。對(duì)于線性表中的數(shù)據(jù)元素和4來(lái)說(shuō)，&一/是&的直接前驅(qū)，a是a-的直接

后繼。

精心整理

?：?所有數(shù)據(jù)元素a在同一個(gè)線性表中必須是相同的數(shù)據(jù)類型。

2、熟悉順序線性表（順序存儲(chǔ)的線性表）的存儲(chǔ)方式及其表單元（簡(jiǎn)單數(shù)據(jù)類型和

記錄數(shù)據(jù)類型）的定位和計(jì)算。

線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)

據(jù)元素。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：

（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；

（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的，即前驅(qū)元素一定

存儲(chǔ)在后繼元素的前面。

3、熟悉順序線性表的插入、刪除和查找的算法思想和程序

4、了解線性表鏈接存儲(chǔ)的結(jié)構(gòu)和特點(diǎn)

假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存

儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。

在鏈?zhǔn)酱鎯?chǔ)方式中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值,

稱為數(shù)據(jù)域（或稱為信息域）；另一部分用于存放指針，稱為指針域。其中指

針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)，從而可以表示數(shù)據(jù)元素之間的邏輯

關(guān)系。

長(zhǎng)度可以任意擴(kuò)充，存儲(chǔ)效率較高；

物理存儲(chǔ)可以是不連續(xù)的；

數(shù)據(jù)元素的邏輯次序可以與其存儲(chǔ)的物理次序不一致。

插入、刪除運(yùn)算靈活方便，不需移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可

5、了解單鏈表、雙向鏈表和循環(huán)鏈表的結(jié)構(gòu)和特點(diǎn)

通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的結(jié)點(diǎn)序列我們就稱為

鏈表。如果這一鏈表中每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，則稱該鏈表為線性鏈表或單鏈表,

否則則稱為雙向鏈表。

雙向鏈表是指線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，用以指向其

直接前驅(qū)；另一個(gè)稱為右指針，用以指向其直接后繼。

循環(huán)鏈表。循環(huán)鏈表和單鏈表的差別僅在于鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不為

“NULL”,而是指向頭一個(gè)結(jié)點(diǎn)，成為一個(gè)由鏈指針鏈結(jié)的環(huán)。循環(huán)鏈表的特點(diǎn)：

只要知道表中任何一個(gè)結(jié)點(diǎn)的地址，就能查詢到表中的任何一個(gè)結(jié)點(diǎn)。

6、了解單鏈表的結(jié)點(diǎn)的類型定義

在程序中，L為單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)。若L為“空"（L=NULL）,

則所表示的線性表為“空”表，其長(zhǎng)度為“零”。除了線性表第一個(gè)數(shù)據(jù)元素作為

該鏈表的頭結(jié)點(diǎn)外，在某些線性鏈表存儲(chǔ)結(jié)構(gòu)中，還可在單鏈表第一個(gè)結(jié)點(diǎn)之前附

加一個(gè)同結(jié)構(gòu)結(jié)點(diǎn)，稱為附加頭結(jié)點(diǎn)。頭結(jié)點(diǎn)數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以

存儲(chǔ)如線性表的長(zhǎng)度等類的附加信息；頭結(jié)點(diǎn)指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針（即

第一個(gè)元素的存儲(chǔ)位置）。那么，指向頭結(jié)點(diǎn)的指針就是頭指針。當(dāng)頭結(jié)點(diǎn)的指針域

為“空”時(shí)，單鏈表為空鏈表

8、熟悉單鏈表中結(jié)點(diǎn)的定位、插入、刪除、查詢的算法思想和操作程序

9、了解線性表的順序與鏈?zhǔn)酱鎯?chǔ)各自的優(yōu)點(diǎn)、不足與它們適用場(chǎng)合。

若線性表的操作主要是查找和讀取時(shí)，采用順序存儲(chǔ)結(jié)構(gòu)為宜；若線性表的操作主

要是插入和刪除時(shí)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。

10、了解線性表的順序與鏈?zhǔn)酱鎯?chǔ)在不同操作場(chǎng)合下的時(shí)間復(fù)雜度指標(biāo)

順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)，表中任一數(shù)據(jù)元素都可以通過(guò)計(jì)算直接得到地址進(jìn)行存取,

時(shí)間復(fù)雜度為0（1）。在順序表中進(jìn)行插入和刪除數(shù)據(jù)元素時(shí)，平均要移動(dòng)近一半的

精心整理

元素，尤其是當(dāng)每個(gè)數(shù)據(jù)元素包含的信息量較大時(shí)，移動(dòng)元素所花費(fèi)的時(shí)間就相當(dāng)

可觀。

動(dòng)態(tài)鏈表是順序存儲(chǔ)結(jié)構(gòu)，表中的任一結(jié)點(diǎn)都需要從頭指針起順鏈掃描才能取得，

時(shí)間復(fù)雜度為。（力（〃為表長(zhǎng)）。但在動(dòng)態(tài)鏈表中進(jìn)行插入和刪除結(jié)點(diǎn)時(shí)，不需要移

動(dòng)結(jié)點(diǎn)，只需要修改指針。

第四章棧和隊(duì)列

1、了解棧的定義及性質(zhì)

棧（stack）又稱堆棧，它是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)

行插入和刪除運(yùn)算。

2、能給出在特定要求下的進(jìn)出棧序列以及判斷某些出棧序列出現(xiàn)的可能性

3、了解棧的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，棧頂指針的設(shè)置

4、了解棧的鏈接存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)、棧頂指針的更改

5、熟悉棧在順序和鏈接存儲(chǔ)結(jié)構(gòu)下的進(jìn)棧、出棧和讀取棧頂元素的操作程序

6、了解遞歸算法的特點(diǎn)及遞歸算法的中止條件，會(huì)結(jié)合具體程序來(lái)分析遞歸程序的

合理性

7、了解隊(duì)列的定義和它的順序存儲(chǔ)結(jié)構(gòu)

隊(duì)列（queue）簡(jiǎn)稱隊(duì)，它也是一種運(yùn)算受限的線性表，其限制是僅允許在表

的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。

我們把進(jìn)行插入的一端稱作隊(duì)尾（rear）,進(jìn)行刪除的一端稱作隊(duì)首（front）。

向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從

隊(duì)列中刪除元素稱為離隊(duì)或出隊(duì)，元素離隊(duì)后，其后繼元素就成為隊(duì)首元素。

由于隊(duì)列的插入和刪除操作分別是在各自的一端進(jìn)行的，每個(gè)元素必然按照進(jìn)

入的次序離隊(duì)，所以又把隊(duì)列稱為先進(jìn)先出表(firstinfirstout,簡(jiǎn)稱

FIFO)o

8、了解隊(duì)列特別是循環(huán)隊(duì)列情況下，隊(duì)列頭指針和尾指針的設(shè)置

9、了解隊(duì)列出現(xiàn)“假溢出”現(xiàn)象的原因及解決辦法：循環(huán)隊(duì)列的實(shí)現(xiàn)(循環(huán)頭指針

和尾指針的計(jì)算、循環(huán)(和普通)隊(duì)列長(zhǎng)度的計(jì)算以及循環(huán)隊(duì)列為空和滿的判斷方

法)

第五章樹(shù)和二叉樹(shù)

1、了解樹(shù)的定義和樹(shù)的基本術(shù)語(yǔ)：樹(shù)和結(jié)點(diǎn)的度、分支結(jié)點(diǎn)和葉子結(jié)點(diǎn)、父母結(jié)點(diǎn)

和孩子結(jié)點(diǎn)、結(jié)點(diǎn)的層數(shù)和樹(shù)的深度、有序樹(shù)和無(wú)序樹(shù)等

在樹(shù)形表示法中，結(jié)點(diǎn)之間的關(guān)系是通過(guò)連線表示的，雖然每條連線上都不帶有箭

頭(即方向)，但它并不是無(wú)向的，而是有向的，其方向隱含為從上向下或從左向右,

即連線的上方或左邊結(jié)點(diǎn)是下方或右邊結(jié)點(diǎn)的前驅(qū)，下方或右邊結(jié)點(diǎn)是上方或左邊

結(jié)點(diǎn)的后繼。

。結(jié)點(diǎn)的度：樹(shù)中每個(gè)結(jié)點(diǎn)具有的非空子樹(shù)數(shù)或者說(shuō)后繼結(jié)點(diǎn)數(shù)被定義為該結(jié)點(diǎn)

的度(degree)。

。樹(shù)的度：一棵樹(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)(child)：某結(jié)點(diǎn)子樹(shù)的根或者說(shuō)某個(gè)結(jié)點(diǎn)的后繼被稱為該結(jié)點(diǎn)的孩

子結(jié)點(diǎn)。

雙親結(jié)點(diǎn)(parent)：一個(gè)結(jié)點(diǎn)是它的那些子樹(shù)的根的雙親結(jié)點(diǎn)。

。兄弟結(jié)點(diǎn)(sibling)：同一個(gè)雙親的孩子之間互為兄弟。

精心整理

?：?堂兄弟結(jié)點(diǎn)(cousins)：其雙親在同一層但不同的結(jié)點(diǎn)互為堂兄弟。

子孫結(jié)點(diǎn)：每個(gè)結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)被稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)

祖先結(jié)點(diǎn)：從整個(gè)(子)樹(shù)的根結(jié)點(diǎn)到達(dá)該結(jié)點(diǎn)的路徑上經(jīng)過(guò)的所有分支結(jié)點(diǎn)

。結(jié)點(diǎn)層次:從根結(jié)點(diǎn)開(kāi)始，根結(jié)點(diǎn)為第1層，根結(jié)點(diǎn)的孩子為第2層，依此

類推

1A.............第1層

2B3C4D….第2層

5E6FG7……...第3層

樹(shù)的深度:樹(shù)中結(jié)點(diǎn)的最大層次。

有序樹(shù)：結(jié)點(diǎn)的子樹(shù)從左到右有序安排。也即樹(shù)T中各子樹(shù)「，丁2,…，■的相對(duì)次

序是有意義的。在有序樹(shù)中，改變了子樹(shù)的相對(duì)次序就變成了另一棵樹(shù)。

無(wú)序樹(shù)：結(jié)點(diǎn)的子樹(shù)順序任意。

2、熟悉樹(shù)的性質(zhì)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)推理和計(jì)算

。性質(zhì)1:樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。基

證明：根據(jù)定義：除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有一個(gè)分支指向。樹(shù)的總分支數(shù)為：

。性質(zhì)2：度為4的樹(shù)中第］.層上至多有個(gè)結(jié)點(diǎn)(7^1)o

用數(shù)學(xué)歸納法證明：

對(duì)于7=1,""=火=1命題成立。

假設(shè)第A1層(7>1)命題成立，該層上有『個(gè)結(jié)點(diǎn)。

對(duì)于第2.層，最多結(jié)點(diǎn)數(shù)稱?公產(chǎn)命題得證。

。性質(zhì)3深度為h的k叉樹(shù)金窘有個(gè)結(jié)點(diǎn)。

證明：利用性質(zhì)2來(lái)證明，k叉樹(shù)的最大結(jié)點(diǎn)數(shù)為每一層最大結(jié)點(diǎn)數(shù)之和，則

有:

當(dāng)一棵4叉樹(shù)上的結(jié)點(diǎn)數(shù)等于時(shí)，則稱該樹(shù)為滿女叉樹(shù)。

。性質(zhì)4：具有〃個(gè)結(jié)點(diǎn)的A叉樹(shù)的最小深度為：

分析：在結(jié)點(diǎn)數(shù)相同的k叉樹(shù)中，每一層結(jié)點(diǎn)都滿，或除最后一層外其余層都滿的

樹(shù)，其深度為最小。

h

證明：設(shè)k叉樹(shù)的最小深度為h,貝)：尸-1<nvk-l

k-1~k-\

前hT層滿的k叉樹(shù)結(jié)點(diǎn)數(shù)〈nWh層都滿的k叉樹(shù)結(jié)點(diǎn)數(shù)，因此有：

上式可變換為：<n(k-l)+lW片

以〃為底取對(duì)數(shù)可得：h-l<logk(n(k-l)+1)Wh

即：logk(n(k-l)+1)Wh<logk(n(k-l)+1)+1

因〃只能為整數(shù)，所以：h=?logk(n(k-l)+l)?

因此得到具有n個(gè)結(jié)點(diǎn)的一般k叉樹(shù)的最小深度為：21陽(yáng)(n(kT)+l)?

注：?x?表示對(duì)x進(jìn)行向上取整

3、熟悉二叉樹(shù)的定義及基本性質(zhì)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)推理和計(jì)算。

二叉樹(shù)(binarytree)是指樹(shù)的度為2的有序樹(shù)。它是一種樹(shù)結(jié)構(gòu)，在計(jì)算機(jī)領(lǐng)

域有著廣泛地應(yīng)用。

二叉樹(shù)的遞歸定義為：二叉樹(shù)或者是一棵空樹(shù)，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩

棵互不相交的分別稱做根的左子樹(shù)和右子樹(shù)所組成的非空樹(shù)，左子樹(shù)和右子樹(shù)

又同樣都是一棵二叉樹(shù)。

?:?性質(zhì)1：在二叉樹(shù)第i層上最多有個(gè)結(jié)點(diǎn)(i21)。

性質(zhì)2：深度為k的二叉樹(shù)，最多有2、1個(gè)結(jié)點(diǎn)(k21)。

性質(zhì)3：若二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為n。，度為2的結(jié)點(diǎn)有出個(gè)，則有：no=n2+l

精心整理

證明：(1)??由于在二叉樹(shù)中，任一結(jié)點(diǎn)的度數(shù)小于或等于2,所以其結(jié)點(diǎn)總

數(shù)n為：

n=n0+Hi+n2

(n°:終端結(jié)點(diǎn)；m:單分支結(jié)點(diǎn)數(shù)，%:雙分支結(jié)點(diǎn)數(shù))

(2)設(shè)B為二叉樹(shù)中總的分支數(shù)目，由于二叉樹(shù)中除了根結(jié)點(diǎn)之外，其余結(jié)

點(diǎn)都有一個(gè)分支進(jìn)入,而這些分支只能是由度數(shù)為1或2的結(jié)點(diǎn)所發(fā)出，所以：

B=a+2n2

于是得：n=ri,+2n2+1

(3)由⑴和⑵得：

n0+ni+n2=n,+2n2+1

所以n0=n2+1#證畢

性質(zhì)4：對(duì)完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)(lWiWn,n21,n為結(jié)點(diǎn)數(shù))有：

(1)若iW?n/2?,即2iWn,則編號(hào)為i的結(jié)點(diǎn)為分支結(jié)點(diǎn)，否則為葉子結(jié)點(diǎn)。

表達(dá)式?x?表示對(duì)x進(jìn)行向下取整。

(2)若n為奇數(shù)，則樹(shù)中每個(gè)分支結(jié)點(diǎn)都既有左孩子，又有右孩子；若n為偶

數(shù)，則編號(hào)最大的分支結(jié)點(diǎn)(編號(hào)為n/2)只有左孩子，沒(méi)有右孩子，其余分支結(jié)點(diǎn)

左、右孩子都有。

(3)若編號(hào)為i的結(jié)點(diǎn)有左孩子，則左孩子結(jié)點(diǎn)的編號(hào)為2i；若編號(hào)為i的結(jié)

點(diǎn)有右孩子，則右孩子結(jié)點(diǎn)的編號(hào)為2i+l,即遵循對(duì)一般二叉樹(shù)的編號(hào)規(guī)則。

(4)除樹(shù)根結(jié)點(diǎn)外，若一個(gè)結(jié)點(diǎn)的編號(hào)為i,則它的雙親結(jié)點(diǎn)的編號(hào)為?n/2?,

也就是說(shuō)，當(dāng)i為偶數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為i/2,它是雙親結(jié)點(diǎn)的左孩子，當(dāng)i

為奇數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為(iT)/2,它是雙親結(jié)點(diǎn)的右孩子。此點(diǎn)也適合于一

般二叉樹(shù)。

性質(zhì)5：具有n個(gè)(n>0)結(jié)點(diǎn)的完全二叉樹(shù)的深度為?log2(n+l)?或?logzn?+l。

此性質(zhì)可以從樹(shù)的相應(yīng)性質(zhì)中直接導(dǎo)出，也可以進(jìn)行如下證明。

證明：設(shè)所求完全二叉樹(shù)的深度為h,由完全二叉樹(shù)的定義可知，它的前

hT層都是滿的，最后一層可以滿，也可以不滿，由此得到的如下不等式

2hl-l<n^2h-l.

可變換為：2i〈n+lW2h

取對(duì)數(shù)后得：h-l<log2(n+l)Wh

即：log2(n+l)^h<log2(n+l)+1

因h只能取整數(shù)，所以：h=?log2(n+l)?

完全二叉樹(shù)的深度h和結(jié)點(diǎn)數(shù)n的關(guān)系，還可表示為：

2,ll^n<2h

取對(duì)數(shù)后得：hTWlog2n<h

即：log2n<h^log2n+l

因h只能取整數(shù)，所以：h=?log2n?+l

4、熟悉滿二叉樹(shù)、完全二叉樹(shù)以及平衡二叉樹(shù)等幾種特殊的二叉樹(shù)的性質(zhì)、特點(diǎn)，

并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)的推理和計(jì)算

滿二叉樹(shù):叉樹(shù)每層的結(jié)點(diǎn)數(shù)達(dá)到最大值。

第i層有個(gè)結(jié)點(diǎn)；全部分支結(jié)點(diǎn)度為2。

完全二叉樹(shù)：除最后一層外，其余層均滿；最后層或?yàn)闈M，或缺少右邊若干連續(xù)結(jié)

點(diǎn)。

特點(diǎn)：

除最后一層，第i層有個(gè)結(jié)點(diǎn);

葉子只可能出現(xiàn)在最后兩層；

精心整理

?：?結(jié)點(diǎn)右子樹(shù)深度為i時(shí)，左子樹(shù)深度為i或i+L

理想平衡二叉樹(shù)：在一棵二叉樹(shù)中，若除最后一層外，其余層都是滿的，而最后一

層上的結(jié)點(diǎn)可以任意分布，則稱此樹(shù)為理想平衡二叉樹(shù),簡(jiǎn)稱理想平衡樹(shù)或理想二叉

樹(shù)。

顯然，理想平衡樹(shù)包含滿二叉樹(shù)和完全二叉樹(shù)。完全二叉樹(shù)中深度

h和結(jié)點(diǎn)數(shù)n之間的關(guān)系，在理想平衡樹(shù)中同樣成立，

5、了解二叉樹(shù)的鏈接存儲(chǔ)結(jié)構(gòu)

根據(jù)二叉樹(shù)的特性，任何一個(gè)結(jié)點(diǎn)最多有左、右兩棵子樹(shù)，所以每個(gè)結(jié)點(diǎn)至少設(shè)有

三個(gè)域：數(shù)據(jù)域和左、右指針域。其結(jié)點(diǎn)結(jié)構(gòu)為：

Leftdataright

其中data表示值域，用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素，left和right分別表示左指針域和

右指針域，用以分別存儲(chǔ)左孩子和右孩子結(jié)點(diǎn)的存貯位置（即指針）

鏈接存儲(chǔ)的另一種方法是：在上面的結(jié)點(diǎn)結(jié)構(gòu)中再增加一個(gè)parent指針域，

用來(lái)指向其雙親結(jié)點(diǎn)。這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，也便于查找雙親結(jié)

點(diǎn)，當(dāng)然也帶來(lái)存儲(chǔ)空間的相應(yīng)增加。

Ichilddataparentrchild

6、瓦蘇二支樹(shù)的4遍遍歷方俁？能轉(zhuǎn)存后二再扇^方展碼出融樹(shù)的遍歷序列

（1）先序遍歷：

若二叉樹(shù)為空，則空操作；否則

①訪問(wèn)根結(jié)點(diǎn)；

②先序遍歷左子樹(shù)；

（先訪問(wèn)左子樹(shù)根節(jié)點(diǎn)；再遍歷左子樹(shù)根節(jié)點(diǎn)的左子樹(shù)，再遍歷左子樹(shù)根

節(jié)點(diǎn)的右子樹(shù)；……直至遍歷完所有左子樹(shù)的節(jié)點(diǎn)｝

③先序遍歷右子樹(shù)。

（先訪問(wèn)右子樹(shù)根節(jié)點(diǎn)；再遍歷右子樹(shù)根節(jié)點(diǎn)的左子樹(shù)，再遍歷右子樹(shù)根

節(jié)點(diǎn)的右子樹(shù)；……直至遍歷完所有右子樹(shù)的節(jié)點(diǎn)｝

（2）中序遍歷：

若二叉樹(shù)為空，則空操作；否則

①中序遍歷左子樹(shù)；

（遍歷的過(guò)程與先根級(jí)的遞歸遍歷類似）

②訪問(wèn)根結(jié)點(diǎn)；

③中序遍歷右子樹(shù)

（遍歷過(guò)程與先根級(jí)的遞歸遍歷相同）

（3）后序遍歷：

若二叉樹(shù)為空，則空操作；否則

①后序遍歷左子樹(shù)；

②后序遍歷右子樹(shù)。

③訪問(wèn)根結(jié)點(diǎn)；

（4）按層遍歷二叉樹(shù)：

①訪問(wèn)根結(jié)點(diǎn)；

②遍歷左子樹(shù)根結(jié)點(diǎn)；

③遍歷右子樹(shù)根結(jié)點(diǎn)。

6、熟悉樹(shù)的遍歷序列與樹(shù)結(jié)構(gòu)之間的關(guān)系，并能由特定的遍歷序列來(lái)恢復(fù)樹(shù)結(jié)構(gòu)和

寫(xiě)出另外的遍歷序列

7、熟悉樹(shù)與二叉樹(shù)的共性和差異之處

8、熟悉樹(shù)的幾種遍歷算法

精心整理

9、能根據(jù)樹(shù)的定義(包括結(jié)點(diǎn)類型的定義)編程實(shí)現(xiàn)樹(shù)的一些基本運(yùn)算

第六章二叉樹(shù)的應(yīng)用

1、了解二叉搜索樹(shù)的定義，性質(zhì)并能根據(jù)定義由給定序列構(gòu)造二叉搜索樹(shù)

二叉搜索樹(shù)(BinanySearchingTree)又稱做二叉排序樹(shù)(BinarySorting

Tree),它或者是一棵空樹(shù)，或者是一棵具有如下特性的非空二叉樹(shù)。

(1)若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均小于樹(shù)根結(jié)點(diǎn)的關(guān)鍵字;

(2)若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均大于樹(shù)根結(jié)點(diǎn)的關(guān)鍵字;

(3)左、右子樹(shù)本身又各是一棵二叉搜索樹(shù)。

在一個(gè)二叉搜索樹(shù)中，當(dāng)每個(gè)結(jié)點(diǎn)的元素類型為簡(jiǎn)單類型時(shí)，則結(jié)點(diǎn)的關(guān)鍵

字就為該結(jié)點(diǎn)的值；當(dāng)結(jié)點(diǎn)的元素類型為記錄類型時(shí)，則結(jié)點(diǎn)的關(guān)鍵字為該結(jié)點(diǎn)的

某一個(gè)域的值。

。由二叉搜索樹(shù)的定義可知，在一棵非空的二叉搜索樹(shù)中，其結(jié)點(diǎn)的關(guān)鍵字是按

照左子樹(shù)、根和右子樹(shù)有序的，所以對(duì)它進(jìn)行中序遍歷得到的結(jié)點(diǎn)序列必然是

一個(gè)有序序列。

2、了解二叉搜索樹(shù)應(yīng)用于查找時(shí)的特性及指標(biāo)

在二叉搜索樹(shù)上進(jìn)行查找的過(guò)程中，給定值item同樹(shù)中結(jié)點(diǎn)比較的次數(shù)最少

為一次(即樹(shù)根結(jié)點(diǎn)就是待查的結(jié)點(diǎn))，最多為樹(shù)的深度，所以平均查找次數(shù)

要小于等于樹(shù)的深度。

若二叉搜索樹(shù)是一棵理想平衡樹(shù)或接近理想平衡樹(shù)，則進(jìn)行查找的時(shí)間復(fù)雜度

為0(log2n),

若為一棵單支樹(shù)(這是最極端和最差的情況)，則其時(shí)間復(fù)雜度為0(n),

一般情況而言，其時(shí)間復(fù)雜度可大致可看做為O(logzn)。

由此可知，在二叉搜索樹(shù)上查找比在集合或線性表上進(jìn)行順序查找的

時(shí)間復(fù)雜度0(n)要小得多，這正是構(gòu)造二叉搜索樹(shù)的優(yōu)勢(shì)所在。二叉搜索樹(shù)查找的

遞歸算法的空間復(fù)雜度平均情況為O(logzn),最差情況為。(n),非遞歸算法的空間

復(fù)雜度為0(1)。

3、了解堆的定義和性質(zhì)

堆(Heap)分為小根堆和大根堆兩種，對(duì)于一個(gè)小根堆，它是具有如下特性的一棵完

全二叉樹(shù)。

(1)若樹(shù)根結(jié)點(diǎn)存在左孩子，則樹(shù)根結(jié)點(diǎn)的值小于等于左孩子結(jié)點(diǎn)的值；

(2)若樹(shù)根結(jié)點(diǎn)存在右孩子，則樹(shù)根結(jié)點(diǎn)的值小于等于右孩子結(jié)點(diǎn)的值；

(3)以左、右孩子為根的子樹(shù)又同樣各是一個(gè)堆。

大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。

若一棵完全二叉樹(shù)是堆，則該樹(shù)中以每個(gè)結(jié)點(diǎn)為根的子樹(shù)也都是一個(gè)堆。

堆頂結(jié)點(diǎn)具有最小值(一一對(duì)應(yīng)于小根堆)或最大值(一一對(duì)應(yīng)于大根堆)。

4、能采用給定的數(shù)據(jù)序列來(lái)生成一個(gè)堆(大根堆或小根堆)

5、了解樹(shù)的帶權(quán)路徑，以及哈夫曼樹(shù)(最優(yōu)二叉樹(shù))的概念和性質(zhì)

(1)路徑和路徑長(zhǎng)度

若在一棵樹(shù)中存在著一個(gè)結(jié)點(diǎn)序列k1,k2,…,kj,使得ki是ki+1的雙親(lWi〈j),則稱

此結(jié)點(diǎn)序列是從k1到kj的路徑。也就是說(shuō)，在二叉樹(shù)中，一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之

間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。因樹(shù)中每個(gè)結(jié)點(diǎn)只有一個(gè)雙親結(jié)點(diǎn)，所以它

也是這兩個(gè)結(jié)點(diǎn)之間的惟一路徑。從X到kj所經(jīng)過(guò)的分支數(shù)稱為這兩點(diǎn)之間的路徑

長(zhǎng)度，它等于路徑上的結(jié)點(diǎn)數(shù)減1。

(2)結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度

精心整理

在許多應(yīng)用中，常常將樹(shù)中的結(jié)點(diǎn)賦予一個(gè)有著某種意義的實(shí)數(shù)，我們

稱此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度規(guī)定為從樹(shù)根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路

徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積。

(3)樹(shù)的帶權(quán)路徑長(zhǎng)度

樹(shù)的帶權(quán)路徑長(zhǎng)度定義為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為：

其中n表示葉子結(jié)點(diǎn)的數(shù)目，%和心分別表示葉子結(jié)點(diǎn)k.的權(quán)值和樹(shù)根結(jié)點(diǎn)到ki之

間的路徑長(zhǎng)度。

。哈夫曼(Huffman)樹(shù)又稱作最優(yōu)二叉樹(shù)。它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二

叉樹(shù)中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)。

6、能根據(jù)給定的權(quán)值集合和結(jié)點(diǎn)集合構(gòu)成具有n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)

(1)根據(jù)與〃個(gè)權(quán)值｛仍,W2,…,％｝對(duì)應(yīng)的〃個(gè)結(jié)點(diǎn)構(gòu)成具有77棵二叉樹(shù)的森林

￡=｛「，心,…,北｝,其中每棵二叉樹(shù)T,(lW?Wn)都只有一個(gè)權(quán)值為叼的根結(jié)點(diǎn)，其左、

右子樹(shù)均為空；

(2)在森林尸中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為一棵新樹(shù)的左、右子樹(shù)，且

置新樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和；

(3)從月中刪除構(gòu)成新樹(shù)的那兩棵樹(shù)，同時(shí)把新樹(shù)加入月中；

(4)重復(fù)(2)和(3)步，直到尸中只含有一棵樹(shù)為止，此樹(shù)便是哈夫曼樹(shù)

第七章圖

1、了解圖的定義以及基本性質(zhì)

圖中的每個(gè)頂點(diǎn)，都允許有任意個(gè)前驅(qū)和后繼，即對(duì)每個(gè)頂點(diǎn)的前驅(qū)和后繼個(gè)

數(shù)均不加以限制

?：?對(duì)于一個(gè)圖G,若E是有序?qū)Φ募?，則每個(gè)有序?qū)?duì)應(yīng)圖形中的一條有向邊,

若E是無(wú)序?qū)Φ募?，則每個(gè)無(wú)序?qū)?duì)應(yīng)圖形中的一條無(wú)向邊，所以可把E看

做為邊的集合。這樣圖的二元組定義可敘述為：圖由頂點(diǎn)集(vertexset)和

邊集(edgeset)所組成。

針對(duì)圖G,頂點(diǎn)集和邊集可分別記為V(G)和E(G)。若頂點(diǎn)集為空，則邊集必然為空,

若頂點(diǎn)集非空，則邊集可空可不空，當(dāng)邊集為空時(shí)，圖G中的頂點(diǎn)均為孤立頂點(diǎn)。

2、了解圖的鄰接矩陣、鄰接表、逆鄰接表和十字鄰接表的定義及性質(zhì)

鄰接矩陣(adjacencymatrix)是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)

是具有n個(gè)頂點(diǎn)的圖，頂點(diǎn)序號(hào)依次為0,1,2,…,nT,則G的鄰接矩陣是具有如下

定義的n階方陣。

?1,對(duì)于無(wú)向圖，(匕，匕)或(%匕)?E(G)；

力"力=?對(duì)于有向圖，〈匕，r??E(G)

?0,對(duì)應(yīng)邊不存在于E(G)中

從鄰接矩陣中可查兩個(gè)結(jié)點(diǎn)的之間是否存在通路，若兩個(gè)結(jié)點(diǎn)的坐標(biāo)的交叉其

值不為零并不是一個(gè)很大的值的話，則有通路，否則沒(méi)有通路。若其值大于1

則為該通路的權(quán)值。

無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣可能是不對(duì)稱的。

在有向圖中，統(tǒng)計(jì)第7.行中1的個(gè)數(shù)可得頂點(diǎn)i的出度，統(tǒng)計(jì)第j列中1

的個(gè)數(shù)可得頂點(diǎn)j的入度。

在無(wú)向圖中，統(tǒng)計(jì)第i行(列)中1的個(gè)數(shù)可得頂點(diǎn)i的度。

圖的鄰接矩陣的存儲(chǔ)需要占用〃X〃個(gè)整數(shù)存儲(chǔ)位置，所以其空間復(fù)雜度為

0(ri)o

精心整理