01 3.1數據結構基本概念
3.2 抽象數據類型
3.3 線性表
3.4 棧和隊列
3.5 樹和二叉樹
3.6 圖
3.7 文件的組織
02
03
04
05
06
07
Con
tent
s 目錄
1
樹的定義
樹（Tree）是n(n≥0)個結點的有限集合T，滿足兩個條件： 有且僅有一個特定的稱為根（Root）的結點，它沒有前趨； 其餘的結點可分成m個互不相交的有限集合T1,T2,…,Tm，其中每個集合
又是一棵樹，並稱為根的子樹。
樹
樹的定義
樹（Tree）是n(n≥0)個結點的有限集合T，滿足兩個條件： 有且僅有一個特定的稱為根（Root）的結點，它沒有前趨； 其餘的結點可分成m個互不相交的有限集合T1,T2,…,Tm，其中每個集合
又是一棵樹，並稱為根的子樹。
樹
樹是遞歸結構—— 在樹的定義中又用到了樹的概念
樹的邏輯結構
4
a
b d c e
f h g i j l m n k
層次結構
一多對
非線性
線性結構便不足以方便地 描述這樣的複雜情形
樹
樹的相關術語
5
A
G
D C B
F E
指樹中的一個元素，包含數據項及若干指向其子樹的分支
結點的子樹的根稱為該結點的孩子
一個結點的直接上層結點稱為該結點的雙親
同一雙親的孩子結點
B、C、D是A的孩子，E、F是B的孩子
A是B、C、D的雙親，B是E、F的雙親
B、C、D是兄弟關係
樹的結點
孩子結點
雙親結點
兄弟結點
樹的相關術語
6
A
G
D C B
F E
結點層
樹的深度
樹的度
葉子結點
分枝結點
有序樹
森林
Level 1
Level 2
Level 3
根結點的層定義為1；根的孩子為第二層結點，依此類推；
樹中最大的結點層
度不為0的結點
也叫終端結點，是度為0的結點
樹中最大的結點度 結點子樹的個數
不考慮子樹的順序 子樹有序的樹
互不相交的樹集合
結點的度
無序樹
樹的基本術語——示例
7
E,K,L,G,
H,I,M
樹的存儲 順序存儲方式
順序存儲時，首先必須對樹形結構的結點進行某種方式的線性化，
使之成為一個線性序列，然後存儲。
鏈式存儲方式
鏈式存儲時，使用多指針域的結點形式，每一個指針域指向一棵
子樹的根結點。
樹的存儲 順序存儲方式
順序存儲時，首先必須對樹形結構的結點進行某種方式的線性化，
使之成為一個線性序列，然後存儲。
鏈式存儲方式
鏈式存儲時，使用多指針域的結點形式，每一個指針域指向一棵
子樹的根結點。
由於樹的分支數不固定，很難給出一種固定的存儲結構，所以本章的剩餘內容將集中介紹二叉樹
二叉樹的基本概念
二叉樹是n（n≥0）個結點的有限集，它或為空樹（n=0），或由一個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹構成。
二叉樹
說明：二叉樹是每個結點最多有兩個子樹的有序樹。二叉樹的子樹通常稱為"左子樹"（left subtree）和"右子樹"（right subtree）。左、右子樹的順序不能互換。
A
F
G
E D
C B
二叉樹是遞歸定義，在二叉樹的定義中又用到了二叉樹的概念
二叉樹的概念
11
二叉樹的概念
12
二叉樹與樹的區別是什麼？
思考&討論
二叉樹的概念
13
二叉樹與樹的區別是什麼？
思考&討論
討論：儘管二叉樹與樹有許多相似之處，樹和二叉樹的兩個主要差別： （1）樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2； （2）樹的結點無左、右之分，而二叉樹的結點有左、右之分，
二叉樹的五種基本形態
R R
L-SubTree
R R-SubTree
R
L-SubTree
R-SubTree
根僅有一棵子樹時，也要分辨是左子樹還是右子樹。
二叉樹的特殊形態——滿二叉樹
15
一顆深度為k且有2k -1個結點的二叉樹稱為滿二叉樹
二叉樹的特殊形態——完全二叉樹
16
(a)滿二叉樹 (b)完全二叉樹 (c) 不是完全二叉樹
如果一個深度為k的二叉樹，它的結點按照從根結點開始
，自上而下，從左至右進行連續編號後，得到的順序與滿二叉樹相應結點編號順序一致，則稱這個二叉樹為完全二叉樹。
二叉樹的存儲——順序存儲
一般二叉樹的存儲
在一棵完全二叉樹中，按照從根結點起，自上而下，從左至右的方式對
結點進行順序編號，便可得到一個反映結點之間關係的線性序列。
一般二叉樹的順序存儲是首先將二叉樹映射為完全二叉樹（通過虛結
點），然後再用完全二叉樹的方式存儲。
A
B C
D E F
G
A
B C
D E F
G
A B C D E F G
(a) 待存儲二叉樹 (b)轉為完全二叉樹（線性化） (c)順序存儲
二叉樹的存儲——鏈式存儲
二叉樹的鏈式存儲
以類似單鍊表中的鍊表示樹中的弧，
即可得到二叉鍊表。
A
B C
D E F
G
A
B C
D E F
G
^
^ ^ ^
^ ^
^ ^
(a)二叉樹 (b)二叉鍊表
19
二叉樹的運算——遍歷
對結點的處理，如修改結點數據、輸出結點數據。
按某種順序訪問數據結構中的結點，要求每個結點訪問一次且僅
訪問一次。
遍歷對線性結構是容易解決的，而二叉樹是非線性的，因而需要尋找一種規律，以便使二叉樹上的結點能排列在一個線性隊列上，從而便於遍歷。
如何訪問二叉樹的
每個結點，而且每個結點僅被訪問一次？
C B
A
D
F
E
訪 問
二叉樹的遍歷
二叉樹的運算——遍歷
兩種遍歷的方法
——深度優先遍歷
——廣度優先遍歷
遍歷是二叉樹中最主要的運算
二叉樹的深度優先遍歷
1
2 3
2
1 3
3
1 2
二叉樹的深度優先遍歷
規定左子樹在右子樹之前訪問，則按照訪問根的時機，定義出三
種次序：先序（前序）、中序和後序遍歷。
(a)先序遍歷 (b)中序遍歷 (c)後序遍歷
深度遍歷策略——先序遍歷
22
若二叉樹非空，則依次進行以下操作
（1）訪問根結點； （2）先序遍歷左子樹； （3）先序遍歷右子樹；
A
B C
D E F G
L
深度遍歷策略——先序遍歷
23
若二叉樹非空，則依次進行以下操作
（1）訪問根結點； （2）先序遍歷左子樹； （3）先序遍歷右子樹；
A
B C
D E F G
L
先序遍歷：A B D E C F L G
深度遍歷策略——中序遍歷
24
若二叉樹非空，則依次進行以下操作
（1）中序遍歷左子樹； （2）訪問根結點； （3）中序遍歷右子樹；
A
B C
D E F G
L
深度遍歷策略——中序遍歷
25
若二叉樹非空，則依次進行以下操作
（1）中序遍歷左子樹； （2）訪問根結點； （3）中序遍歷右子樹；
A
B C
D E F G
L
中序遍歷：D B E A L F C G
深度遍歷策略——後序遍歷
26
若二叉樹非空，則依次進行以下操作
（1）後序遍歷左子樹； （2）後序遍歷右子樹； （3）訪問根結點；
A
B C
D E F G
L
深度遍歷策略——後序遍歷
27
若二叉樹非空，則依次進行以下操作
（1）後序遍歷左子樹； （2）後序遍歷右子樹； （3）訪問根結點；
A
B C
D E F G
L
後序遍歷：D E B L F G C A
二叉樹的廣度優先遍歷
二叉樹的廣度優先遍歷
按層次自根結點向下，每層自左向右進行處理。
A
B E
C D F
A
B E
C D F
A
B E
C D F
A
B E
C D F
二叉樹的應用——引子
29
數字通信系統模型
信息發布者
信息接收者
信源編碼——將信源發出的消息符號轉換為適合信道傳輸的符號。
信源解碼——按照編碼的逆過程，將信息還原為原來的形式。
二元信道(常用)
信源編碼 信源編碼
•編碼或代碼（code）通常指一種在人和機器之間進行信息轉換的系統（體系）。換句話說，編碼便是交流。
•在信源編碼中，除了使信息數字化，還強調使用儘量少的數據代表儘量多的信息。
定長與變長碼
定長碼與變長碼
•信源編碼可以採用定長碼（每個字符用固定長度二進位碼字表示），也可以採用變長碼（每個字符使用不一樣長度的二進位碼字表示）。
a b c d e F
頻率(千次) 45 13 12 16 9 5
定長碼 000 001 010 011 100 101
變長碼 0 101 100 111 1101 1100
文件中共有100000個字符,其中只有a,b,c,d,e共5種字符,每種字符出現的頻率如下表.
例
採用定長碼和變長碼方案的文件編碼總長度分別為300000位和224000位.
前綴碼
前綴碼
•任何一個字符的代碼都不是其它字符代碼的前綴,稱這種性質為編碼的前綴性質,簡稱為前綴碼.
•編碼的前綴性質保證了解碼過程的正確性。
a b c d e F
頻率(千次) 45 13 12 16 9 5
定長碼 000 001 010 011 100 101
變長碼 0 101 100 111 1101 1100
哈夫曼樹的編碼和解碼示例
A B C D E
1
0
1
1
0 0 0 1
A：00 B:010 C：011 D：10 E：11
EAEBAECDEA
A：00 B:010 C：011 D：10 E：11
1100110100011011101100
ASC II碼：10字節 22比特<3字節
編碼
解碼
哈夫曼樹的概念
34
D
C
A B 4
7 5
2
路徑
結點的權
結點的帶權路徑長度
樹的帶權路徑長度
(Weighted Path Length)
若存在一個結點序列k1,k2,…,kj，可使k1到達kj,
則稱這個結點序列是k1到達kj的一條路徑
具有一定含義的比例係數。如"詞頻"
路徑長度 路徑經過的邊的數目
結點的路徑長度 從根到該結點的路徑長度
從根到該結點的路徑長度與該結點權的乘積
n
i i
i 1
WPL W L
n ——葉子結點的數目 Wi——第i個葉結點的權值，i=1,2,...n Li——第i個葉結點的路徑長度，i=1,2,...n
哈夫曼樹（Huffman Tree）
C D A B
4 7 5 2
在有n個帶權葉子結點的所有二叉樹中，帶權路徑長度WPL最
小的二叉樹被稱為最優二叉樹或哈夫曼樹。
哈夫曼樹
哈夫曼樹的構造
哈夫曼樹的構造方法
(1)根據給定的n個權值{w1, w2,…,wn}構成n棵二叉樹的集合F＝
{T1,T2,…,Tn }, 其中Ti中只有一個權值為wi的根結點，左、右子
樹均為空。
(2)在F中選取兩棵根結點的權值最小的樹作為左、右子樹構造一棵
新的二叉樹，且置新的二叉樹的根結點的權值為左、右子樹上根結
點的權值之和。
(3)在F中刪除這兩個棵權值最小的樹，同時將新得到的二叉樹加入
F中。
(4) 重複(2)、(3)直到F中僅剩一棵樹為止。這棵樹就是哈夫曼樹。
示例：權值為0.4、0.3、0.1、0.1、0.02、0.08的6個葉子結點A、B、C、D、E、F構造哈夫曼樹。
哈夫曼編碼和解碼
哈夫曼編碼
從哈夫曼樹根結點開始，對左子樹分配代碼0，右子樹分配代碼1，一直
到達葉子結點為止，然後將從樹根沿每條路逕到達葉子結點的代碼排列
起來，便得到了哈夫曼碼。
A B C D E
1
0
1
1
0 0 0 1
A：00 B:010 C：011 D：10 E：11
EAEBAECDEA
A：00 B:010 C：011 D：10 E：11
1100110100011011101100
ASC II碼：10字節 22比特<3字節
編碼
解碼
樹-思考與練習
思考
•掌握二叉樹的特點、基本性質、存儲方法；
•理解二叉樹的遍歷方法；
•理解哈夫曼編碼算法。
上機練習
•電子版(PDF)講義4中的4-19,4-20,4-21,4-22
01 3.1數據結構基本概念
3.2 抽象數據類型
3.3 線性表
3.4 棧和隊列
3.5 樹和二叉樹
3.6 圖
3.7 文件的組織
02
03
04
05
06
07
Con
tent
s 目錄
40
主要內容
• 圖
• 圖的應用
41
學習目標
• 理解圖及圖結構的描述
• 掌握圖的遍歷
• 掌握Dijkstra算法解決圖的最短路徑問
題
42
圖引例1——地圖染色問題
3
1
2
3
2 3
3
4
四色猜想 四色定理
1852年英國人 發現現象
1976年美國人 計算機證明
每幅地圖最多可以用四種顏色著色，使得相鄰區域不重色 43
圖引例1——地圖染色問題
44
圖引例1——地圖染色問題
信息與信息間的聯繫如何 抽象後存儲到計算機中？
陝西 河南
安徽
湖北 四川
山西
貴州
湖南
廣東 廣西
福建
浙江
江西
江蘇
山東
45
圖引例2——搜尋引擎與網站的結構
其他網站
頻道頁2
首頁
頻道頁3
標籤
頻道頁1
內容頁2 內容頁3內容頁1
搜尋引擎的工作原理是按照一定的搜索策略搜索網絡並搜集信息，在對信息進行組織和處理後存儲在自己的資料庫中，以便為用戶提供快速檢索服務。完成網絡信息搜索任務的軟體俗稱"網絡蜘蛛"或"網絡爬蟲"，網絡蜘蛛是通過網站的站內連結來遍歷網站內容的。
網站內連結結構
46
圖引例2——搜尋引擎與網站的結構
（a）網站連結 （b）網站間的連結抽象
47
圖引例3——最短路線問題
路線圖 城市：頂點={a, b, c, d, e} 路線：頂點間連線={ab, ad, bc , be, de} 問題描述：求出從d到c的最短路線。
49
圖的討論
【思考與討論】從實際問題中抽象出來的數據結構的"圖"有什麼特點？
50
圖的討論
【思考與討論】從實際問題中抽象出來的數據結構的"圖"有什麼特點？
51
數據結構中的圖是拓撲意義上的圖，其特點為：
用點表示對象，有直接聯繫的對象用線連接起來。
圖形中連線的長短曲直和結點的位置無關緊要，每一條線兩端都
有結點。
圖的概念
圖(G)是一種非線性數據結構，它由兩個集合V(G)和E(G)組成，形式上記
為：G=( V, E )。其中V(G)是頂點(Vertex)的非空有限集合，E(G)是V(G)中任意兩
個頂點之間的關係集合，又稱為邊(Edge)的有限集合。
圖
元素結點之間的關係可以是多對多的
52
圖的類型
有向圖
•若且唯若圖G的每條邊有方向，稱G為有向圖，如下圖(a) 。有向邊記為〈
起始頂點，終止頂點〉。有向邊又稱為弧，因此弧的起始頂點就稱為弧尾，終止頂點稱為弧頭。
無向圖
•G為無向圖若且唯若G中的每條邊是無方向的，如下圖(b) 。記法：無向圖用兩個頂點組成的無序對表示，即(頂點1，頂點2)。
A
B C
A
B C
（a） （b）
頂點集合V={A,B,C}； 邊集合E={(A,B),(B,C),(A,C)}；
頂點集合V={A,B,C}； 邊集合E={<A,B>,<B,A>,<B,C>,<A,C>}；
53
圖的基本術語——圖
有很少條邊或弧（如e<nlogn，n是圖的頂點數，e是邊數或者弧數）的圖稱為稀疏圖；反之稱為稠密圖。
稀疏圖與稠密圖
54
圖的基本術語——頂點與邊
鄰接點
關聯邊
邊的兩個頂點
55
若存在邊e= (v, u), 則稱頂點v、u 關聯邊e，或者稱邊e和頂點v、u 關聯。
圖的基本術語——度
度
•與樹相似，圖中的頂點也有度的概念：在無向圖中關聯於某一頂點vi的邊
的數目稱為vi的度，記為D(vi)。在有向圖中，把以頂點vi為終點的邊的數目
稱為vi的入度，記為ID(vi)；把以頂點vi為起點的邊的數目稱為vi的出度，記
為OD(vi)；把頂點vi的度定義為該頂點的入度和出度之和。
A
B C
A
B C
（a） （b）
（a）A的出度為2，入度為1，度為3。 （b）A的度為2。
56
圖的基本術語——權與網
網絡
•圖中的邊還可以標註一個數值特徵，稱為該邊的權值。圖中的每條邊都具
有權值時，