西安交通大學數(shù)據(jù)結構復習資料

精心整理

第一章緒論

1、數(shù)據(jù)結構的主要研究內(nèi)容

①數(shù)據(jù)的邏輯結構一數(shù)據(jù)關系之間的邏輯關系

②數(shù)據(jù)的存儲結構一數(shù)據(jù)的邏輯結構在計算機中的表示

2、數(shù)據(jù)邏輯結構的種類：集合、線性表、樹和圖的性質(zhì)和特點。

。集合結構中的元素是各自獨立的，元素之間沒有聯(lián)系

線性結構中的元素是一個接一個串聯(lián)起來的，它有一個頭元素和一個尾元素，

其余為中間元素；每個中間元素既有前驅元素，又有后繼元素

在樹結構中，樹根結點只有后繼結點，而沒有前驅結點；除樹根結點外，每個

結點都有唯---個前驅結點，又稱為是父結點或雙親結點

在圖結構中，每個結點或稱頂點都可以有任意多個前驅結點和任意多個后繼結

點。

。樹結構是圖結構的特例，線性結構是樹結構的特例。為了區(qū)別于線性結構，時

常把樹結構和圖結構稱為非線性結構。

3、數(shù)據(jù)結構的二元組定義，能根據(jù)給出的二元組來判斷數(shù)據(jù)的邏輯結構類型。

。集合結構中的元素集合K和二元關系R分別為：

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

R={}

線性結構中的元素集合K和二元關系R分別為：

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

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

精心整理

。樹結構中的元素集合K和二元關系R分別為：

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

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

圖結構中的元素集合K和二元關系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ù)的幾種存儲結構（物理結構）及它們各自的性質(zhì)和特點。

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

的數(shù)據(jù)結構.

（2）鏈式結構：給結點附加一個指針字段，指出其后繼節(jié)點的位置，即存放結點的

存儲單元分為兩部分：

數(shù)據(jù)項指針項

（3）散列（hashing）結構：散列的方法是用結點的關鍵字值直接計算出結點的存

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

5、數(shù)據(jù)的邏輯結構、存儲結構和總的數(shù)據(jù)結構之間的關系

邏輯結構相同，但存儲結構不同，則認為是不同的數(shù)據(jù)結構。如順序表和鏈

表具有相同的邏輯結構，但存儲結構分別為順序結構和鏈表結構

6、算法的設計要求有那些，會結合實際的語言設計來說明這些要求

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

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

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

3）健壯性：當輸入非法時，算法還能做出適當?shù)姆磻粫罎?，如輸出錯誤信

息；算法中應該考慮適當?shù)腻e誤處理；

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

存儲空間。

7、了解時間復雜度的概念、時間復雜度的度量、時間復雜度的類型，能對實際的程

序分析它的時間復雜度。

算法的時間復雜度是一個算法運行時間的相對量度。

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

用它來衡量一個算法的運行時間性能或稱計算性能

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

最壞情況復雜度(TheWorstCase)：估算最壞情況下時間復雜度的一個上

界.這也是通常所指的復雜度.

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

第二章線性表

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

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

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

長度.

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

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

除起點元素之外，集合中的每個數(shù)據(jù)元素均只有一個前驅

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

起點元素只有后繼沒有前驅，終點元素只有前驅沒有后繼

。對于線性表中的數(shù)據(jù)元素和4來說，&一/是&的直接前驅，a是a-的直接

后繼。

精心整理

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

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

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

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

據(jù)元素。線性表的順序存儲結構具有以下兩個基本特點：

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

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

存儲在后繼元素的前面。

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

4、了解線性表鏈接存儲的結構和特點

假設數(shù)據(jù)結構中的每一個數(shù)據(jù)結點對應于一個存儲單元，這種存儲單元稱為存

儲結點，簡稱結點。

在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用于存放數(shù)據(jù)元素值,

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

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

關系。

長度可以任意擴充，存儲效率較高；

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

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

插入、刪除運算靈活方便，不需移動結點，只要改變結點中指針域的值即可

5、了解單鏈表、雙向鏈表和循環(huán)鏈表的結構和特點

通過每個結點的指針域將n個結點按其邏輯順序鏈接在一起的結點序列我們就稱為

鏈表。如果這一鏈表中每個結點只有一個指針域，則稱該鏈表為線性鏈表或單鏈表,

否則則稱為雙向鏈表。

雙向鏈表是指線性鏈表中的每個結點設置兩個指針，一個稱為左指針，用以指向其

直接前驅；另一個稱為右指針，用以指向其直接后繼。

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

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

只要知道表中任何一個結點的地址，就能查詢到表中的任何一個結點。

6、了解單鏈表的結點的類型定義

在程序中，L為單鏈表的頭指針，它指向表中第一個結點。若L為“空"（L=NULL）,

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

該鏈表的頭結點外，在某些線性鏈表存儲結構中，還可在單鏈表第一個結點之前附

加一個同結構結點，稱為附加頭結點。頭結點數(shù)據(jù)域可以不存儲任何信息，也可以

存儲如線性表的長度等類的附加信息；頭結點指針域存儲指向第一個結點的指針（即

第一個元素的存儲位置）。那么，指向頭結點的指針就是頭指針。當頭結點的指針域

為“空”時，單鏈表為空鏈表

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

9、了解線性表的順序與鏈式存儲各自的優(yōu)點、不足與它們適用場合。

若線性表的操作主要是查找和讀取時，采用順序存儲結構為宜；若線性表的操作主

要是插入和刪除時，采用鏈式存儲結構為宜。

10、了解線性表的順序與鏈式存儲在不同操作場合下的時間復雜度指標

順序表是隨機存儲結構，表中任一數(shù)據(jù)元素都可以通過計算直接得到地址進行存取,

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

精心整理

元素，尤其是當每個數(shù)據(jù)元素包含的信息量較大時，移動元素所花費的時間就相當

可觀。

動態(tài)鏈表是順序存儲結構，表中的任一結點都需要從頭指針起順鏈掃描才能取得，

時間復雜度為。（力（〃為表長）。但在動態(tài)鏈表中進行插入和刪除結點時，不需要移

動結點，只需要修改指針。

第四章棧和隊列

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

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

行插入和刪除運算。

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

3、了解棧的順序存儲結構實現(xiàn)，棧頂指針的設置

4、了解棧的鏈接存儲結構的實現(xiàn)、棧頂指針的更改

5、熟悉棧在順序和鏈接存儲結構下的進棧、出棧和讀取棧頂元素的操作程序

6、了解遞歸算法的特點及遞歸算法的中止條件，會結合具體程序來分析遞歸程序的

合理性

7、了解隊列的定義和它的順序存儲結構

隊列（queue）簡稱隊，它也是一種運算受限的線性表，其限制是僅允許在表

的一端進行插入，而在表的另一端進行刪除。

我們把進行插入的一端稱作隊尾（rear）,進行刪除的一端稱作隊首（front）。

向隊列中插入新元素稱為進隊或入隊，新元素進隊后就成為新的隊尾元素；從

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

由于隊列的插入和刪除操作分別是在各自的一端進行的，每個元素必然按照進

入的次序離隊，所以又把隊列稱為先進先出表(firstinfirstout,簡稱

FIFO)o

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

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

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

法)

第五章樹和二叉樹

1、了解樹的定義和樹的基本術語：樹和結點的度、分支結點和葉子結點、父母結點

和孩子結點、結點的層數(shù)和樹的深度、有序樹和無序樹等

在樹形表示法中，結點之間的關系是通過連線表示的，雖然每條連線上都不帶有箭

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

即連線的上方或左邊結點是下方或右邊結點的前驅，下方或右邊結點是上方或左邊

結點的后繼。

。結點的度：樹中每個結點具有的非空子樹數(shù)或者說后繼結點數(shù)被定義為該結點

的度(degree)。

。樹的度：一棵樹上所有結點的度的最大值就是這棵樹的度。

葉子結點：度為零的結點稱葉子結點或終端結點。

分支結點：度非零的結點稱為分支結點或稱為非終端結點。

?:?孩子結點(child)：某結點子樹的根或者說某個結點的后繼被稱為該結點的孩

子結點。

雙親結點(parent)：一個結點是它的那些子樹的根的雙親結點。

。兄弟結點(sibling)：同一個雙親的孩子之間互為兄弟。

精心整理

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

子孫結點：每個結點的所有子樹中的結點被稱為該結點的子孫結點

祖先結點：從整個(子)樹的根結點到達該結點的路徑上經(jīng)過的所有分支結點

。結點層次:從根結點開始，根結點為第1層，根結點的孩子為第2層，依此

類推

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

2B3C4D….第2層

5E6FG7……...第3層

樹的深度:樹中結點的最大層次。

有序樹：結點的子樹從左到右有序安排。也即樹T中各子樹「，丁2,…，■的相對次

序是有意義的。在有序樹中，改變了子樹的相對次序就變成了另一棵樹。

無序樹：結點的子樹順序任意。

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

。性質(zhì)1:樹中的結點數(shù)等于所有結點的度數(shù)加1?；?/p>

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

。性質(zhì)2：度為4的樹中第］.層上至多有個結點(7^1)o

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

對于7=1,""=火=1命題成立。

假設第A1層(7>1)命題成立，該層上有『個結點。

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

。性質(zhì)3深度為h的k叉樹金窘有個結點。

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

有:

當一棵4叉樹上的結點數(shù)等于時，則稱該樹為滿女叉樹。

。性質(zhì)4：具有〃個結點的A叉樹的最小深度為：

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

樹，其深度為最小。

h

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

k-1~k-\

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

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

以〃為底取對數(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個結點的一般k叉樹的最小深度為：21陽(n(kT)+l)?

注：?x?表示對x進行向上取整

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

二叉樹(binarytree)是指樹的度為2的有序樹。它是一種樹結構，在計算機領

域有著廣泛地應用。

二叉樹的遞歸定義為：二叉樹或者是一棵空樹，或者是一棵由一個根結點和兩

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

又同樣都是一棵二叉樹。

?:?性質(zhì)1：在二叉樹第i層上最多有個結點(i21)。

性質(zhì)2：深度為k的二叉樹，最多有2、1個結點(k21)。

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

精心整理

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

數(shù)n為：

n=n0+Hi+n2

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

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

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

B=a+2n2

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

(3)由⑴和⑵得：

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

所以n0=n2+1#證畢

性質(zhì)4：對完全二叉樹中編號為i的結點(lWiWn,n21,n為結點數(shù))有：

(1)若iW?n/2?,即2iWn,則編號為i的結點為分支結點，否則為葉子結點。

表達式?x?表示對x進行向下取整。

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

數(shù)，則編號最大的分支結點(編號為n/2)只有左孩子，沒有右孩子，其余分支結點

左、右孩子都有。

(3)若編號為i的結點有左孩子，則左孩子結點的編號為2i；若編號為i的結

點有右孩子，則右孩子結點的編號為2i+l,即遵循對一般二叉樹的編號規(guī)則。

(4)除樹根結點外，若一個結點的編號為i,則它的雙親結點的編號為?n/2?,

也就是說，當i為偶數(shù)時，其雙親結點的編號為i/2,它是雙親結點的左孩子，當i

為奇數(shù)時，其雙親結點的編號為(iT)/2,它是雙親結點的右孩子。此點也適合于一

般二叉樹。

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

此性質(zhì)可以從樹的相應性質(zhì)中直接導出，也可以進行如下證明。

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

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

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

可變換為：2i〈n+lW2h

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

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

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

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

2,ll^n<2h

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

即：log2n<h^log2n+l

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

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

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

滿二叉樹:叉樹每層的結點數(shù)達到最大值。

第i層有個結點；全部分支結點度為2。

完全二叉樹：除最后一層外，其余層均滿；最后層或為滿，或缺少右邊若干連續(xù)結

點。

特點：

除最后一層，第i層有個結點;

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

精心整理

?：?結點右子樹深度為i時，左子樹深度為i或i+L

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

層上的結點可以任意分布，則稱此樹為理想平衡二叉樹,簡稱理想平衡樹或理想二叉

樹。

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

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

5、了解二叉樹的鏈接存儲結構

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

三個域：數(shù)據(jù)域和左、右指針域。其結點結構為：

Leftdataright

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

右指針域，用以分別存儲左孩子和右孩子結點的存貯位置（即指針）

鏈接存儲的另一種方法是：在上面的結點結構中再增加一個parent指針域，

用來指向其雙親結點。這種存儲結構既便于查找孩子結點，也便于查找雙親結

點，當然也帶來存儲空間的相應增加。

Ichilddataparentrchild

6、瓦蘇二支樹的4遍遍歷方俁？能轉存后二再扇^方展碼出融樹的遍歷序列

（1）先序遍歷：

若二叉樹為空，則空操作；否則

①訪問根結點；

②先序遍歷左子樹；

（先訪問左子樹根節(jié)點；再遍歷左子樹根節(jié)點的左子樹，再遍歷左子樹根

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

③先序遍歷右子樹。

（先訪問右子樹根節(jié)點；再遍歷右子樹根節(jié)點的左子樹，再遍歷右子樹根

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

（2）中序遍歷：

若二叉樹為空，則空操作；否則

①中序遍歷左子樹；

（遍歷的過程與先根級的遞歸遍歷類似）

②訪問根結點；

③中序遍歷右子樹

（遍歷過程與先根級的遞歸遍歷相同）

（3）后序遍歷：

若二叉樹為空，則空操作；否則

①后序遍歷左子樹；

②后序遍歷右子樹。

③訪問根結點；

（4）按層遍歷二叉樹：

①訪問根結點；

②遍歷左子樹根結點；

③遍歷右子樹根結點。

6、熟悉樹的遍歷序列與樹結構之間的關系，并能由特定的遍歷序列來恢復樹結構和

寫出另外的遍歷序列

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

8、熟悉樹的幾種遍歷算法

精心整理

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

第六章二叉樹的應用

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

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

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

(1)若它的左子樹非空，則左子樹上所有結點的關鍵字均小于樹根結點的關鍵字;

(2)若它的右子樹非空，則右子樹上所有結點的關鍵字均大于樹根結點的關鍵字;

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

在一個二叉搜索樹中，當每個結點的元素類型為簡單類型時，則結點的關鍵

字就為該結點的值；當結點的元素類型為記錄類型時，則結點的關鍵字為該結點的

某一個域的值。

。由二叉搜索樹的定義可知，在一棵非空的二叉搜索樹中，其結點的關鍵字是按

照左子樹、根和右子樹有序的，所以對它進行中序遍歷得到的結點序列必然是

一個有序序列。

2、了解二叉搜索樹應用于查找時的特性及指標

在二叉搜索樹上進行查找的過程中，給定值item同樹中結點比較的次數(shù)最少

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

要小于等于樹的深度。

若二叉搜索樹是一棵理想平衡樹或接近理想平衡樹，則進行查找的時間復雜度

為0(log2n),

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

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

由此可知，在二叉搜索樹上查找比在集合或線性表上進行順序查找的

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

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

復雜度為0(1)。

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

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

全二叉樹。

(1)若樹根結點存在左孩子，則樹根結點的值小于等于左孩子結點的值；

(2)若樹根結點存在右孩子，則樹根結點的值小于等于右孩子結點的值；

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

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

若一棵完全二叉樹是堆，則該樹中以每個結點為根的子樹也都是一個堆。

堆頂結點具有最小值(一一對應于小根堆)或最大值(一一對應于大根堆)。

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

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

(1)路徑和路徑長度

若在一棵樹中存在著一個結點序列k1,k2,…,kj,使得ki是ki+1的雙親(lWi〈j),則稱

此結點序列是從k1到kj的路徑。也就是說，在二叉樹中，一個結點到另一個結點之

間的分支構成這兩個結點之間的路徑。因樹中每個結點只有一個雙親結點，所以它

也是這兩個結點之間的惟一路徑。從X到kj所經(jīng)過的分支數(shù)稱為這兩點之間的路徑

長度，它等于路徑上的結點數(shù)減1。

(2)結點的權和帶權路徑長度

精心整理

在許多應用中，常常將樹中的結點賦予一個有著某種意義的實數(shù)，我們

稱此實數(shù)為該結點的權。結點的帶權路徑長度規(guī)定為從樹根結點到該結點之間的路

徑長度與該結點上權的乘積。

(3)樹的帶權路徑長度

樹的帶權路徑長度定義為樹中所有葉子結點的帶權路徑長度之和，通常記為：

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

間的路徑長度。

。哈夫曼(Huffman)樹又稱作最優(yōu)二叉樹。它是n個帶權葉子結點構成的所有二

叉樹中，帶權路徑長度WPL最小的二叉樹。

6、能根據(jù)給定的權值集合和結點集合構成具有n個結點的哈夫曼樹

(1)根據(jù)與〃個權值｛仍,W2,…,％｝對應的〃個結點構成具有77棵二叉樹的森林

￡=｛「，心,…,北｝,其中每棵二叉樹T,(lW?Wn)都只有一個權值為叼的根結點，其左、

右子樹均為空；

(2)在森林尸中選出兩棵根結點的權值最小的樹作為一棵新樹的左、右子樹，且

置新樹的根結點的權值為其左、右子樹上根結點的權值之和；

(3)從月中刪除構成新樹的那兩棵樹，同時把新樹加入月中；

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

第七章圖

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

圖中的每個頂點，都允許有任意個前驅和后繼，即對每個頂點的前驅和后繼個

數(shù)均不加以限制

?：?對于一個圖G,若E是有序對的集合，則每個有序對對應圖形中的一條有向邊,

若E是無序對的集合，則每個無序對對應圖形中的一條無向邊，所以可把E看

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

邊集(edgeset)所組成。

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

若頂點集非空，則邊集可空可不空，當邊集為空時，圖G中的頂點均為孤立頂點。

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

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

是具有n個頂點的圖，頂點序號依次為0,1,2,…,nT,則G的鄰接矩陣是具有如下

定義的n階方陣。

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

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

?0,對應邊不存在于E(G)中

從鄰接矩陣中可查兩個結點的之間是否存在通路，若兩個結點的坐標的交叉其

值不為零并不是一個很大的值的話，則有通路，否則沒有通路。若其值大于1

則為該通路的權值。

無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的。

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

的個數(shù)可得頂點j的入度。

在無向圖中，統(tǒng)計第i行(列)中1的個數(shù)可得頂點i的度。

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

0(ri)o

精心整理