數據結構與算法分析

新視角

結點邏輯關系分層次的非線性結構樹Chapter

5DataStructuresandAlgorithmAnalysis主要內容廣義表的概念、存儲結構、基本運算廣義表樹的定義和基本術語二叉樹的概念、存儲結構遍歷二叉樹哈夫曼樹及其應用樹學習目標了解數據的邏輯結構從線性結構到非線性結構的過渡了解包含子結構的線性結構理解鏈式存儲結構在表達非線性數據結構中的作用掌握樹的概念、存儲方法、基本運算了解廣義表的概念、結構特點及其存儲表示方法實際問題中的樹及抽象樹的邏輯結構樹的存儲結構二叉樹的邏輯結構二叉樹的存儲結構及實現樹的遍歷樹的應用廣義表*CONTENTS5.15.25.35.45.55.65.75.8實際問題中的樹及抽象樹的邏輯結構樹的存儲結構二叉樹的邏輯結構二叉樹的存儲結構及實現樹的遍歷樹的應用廣義表*CONTENTS5.15.25.35.45.55.65.75.85.1實際問題中的樹及抽象樹引例1——日常生活中的樹形結構8樹引例2——計算機的目錄結構9樹引例3——樹形結構的網站10表達式樹11實際問題本質的抽象12一切具有層次關系的問題都可用樹來描述實際問題中的樹及抽象樹的邏輯結構樹的存儲結構二叉樹的邏輯結構二叉樹的存儲結構及實現樹的遍歷樹的應用廣義表*CONTENTS5.15.25.35.45.55.65.75.8樹的邏輯結構14abdcefhgijlmnk層次結構一多對應非線性線性結構便不足以方便地描述這樣的復雜情形樹5.2樹的邏輯結構5.2.15.2.2樹的定義和基本術語樹的操作定義5.2樹的邏輯結構5.2.15.2.2樹的定義和基本術語樹的操作定義樹17定義AGDCBFE樹形結構是一種重要的非線性結構，討論的是層次和分支關系樹是遞歸結構——在樹的定義中又用到了樹的概念樹（tree）是包含n個結點的有限集合，其中：（1）有一個根結點，它只有直接后繼，但沒有直接前趨。（2）除根結點之外的其余數據元素被分為m個根的子樹。當樹的集合為空時，n=0，此時稱為空樹，空樹中沒有結點。樹的示意圖18樹的圖形表示方法19樹的相關術語20AGDCBFE包含一個數據元素及若干指向子樹的分支結點的子樹的根稱為該結點的孩子一個結點的直接上層結點稱為該結點的雙親同一雙親的孩子結點B、C、D是A的孩子，E、F是B的孩子A是B、C、D的雙親，B是E、F的雙親B、C、D是兄弟關系樹的結點孩子結點雙親結點兄弟結點樹的相關術語21AGDCBFE結點層樹的深度結點的度樹的度葉子結點分枝結點有序樹無序樹森林Level1Level2Level3根結點的層定義為1；根的孩子為第二層結點，依此類推；樹中最大的結點層度不為0的結點也叫終端結點，是度為0的結點樹中最大的結點度結點子樹的個數不考慮子樹的順序子樹有序的樹互不相交的樹集合樹的基本術語——示例22E,K,L,GH,I,M樹的概念23我們熟悉的樹形結構中，無序樹、有序樹有哪些？思考&討論討論：有序樹無序樹的區別在于子樹是否有順序要求，有順序要求的如家譜、書的目錄等；無序的可以是計算機中的文件夾目錄等。5.2樹的邏輯結構5.2.15.2.2樹的定義和基本術語樹的操作定義構造建立一棵樹，初始化。樹的基本操作查找可以是查找根結點、雙親結點、孩子結點、葉子結點、指定值的結點等。插入刪除在指定位置插入/刪除結點遍歷沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴于具體的應用問題求深度計算樹的高度。實際問題中的樹及抽象樹的邏輯結構樹的存儲結構二叉樹的邏輯結構二叉樹的存儲結構及實現樹的遍歷樹的應用廣義表*CONTENTS5.15.25.35.45.55.65.75.8樹的存儲結構27存得進取得出A存數值存聯系B樹形結構的存儲原則。非線性結構比線性關系復雜，存儲樹形結構問題的關鍵與重點。樹的存儲結構2828樹形結構存儲結點間聯系的原則是什么？一個雙親n個孩子對于設計好的存儲結構，檢驗的標準則是只要在存儲結構中能找到一個結點的這兩種關系，那么這樣的存儲結構設計就是可行的。我們可以稱之為“雙親孩子檢驗原則”。雙親孩子檢驗法思考&討論5.3樹的存儲結構5.3.15.3.2樹的連續存儲方式樹的鏈式存儲方式5.3樹的存儲結構5.3.15.3.2樹的連續存儲方式樹的鏈式存儲方式樹連續存儲1——雙親孩子表示法31樹連續存儲2——雙親表示法32樹連續存儲3——孩子表示法335.3樹的存儲結構5.3.15.3.2樹的連續存儲方式樹的鏈式存儲方式樹的鏈式存儲方式35樹的鏈式存儲方式361.同構型結構的特點有哪些？關于樹的結構討論37思考&討論2．什么樣的樹在用同構型結構時，空的指針域最少？討論：同構型結構消除了異構型的缺陷，結構的統一化使管理變得容易，但若多數結點的度小于樹的度，則部分指針域為空，造成存儲空間的浪費。38什么樣的樹在用同構型結構時，空鏈域最少？設有n個結點，度為d的樹，用同構型結點存儲整個鏈表共有指針域數有用的指針域數n*d個n-1個空的指針域數n(d-1)+1個R=空的指針域數整個鏈表共有指針域數=n(d-1)+1ndR=n→∞Limn→∞Limn(d-1)+1nd=1d1-K越小越好結論：d=2時，空鏈域最少二叉樹關于樹的結構討論根結點的地址不占指針域degree——度想去掉結點個數的因素思考&討論樹鏈式存儲——孩子兄弟表示法39樹鏈式存儲——孩子鏈表表示法40樹鏈式存儲——孩子鏈表表示法41實際問題中的樹及抽象樹的邏輯結構樹的存儲結構二叉樹的邏輯結構二叉樹的存儲結構及實現樹的遍歷樹的應用廣義表*CONTENTS5.15.25.35.45.55.65.75.843若我們能找到普通樹轉換為二叉樹、二叉樹又能還原成原來的普通樹的方法，就完美地解決了這個問題。把二叉樹作為典型的結構加以研究討論，相應的結果能用到普通的樹上面嗎？二叉樹普通樹思考&討論樹轉換為二叉樹44樹轉換為二叉樹的過程中各結點的聯系有怎樣的變化？樹轉換為二叉樹45思考&討論討論：加線的過程，是增加了結點和兄弟的直接關聯；去線的操作，是去掉了除長子之外的聯系，但是可以通過長子的兄弟關系，間接得到所有孩子的信息，這個和前面介紹的“樹鏈式存儲-孩子兄弟表示法”是一樣的原理。森林轉換為二叉樹46二叉樹還原為樹47樹還原為二叉樹的過程中各結點的聯系有怎樣的變化？思考&討論一個結點x的左孩子其子孫，從來歷上看，都是這個左孩子的兄弟，如圖5.24中的FG點，都是E的子孫，EFG都是B的孩子，故加線是恢復結點與孩子的關系；去線是去掉兄弟間的連線，這樣就可以恢復成原來的樹結構了。樹與二叉樹的存儲關系48樹鏈式存儲——孩子兄弟表示法495.4二叉樹的邏輯結構5.4.15.4.2二叉樹的概念二叉樹的基本性質5.4.3二叉樹的操作定義5.4二叉樹的邏輯結構5.4.15.4.2二叉樹的概念二叉樹的基本性質5.4.3二叉樹的操作定義52說明：二叉樹是每個結點最多有兩個子樹的有序樹。二叉樹的子樹通常稱為“左子樹”（leftsubtree）和“右子樹”（rightsubtree）。左、右子樹的順序不能互換。二叉樹的概念AFGEDCB二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念

二叉樹是n(n≥0)個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成。二叉樹二叉樹的概念53二叉樹與樹的區別是什么？思考&討論討論：盡管二叉樹與樹有許多相似之處，樹和二叉樹的兩個主要差別：（1）樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2；（2）樹的結點無左、右之分，而二叉樹的結點有左、右之分，二叉樹的基本形態54二叉樹的特殊形態——滿二叉樹55如果深度為k的二叉樹，有2k-1個結點則稱為滿二叉樹二叉樹的特殊形態——完全二叉樹56可以說滿二叉樹是完全二叉樹的特例情形、(b)完全二叉樹(c)不是完全二叉樹二叉樹的特殊形態——完全二叉樹57完全二叉樹5.4二叉樹的邏輯結構5.4.15.4.2二叉樹的概念二叉樹的基本性質5.4.3二叉樹的操作定義二叉樹的基本性質59深度為h的二叉樹至多有2h–1個結點（h

≥1）對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為2的結點，則必存在關系式：n0=n2+1FGCBADE在二叉樹的第i層上至多有2i-1個結點（i≥1）性質1性質2性質3完全二叉樹的性質60具有n個結點的完全二叉樹的深度為：[log2n]+1若對含n個結點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為i的結點：若i=1，則該結點是二叉樹的根，無雙親，否則，編號為

i/2

的結點為其雙親結點；若2i>n，則該結點無左孩子，否則，編號為2i的結點為其左孩子結點；若2i+1>n，則該結點無右孩子結點，否則，編號為2i+1的結點為其右孩子結點。123456FCBADE方括號表示取整性質4性質5完全二叉樹的性質【例5-1】二叉樹各種結點數目的計算若一個完全二叉樹有n=1450個結點，則度為1的結點、度為2的結點、葉子結點個數分別是多少？有多少左孩子，多少右孩子？該樹的高度是多少？解：樹的高度：∵是完全二叉樹

∴1～10層全滿，k=10最下層葉子結點的個數=n-（2k

-1）=1450-1023=427k-1層帶葉子的結點數=[427+1/2]=214k-1層結點數=2k-1=512k-1層葉子數=512-214=298∴總葉子數n0=427+298=725度為2的結點n2=n0-1=724度為1的結點n1=n-1-2n2=1450-1-2*724=1有左孩子結點數=度為2的結點數+度為1的結點數=725有右孩子結點數=度為2的結點數=72461二叉樹的特殊形態——完全二叉樹62完全二叉樹k層最下層k-1層k-1層帶葉子的結點k-1層帶的葉子數5.4二叉樹的邏輯結構5.4.15.4.2二叉樹的概念二叉樹的基本性質5.4.3二叉樹的操作定義二叉樹的操作定義構造建立一棵樹，初始化查找查找指定條件的結點插入

刪除在指定位置插入/刪除結點遍歷

對樹中每個結點均做一次且僅做一次訪問求深度計算樹的高度實際問題中的樹及抽象樹的邏輯結構樹的存儲結構二叉樹的邏輯結構二叉樹的存儲結構及實現樹的遍歷樹的應用廣義表*CONTENTS5.15.25.35.45.55.65.75.8普通樹二叉樹二叉樹的存儲結構及實現已討論過一般形式樹的存儲方案簡化對照樹的一般形式來討論二叉樹的存儲方案5.5二叉樹的存儲結構及實現5.5.15.5.2二叉樹的順序存儲結構二叉樹的鏈式存儲結構5.5.3建立動態二叉鏈表二叉樹順序存儲——結點間關系分析68二叉樹順序存儲——結點間關系分析69二叉樹順序存儲——結點位置分析70二叉樹順序存儲——結點位置分析71完全二叉樹存儲方案是否適用一般的二叉樹存儲？將二叉樹的所有結點，按照完全二叉樹的編號方法進行編號，按序存儲到一片連續的存儲單元中。結點的順序將反映出結點之間邏輯關系。二叉樹的順序存儲思考&討論二叉樹順序存儲——結點位置分析72退化的二叉樹的存儲5.5二叉樹的存儲結構及實現5.5.15.5.2二叉樹的順序存儲結構二叉樹的鏈式存儲結構5.5.3建立動態二叉鏈表二叉樹的鏈式存儲結構74

二叉樹的每個結點含有兩個指針域來分別指向相應的分支，稱其為二叉鏈表二叉鏈表二叉樹的鏈式存儲結構75二叉樹的每個結點含有兩個指針域來分別指向相應的分支。二叉樹的鏈式存儲二叉樹的三叉鏈存儲結構76樹的三重鏈表表示77靜態二叉鏈表78ADBCFE021435孩子結點在數組中的位置。用-1表示無左孩子或右孩子采用數組存儲的靜態二叉鏈表5.5二叉樹的存儲結構及實現5.5.15.5.2二叉樹的順序存儲結構二叉樹的鏈式存儲結構5.5.3建立動態二叉鏈表層次輸入法創建二叉鏈表方法一80層次輸入法創建二叉鏈表方法一81

Q隊列元素A出列，A的下標i=1

將A的左孩子結點地址（在下標為2*i處）填入A結點的左指針域

將A的右孩子結點地址（在下標為2*i+1處）填入A結點的右指針域層次輸入法創建二叉鏈表方法一82

Q隊列元素A出列，A的下標i=1

將A的左孩子結點地址（在下標為2*i處）填入A結點的左指針域

將A的右孩子結點地址（在下標為2*i+1處）填入A結點的右指針域83層次輸入法創建二叉鏈表方法一偽代碼描述設二叉樹的深度為k，則隊列Q的長度至少為2k-1+1(隊列的0下標位不用)生成樹的所有結點，結點地址按結點編號順序填入隊列數組Q[]中隊頭元素下標i=1當Q隊列i<k-1層元素個數(2k-1)

Q隊列元素i出列將i的左孩子結點地址(下標2*i）填入i的左指針域將i的右孩子結點地址(下標2*i+1的結點）填入i的右指針域返回根結點地址層次輸入法創建二叉鏈表方法二84

輸入結點信息，若輸入的結點不是虛結點，則建立一個新結點。若新結點是第1個結點，則令其為根結點，否則將新結點作為孩子鏈接到它的雙親結點上。如此反復進行，直到輸入結束標志“＃”為止層次輸入法創建二叉鏈表方法二85

輸入結點信息，若輸入的結點不是虛結點，則建立一個新結點。若新結點是第1個結點，則令其為根結點，否則將新結點作為孩子鏈接到它的雙親結點上。如此反復進行，直到輸入結束標志“＃”為止86層次輸入法創建二叉鏈表方法二偽代碼細化描述設二叉樹的深度為k，則隊列Q的長度設置按完全二叉樹編號至樹的最后一個結點當輸入結點信息不是結束標志‘#’若輸入的結點不是虛結點，則建立一個新結點并入隊若新結點是第1個結點，則令其為根結點，否則將新結點作為孩子鏈接到它的雙親結點上。若新結點是雙親結點的右孩子，則雙親結點出隊。返回根結點地址87層次輸入法創建二叉鏈表方法二功能描述輸入輸出CreaTree無根地址函數名形參函數類型

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;數據結構設計函數框架設計層次輸入法創建二叉鏈表方法二/*===============================================函數功能：層次輸入法創建二叉鏈表函數輸入：無函數輸出：二叉鏈表根結點鍵盤輸入：按完全二叉樹結點編號規則順序輸入結點值，空結點為@====================================================*/885.6樹的遍歷5.6.15.6.2樹的廣度優先遍歷樹的深度優先遍歷5.6.3樹的遍歷的應用引例1——機電設備通電自檢模型90設備通電自檢步驟應該如何進行檢測步驟：左子樹：網卡等正常→PCI正常→顯卡等正常→非PCI正常→板卡正常右子樹：硬盤等正常→外存正常→鍵盤等正常→其他正常→非板卡正常整棵樹：板卡正常→非板卡正常→計算機正常在上述的檢測過程中，“后序遍歷”的意思是指樹的根結點是最后被訪問到的，無論是整棵樹還是左右子樹。“后序遍歷”引例2——網購商品的管理91FoodMeatPorkBeefFruitYellowBananMangoRedCherry如何打印商品清單“先序遍歷”根結點：Food左子樹：Meat→Pork/Beef右子樹：Fruit→（左子樹）Yellow→Banan/MangoFruit→（右子樹）Red→Cherry引例3——樹中結點的快速查找策略92“中序遍歷”如何得到有序序列？二分查找遞歸過程根為1的樹：左子樹（空）→根1→右子樹（2）→結果為1、2根為3的樹：左子樹（1,2）→根3→右子樹（4,5）→結果為1、2、3、4、5根為9的樹：左子樹（7,8）→根9→右子樹（10,11）→結果為7、8、9、10、1193遍歷的基本概念對結點的處理。如修改結點數據、輸出結點數據。

按某種順序訪問數據結構中的結點，要求每個結點訪問一次且僅訪問一次。遍歷對線性結構是容易解決的，而二叉樹是非線性的，因而需要尋找一種規律，以便使二叉樹上的結點能排列在一個線性隊列上，從而便于遍歷。如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？CBADFE遍歷訪問94遍歷的基本概念——基本遍歷策略廣度遍歷(Breadth-FirstSearch)深度遍歷(Depth_FirstSearch)5.6樹的遍歷5.6.15.6.2樹的廣度優先遍歷樹的深度優先遍歷5.6.3樹的遍歷的應用基于順序存儲結構的樹的廣度優先遍歷96廣度遍歷（層次遍歷）方法：從上到下、從左到右訪問各結點適用于順序存儲結構

基于鏈式存儲結構的二叉樹廣度優先遍歷97基于鏈式存儲結構的二叉樹廣度優先遍歷98(1)初始化一個隊列，并把根結點入列隊；

(2)隊列元素出隊，取得一個結點，訪問該結點；

(3)若該結點的左孩子非空，則將該結點的左子樹入隊列；

(4)若該結點的右孩子非空，則將該結點的右子樹入隊列；(5)循環執行步驟2到4，直至隊列為空。算法描述基于鏈式存儲結構的二叉樹廣度優先遍歷99二叉樹結點結構描述typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*Q[MAXSIZE];//設數組Q做隊列，隊列元素類型為二叉鏈表結點類型功能輸入輸出層次遍歷二叉樹leverOrder二叉鏈表根結點地址無函數名形參函數類型函數框架設計數據結構設計基于鏈式存儲結構的二叉樹廣度優先遍歷/*=====================================函數功能：層次遍歷二叉樹，打印遍歷序列函數輸入：二叉鏈表根結點地址bitree*Ptr函數輸出：無=======================================*/1005.6樹的遍歷5.6.15.6.2樹的廣度優先遍歷樹的深度優先遍歷5.6.3樹的遍歷的應用樹的深度優先遍歷102深度優先遍歷方法深度優先遍歷遞歸算法深度優先遍歷非遞歸算法樹的深度優先遍歷103深度優先遍歷方法深度優先遍歷遞歸算法深度優先遍歷非遞歸算法深度優先遍歷方法104先左后右：DLR，LDR，LRD先右后左：DRL，RDL，RLD105深度優先遍歷方法先序遍歷（DLR）中序遍歷（LDR）后序遍歷（LRD）深度遍歷策略——先序遍歷106若二叉樹非空，則依次進行以下操作（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹；深度遍歷策略——中序遍歷107若二叉樹非空，則依次進行以下操作（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹；深度遍歷策略——后序遍歷108若二叉樹非空，則依次進行以下操作（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點；用投影法理解樹的遍歷109用投影法理解樹的遍歷110用投影法理解樹的遍歷111先序遍歷的例子112先序遍歷的例子113情形圈中表示DLR序列情形圈中表示DLR序列1樹的根A6A的右子樹繼續細化2A的左子樹繼續細化7A右子樹的根E3A左子樹的根B8E的右子樹繼續細化4B的右子樹繼續細化9E的右子樹的根F5B的右子樹的根C10F的左子樹GHK4'B的右子樹CD8'E的右子樹FGHK2'A的左子樹BCD6'A的右子樹EFGHK中序遍歷的例子114中序遍歷的例子115情形圈中表示LDR序列情形圈中表示LDR序列1A的左子樹繼續細化6A的右子樹繼續細化2A的左子樹的根B7A的右子樹的根E3B的右子樹繼續細化8E的右子樹繼續細化4C的左子樹的根D9F的左子樹HGK3'B的右子樹DC8'E的右子樹HGKF1’A的左子樹BDC6'A的右子樹EHGKF5樹的根A

后序遍歷的例子116后序遍歷的例子情形圈中表示LDR序列情形圈中表示LDR序列1A的左子樹繼續細化5E的右子樹繼續細化2B的右子樹繼續細化6F的左子樹HKG3C的左子樹的根D5'E的右子樹HKGF2'B的右子樹DC4'A的右子樹HKGFE1'A的左子樹DCB7樹的根A4A的右子樹繼續細化

117深度優先遍歷遞歸算法118深度優先遍歷方法深度優先遍歷遞歸算法深度優先遍歷非遞歸算法先序遍歷的遞歸算法119功能描述輸入輸出輸出DLR遍歷序列PreOrder根地址無函數名形參函數類型偽代碼描述輸入：樹的當前根結點t；設樹的結點指針bitree*t遞歸的邊界條件：t為空結點，返回；遞歸繼續的條件：訪問t結點；

前序遍歷t的左子樹；

前序遍歷t的右子樹；函數框架設計先序遍歷的遞歸算法120typedefstructnode{ datatypedata; structnode*lchild,*rchild;}BinTreeNode;數據結構設計先序遍歷的遞歸算法/*=================================函數功能：先序遍歷樹的遞歸算法函數輸入：樹的根結點函數輸出：無屏幕輸出：樹的先序遍歷序列====================================*/121DLR遞歸過程示意圖122中序遍歷的遞歸算法/*=============================函數功能：中序遍歷樹的遞歸算法函數輸入：樹的根結點函數輸出：無屏幕輸出：樹的中序遍歷序列===============================*/voidinorder(BinTreeNode*t){if(t){inorder(t->lchild);putchar(t->data);inorder(t->rchild);}}123后序遍歷的遞歸算法/*=====================================

函數功能：后序遍歷樹的遞歸算法

函數輸入：樹的根結點

函數輸出：無

屏幕輸出：樹的后序遍歷序列======================================*/voidpostorder(BinTreeNode*t){if(t)

{

postorder(t->lchild);postorder(t->rchild);putchar(t->data);}}124遍歷的分析125二叉樹遍歷路徑圖從根結點出發到終點的路徑上，每個結點經過3次“左手扶墻”法第一次經過A1B1C1D1E1————先序遍歷ABCDE第二次經過B2D2C2A2E2————中序遍歷BDCAE第三次經過D3C3B3E3A3————后序遍歷DCBEA用遍歷的方法建立二叉鏈表【例5-3】用遍歷的方法建立二叉鏈表解：算法基本思想，按先序遍歷順序，建立二叉鏈表的所有結點并完成相應結點的鏈接。樹的先序序列為ABD@F@@@CE@@@126用遍歷的方法建立二叉鏈表【例5-3】用遍歷的方法建立二叉鏈表/*=========================================函數功能：用先序遍歷的方法建立二叉鏈表函數輸入：（二叉鏈表根結點）函數輸出：二叉鏈表根結點鍵盤輸入：樹的先序遍歷序列,子樹為空時輸入@============================================*/ 127樹的深度優先遍歷128深度優先遍歷方法深度優先遍歷遞歸算法深度優先遍歷非遞歸算法深度優先遍歷非遞歸算法129遞歸非遞歸利用一個棧來記錄尚待遍歷的結點，以備以后訪問棧可以將遞歸的深度優先遍歷改為非遞歸的算法。

遞歸的深度優先遍歷130深度優先遍歷非遞歸算法非遞歸先序遍歷非遞歸中序遍歷非遞歸后序遍歷非遞歸先序遍歷131算法設計（1）當前指針指向根結點；（2）打印當前結點，當前指針指向其左孩子并進棧，重復(2)，直到左孩子為NULL；（3）依次退棧，將當前指針指向右孩子；（4）若棧非空或當前指針非NULL，執行（2），否則結束。對二叉樹各結點的訪問順序是沿其左鏈一路訪問下來，在訪問結點的同時將其入棧，直到左鏈為空。然后結點出棧，對于每個出棧結點，即表示該結點和其左子樹已被訪問結束，應該訪問該結點的右子樹。非遞歸前序遍歷/*==================================函數功能：先序遍歷樹的非遞歸算法函數輸入：樹的根結點函數輸出：無屏幕輸出：樹的先序遍歷序列=========================================*/132非遞歸中序遍歷133算法設計

遇到一個結點，就把它壓入棧中，并去遍歷它的左子樹。遍歷完左子樹后，結點出棧并訪問之，然后按照它的右鏈接指示的地址再去遍歷該結點的右子樹。

非遞歸后序遍歷134

遇到一個結點，壓棧遍歷結點的左子樹遍歷結點的右子樹出棧該結點并訪問之給棧中的每個元素加上一個特征位特征為Left表示已進入該結點的左子樹，將從左子樹返回特征為Right表示已進入該結點的右子樹，將從右子樹返回

算法設計樹的遍歷程序的測試/*=========================================測試功能：樹的各種遍歷算法測試測試函數： 1.用先序遍歷的方法建立二叉鏈表CreatBTree_DLR 2.非遞歸先序遍歷序列PreOrder_NR 3.遞歸先序遍歷序列PreOrder 4.遞歸中序遍歷序列inorder 5.遞歸后序遍歷序列postorder==========================================*/1355.6樹的遍歷5.6.15.6.2樹的廣度優先遍歷樹的深度優先遍歷5.6.3樹的遍歷的應用137樹的遍歷的應用求二叉樹深度統計葉子數目138樹的遍歷的應用求二叉樹深度統計葉子數目樹的遍歷的應用139二叉樹的深度是二叉樹中結點層次的最大值。可通過先序遍歷來計算二叉樹中每個結點的層次,其中的最大值即為二叉樹的深度。求二叉樹深度求二叉樹深度2——先序遍歷法140DLR序列ABDEGHCF層數leve12334423最大高度h12334444求二叉樹深度1——先序遍歷法141按先序遍歷的方式求二叉樹深度輸入：樹的當前根結點；樹的當前根結點所處的層數leve設樹的結點指針bitree*p，樹的高度h，樹的層數leve遞歸的邊界條件：P為空結點，返回h；遞歸繼續的條件：leve增1，h取左右子樹中leve的大者

p的左孩子非空，先序遍歷p的左孩子；

p的右孩子非空，先序遍歷p的右孩子；求二叉樹深度1——先序遍歷法/*===================================================函數功能：按先序遍歷的方式求二叉樹深度函數輸入：根結點函數輸出：樹的深度屏幕輸出：（葉子結點值、層數、樹的當前高度）——方便調試用=====================================================*/142求二叉樹深度2——后序遍歷法143DLR序列DGHEBFCA左子樹高lh11122114右子樹高rh11123123求二叉樹深度2——后序遍歷法144按后序遍歷的方式求二叉樹深度輸入：樹的當前根結點；設樹的結點指針bitree*p，左子樹的高度lh，右子樹的高度rh遞歸的邊界條件：p為空結點，返回0；遞歸繼續的條件：p的左孩子非空，后序遍歷遞歸求lh；

p的右孩子非空，后序遍歷遞歸求rh；

返回左右子樹中高度值大者把左右子樹的高度分別記錄在lh、rh兩個變量中，即使它們都是局部量，但在每一層二者都是可比較的求二叉樹深度2——后序遍歷法/*================================================函數功能：按后序遍歷的方式求二叉樹深度函數輸入：根結點函數輸出：樹的深度屏幕輸出：（葉子結點值、左右子樹高度）——方便調試用================================================*/145146樹的遍歷的應用求二叉樹深度統計葉子數目樹的遍歷的應用147

利用遍歷的方式來訪問樹的各個結點，由于葉子結點的特殊性，因此可以統計出一棵樹中葉子的數目。葉子結點判斷條件：root->lchild==NULL&&root->rchild==NULL或者：!root->lchild&&!root->rchild統計葉子數目求葉子結點數1——先序遍歷法【例5-4】統計二叉樹中葉子結點的數目并打印出葉子結點的值。解：若結點root的左右指針均空，則為葉子。可選用任何一種遍歷算法查找葉子，將其統計并打印出來。

【方法一】用先序遍歷遞歸法求樹的葉子結點的數目148求葉子結點數1——先序遍歷法149/*============================================函數功能：用先序遍歷遞歸法求樹的葉子結點的數目函數輸入：二叉樹根結點函數輸出：無（通過全局量傳遞葉子結點的數目）屏幕輸出：葉子結點值=============================================*/求葉子結點數2——遞歸法150/*====================================函數功能：遞歸求樹的葉子結點的數目函數輸入：根結點地址函數輸出：葉子結點數目=======================================*/intLeafNum(BinTreeNode*root){ if(root==NULL)return(0); elseif(root->lchild==NULL&&root->rchild==NULL) return(1); elsereturn(LeafNum(root->lchild)+LeafNum(root->rchild));}

求葉子結點函數的測試/*============================================測試功能：求葉子結點的數目的測試測試函數：1.遞歸求樹的葉子結點的數目LeafNum2.用先序遍歷遞歸法求樹的葉子結點的數目LeafNum_DLR===============================================*/1515.7樹的應用5.7.15.7.2表達式樹線索二叉樹5.7.3哈夫曼樹及哈夫曼編碼樹的應用153樹基本操作擴展/限定條件樹的應用樹的應用，可以說是在樹的結構及基本操作基礎上增加各種擴展或限定條件后，形成的特定使用方法。本節介紹一些經典的應用，重點介紹哈夫曼樹。關于樹的查找的相關內容將在查找一章介紹。5.7樹的應用5.7.15.7.2表達式樹線索二叉樹5.7.3哈夫曼樹及哈夫曼編碼表達式樹155在計算機內，使用后綴表達式易于求值。表達式樹【例5-5】輸入一個算術表達式，輸出表達式的表達式樹。（假設輸入的表達式為合法表達式，判斷該表達式是否合法部分略）表達式不合法有三種情況：①左右括號不匹配；②變量名不合法；③運算符兩旁無參與運算的變量或數。156表達式樹【例5-5】輸入一個算術表達式，輸出表達式的表達式樹。157①設數組ex存放表達式串的各字符，lt、rt作為結點的左右指針，變量left、right用于存放每次取字符范圍的左、右界。②設置左界初值為1；右界初值為串長度。③判斷左右括號是否匹配，不匹配則認為輸入有錯誤。④在表達式的左右界范圍內尋找運算級別最低的運算符，同時判斷運算符兩旁有否參與運算的變量或數。若無，則輸入表達式不合法；若有，作為當前子樹的根結點，設置左子樹指針及其左右界值，設置右子樹指針及其左右界值。⑤若表達式在左右界范圍內無運算符，則為葉子結點，判斷變量名或數是否合法。⑥轉④，直到表達式字符取完為止。5.7樹的應用5.7.15.7.2表達式樹線索二叉樹5.7.3哈夫曼樹及哈夫曼編碼問題引入159遞歸方法借助棧的非遞歸方法二叉樹遍歷方法二者本質都要用棧問題引入160相比遞歸模式的二叉樹運算，非遞歸模式具有更廣泛的應用面。“少跳轉、無堆棧、非遞歸”時間空間受限的系統如嵌入式系統或片上系統對算法的要求嵌入式系統完全嵌入受控器件內部的、為特定應用或專門用途而設計的專用計算機系統。片上系統：將一個完整的系統（產品）的各個功能集成在一個芯片上或一組芯片上。傳統的與數據結構相關的算法，大多面向軟件層面的需求，較少顧及硬件層面的考慮。隨著硬件體系結構的擴展及其開發技術的發展，尤其是近年來可重構計算系統的迅速發展，“硬件的軟化”、“軟件的硬化”以及“芯片級程序設計技術”等成為當代程序與算法設計的—個重要方向，硬件系統設計已經不可避免地涉及到了數據結構的基本問題。二叉樹結點前趨后繼的查找問題161“前趨后繼關系”基于樹遍歷的結果而言“雙親孩子關系”基于樹結構定義而言遍歷二叉樹的結果是:求得結點的一個線性序列。二叉樹結點關系二叉樹結點前趨后繼的查找問題162

采用樹的線性存儲方式解決結點的前趨或后繼的查找，有什么問題？在二叉鏈表中查找結點的前趨后繼方便嗎？二叉鏈表線索化的實現163【方案一】增加前趨后繼指針域可以增加二叉鏈表結點中的指針域來存放前趨和后繼結點信息，其中Lthread表示前趨結點的地址，Rthread表示后繼結點的地址。二叉鏈表線索化討論164結點前趨左孩子右孩子后繼A空BDBBA空CCCB空空DDC空EEEDF空FFE空空空前趨、后繼線索與孩子指針的信息是否有重復的地方？增加兩個指針域記錄前趨后繼先序遍歷中，結點的孩子或者沒有，或者與后繼是一樣的————可以考慮利用原結點的指針域來存儲前趨、后繼的線索。二叉鏈表線索化討論165利用原結點的指針域的方案是否能區分孩子還是線索？無法區分用空鏈域記錄前趨/后繼的位置ADECBF【方案二】利用原結點的指針域二叉鏈表線索化討論166改進的方案利用原結點的指針域的方案是否能保證所有前趨的線索都被記錄？存在結點有左孩子而無法記錄其前趨的狀況，如結點E，其前趨D的地址沒有指針域記錄，但對于先序遍歷而言，只要有結點的后繼線索即可，因此，前趨線索有“中斷”不影響先序遍歷的操作。167線索二叉樹二叉樹添加了直接指向結點的前趨和后繼的指針的二叉樹稱為線索二叉樹。線索二叉樹根據線索內容的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。線索二叉樹168結點的標志Ltag與Rtag用來標示相應的指針域存儲的是線索或孩子線索二叉樹【例5-6】畫出圖中二叉樹的中序二叉鏈表和中序線索二叉樹。解：求出二叉樹的中序遍歷序列為BCADFE（1）按照二叉樹的形狀，畫出二叉鏈表；（2）按照線索二叉樹結點定義，畫出線索域的指向；169線索二叉樹170如何在線索二叉樹的遍歷序列中找結點的前趨和后繼結點？BCADFE前趨標志110110前趨空B左子樹最后結點CAD左子樹最后結點F后繼標志010011后繼右子樹最左結點CA右子樹最左結點D右子樹最左結點FE空右線索標志為1：右孩子為后繼右線索標志為0：右子樹最左結點為后繼右子樹最左結點：中序遍歷右子樹時訪問的第一個結點左線索標志為1，左孩子為前趨左線索標志為0，左子樹最右結點為前趨左子樹最右結點：中序遍歷左子樹時訪問的最后一個結點由線索二叉樹得到遍歷序列的方法171由中序遍歷線索二叉樹得到中序遍歷序列的方法：訪問根結點找根的前趨序列找根的后繼序列由先序遍歷線索二叉樹得到先序遍歷序列的方法：訪問根結點找根的后繼序列由后序遍歷線索二叉樹得到后序遍歷序列的方法：訪問根結點找根的前趨序列線索化方法172線索化的過程——在遍歷過程中修改空指針在遍歷過程中將二叉樹線索化5.7樹的應用5.7.15.7.2表達式樹線索二叉樹5.7.3哈夫曼樹及哈夫曼編碼通信中的編碼問題174數字通信系統模型信息發布者信息接收者信源編碼——將信源發出的消息符號轉換為適合信道傳輸的符號。信源譯碼——按照編碼的逆過程，將信息還原為原來的形式。二元信道(常用)等長二元編碼設計175【例5-7】等長二元編碼設計設一個信源符號集只有A、B、C、D四種字符，為區分不同的字符，設每個字符需要的二進制編碼位數為n：∵4=2n∴n=2所謂數據編碼就是數據與二進制字符串的轉換等長編碼問題討論176在實際應用中，有些字母（如e,s,t）出現頻率很高，有些字母出現頻率很低。如果對所有字母重新編碼，用比較少的bit表示出現次數高的字母，用比較多的bit表示出現次數低的字母，這樣就應該可以用比較小的儲存空間存相同的信息，使得總的報文碼長縮短，提高通信效率。已知電文中出現的一組字符及出現頻率，試為該組字符編碼以使得電文總長最短。等長編碼的效率如何？不等長二元編碼設計177譯碼結果不唯一，原因是什么？【例5-8】不等長二元編碼設計譯碼結果討論178譯碼具有唯一性的必要條件——任一個字符的編碼都不是另一個字符的編碼的前綴譯碼樹譯碼問題是一個字符串的查找問題，即串的多模式匹配問題字符結點不能出現分支結點上譯碼結果討論179哈夫曼編碼哈夫曼樹180哈夫曼樹與哈夫曼編碼哈夫曼樹的概念哈夫曼樹構造算法哈夫曼樹的算法實現哈夫曼編碼哈夫曼樹的譯碼哈夫曼樹的應用181哈夫曼樹與哈夫曼編碼哈夫曼樹的概念哈夫曼樹構造算法哈夫曼樹的算法實現哈夫曼編碼哈夫曼樹的譯碼哈夫曼樹的應用哈夫曼樹的概念182DCAB4752路徑

結點的權

結點的帶權路徑長度樹的帶權路徑長度

(WeightedPathLength)從一個結點到另一個結點之間的若干個分支具有一定含義的比例系數。如“詞頻”路徑長度

路徑上的分支數目稱為路徑長度結點的路徑長度

從根到該結點的路徑長度從根到該結點的路徑長度與該結點權的乘積n——葉子結點的數目Wi——第i個葉結點的權值，i=1,2,...nLi——第i個葉結點的路徑長度，i=1,2,...n哈夫曼樹183DCAB4752CDAB4752

用n（n>0）個帶權值的葉子來構造二叉樹，限定二叉樹中除了這n個葉子外只能出現度為2的結點，那么符合這樣條件的二叉樹往往可構造出許多棵，其中帶權路徑長度最小的二叉樹就是哈夫曼樹或最優二叉樹。哈夫曼樹哈夫曼樹184185哈夫曼樹與哈夫曼編碼哈夫曼樹的概念哈夫曼樹構造算法哈夫曼樹的算法實現哈夫曼編碼哈夫曼樹的譯碼哈夫曼樹的應用哈夫曼樹的構造186【例5-9】構造哈夫曼樹構造以W=（6，5，3，4）為權的哈夫曼樹，和構造以W=（7，2，4，5）為權的哈夫曼樹。187哈夫曼樹與哈夫曼編碼哈夫曼樹的概念哈夫曼樹構造算法哈夫曼樹的算法實現哈夫曼編碼哈夫曼樹的譯碼哈夫曼樹的應用哈夫曼樹的算法實現188typedefstruct //結點結構體{chardata; //結點值intweight; //權值intparent; //雙親結點intlchild; //左孩子結點intrchild; //右孩子結點}HTree_Node;數據結構設計Weightparentlchildrchild哈夫曼樹表結構哈夫曼樹的算法實現189函數框架設計功能描述輸入輸出構造Huffman樹n個權值哈夫曼樹函數名形參函數類型/*=======================================函數功能：創建哈夫曼樹函數輸入：（哈夫曼樹）函數輸出：（哈夫曼樹）=========================================*/哈夫曼樹的構造算法190191哈夫曼樹與哈夫曼編碼哈夫曼樹的概念哈夫曼樹構造算法哈夫曼樹的算法實現哈夫曼編碼哈夫曼樹的譯碼哈夫曼樹的應用哈夫曼編碼192在已建立的哈夫曼樹中，沿葉子結點的雙親路徑回退到根結點，每回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結點到相應葉結點所經過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。

若規定哈夫曼樹中的左分支代表0，右分支代表1；則從根結點到每個葉結點所經過的路徑分支組成的0和1的序列便為該結點對應字符的編碼。哈夫曼編碼方法哈夫曼編碼193從葉子結點L開始，找其雙親F，根據F判斷L是F的左孩子還是右孩子左孩子：編碼為0（or1）右孩子：編碼為1（or0）設L=F，重復上述過程，直到A為根結點(得到的編碼是從低位到高位)哈夫曼編碼194在已建立的哈夫曼樹中，沿葉子結點的雙親路徑回退到根結點，每回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結點到相應葉結點所經過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。哈夫曼編碼/*==========================================函數功能：哈夫曼符號集編碼函數輸入：哈夫曼樹、（哈夫曼碼編碼表）函數輸出：（哈夫曼編碼表）=============================================*/195196哈夫曼樹與哈夫曼編碼哈夫曼樹的概念哈夫曼樹構造算法哈夫曼樹的算法實現哈夫曼編碼哈夫曼樹的譯碼哈夫曼樹的應用哈夫曼樹的譯碼197

從哈夫曼樹根開始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達葉子結點，則譯出一個字符；再重新從根出發，直到電文結束。哈夫曼譯碼方法哈夫曼樹的譯碼198從根結點A開始，根據電文找其孩子B：編碼為0，B為左孩子；編碼為1，B為右孩子。設B=A重復以上過程，直到B為葉子結點。哈夫曼樹的譯碼——程序199/*====================================函數功能：將哈夫曼碼翻譯為字符函數輸入：哈夫曼樹、哈夫曼編碼函數輸出：無======================================*/哈夫曼樹的譯碼——測試程序/*=======================================函數功能：輸出哈夫曼編碼表函數輸入：哈夫曼樹、哈夫曼碼編碼表函數輸出：（哈夫曼碼編碼表）屏幕輸出：哈夫曼樹、哈夫曼碼編碼表=========================================*/200哈夫曼樹的譯碼——測試程序/*============================================

函數功能：對給定字符串進行編碼

函數輸入：哈夫曼樹、哈夫曼碼編碼表

函數輸出：無

鍵盤輸入：要編碼的字符串

屏幕輸出：輸入字符串的哈夫曼編碼串===============================================*/201202哈夫曼樹與哈夫曼編碼哈夫曼樹的概念哈夫曼樹構造算法哈夫曼樹的算法實現哈夫曼編碼哈夫曼樹的譯碼哈夫曼樹的應用哈夫曼樹應用舉例——最佳判定算法203【例5-10】哈夫曼樹的應用——最佳判定算法編制一個程序，將百分制轉換成優秀、良好、中等、及格、不及格5個等級輸出。哈夫曼樹應用舉例——最佳判定算法204這樣的轉換效率高不高？有80%的數據需要進行三次或三次以上的比較才能得出結果思考&討論哈夫曼樹應用舉例——最佳判定算法205這樣的改進，算法效率真的提高了么？每個結點的比較次數增加了哈夫曼樹應用舉例——最佳判定算法206605.8廣義表5.8.15.8.2廣義表的定義廣義表的存儲5.8.3廣義表的基本運算你去過哪里旅游？208形式1：國家(直轄市，省(城市1，城市2，...城市n))形式2：洲名(國家(城市1，城市2，...城市n))包含子結構的線性結構，線性表的推廣——廣義表中國(

北京,上海,

江蘇(南京,蘇州),

浙江(杭州，寧波)，

陜西(西安，咸陽，寶雞))歐洲(

荷蘭(阿姆斯特丹，埃因霍溫)，

比利時(布魯塞爾)，

法國(巴黎)，

英國(倫敦))線性表及相關形式2095.8廣義表5.8.15.8.2廣義表的定義廣義表的存儲5.8.3廣義表的基本運算廣義表定義211說明：

廣義表名——LS

表頭——廣義表LS非空時，稱第一個元素為LS的表頭。

表尾——廣義表LS中除表頭外其余元素組成的廣義表。

長度——廣義表LS中的直接元素的個數。

深度——廣義表LS中括號的最大嵌套層數。原子的深度為0，空表的深度為1。

單元素——ai可以是單個的數據元素，單元素也稱為原子，是指結構上不可再分的一個數或一個結構。

子表——ai可以是一個廣義表。

廣義表是n（n≥0）個數據元素的有限序列，記作：LS=(a1，a2，……，an)廣義表廣義表特性1）廣義表是一個多層次的結構。因為廣義表的元素可以是一個子表，而子表的元素還可以是子表。2）一個廣義表可以為其他廣義表共享，這種共享廣義表稱為再入表；3）廣義表可以是一個遞歸的表。一個廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無窮值,長度是有限值；4）廣義表與樹形結構相對應，這個廣義表就是純表。廣義表是對線性表和樹的推廣。各種表的關系如下：線性表∈純表（樹）∈再入表∈遞歸表

212廣義表表示法1213不帶名字的廣義表表示廣義表表示法2214帶名字的廣義表表示廣義表表示示例215廣義表常用表示等價寫法帶名字的表示法表長原子子表說明E=()E()0無無E為空表L=(a，b)L(a，b)2a，b無L也是線性表A=(x，L)A=(x，(a，b))A(x，L(a，b))2xLB=(A，y)B=((x，(a，b))，y)B(A(x，L(a，b))，y)2yAC=(A，B)C=((x,(a,b)),((x,(a,b)),y))C(A(x，l(a，b))，B(A(x，L(a，b))，y))2無A,BD=(a，D)D=(a，(a，(a，(…))))D(a，D(a，D(…)))2aDD為遞歸表廣義表的圖形表示216廣義表與其他數據結構的關系217（1）與線性表的關系當限定廣義表的每一項只能是基本元素而非子表時，廣義表就退化為線性表：(a1,a2,…,an)；（2）與二維數組的關系當將數組的每行（或每列）看作為子表時，數組即為一個廣義表：((a11,a12,…,a1n),(a21,a22,…,a2n),…(an1,an2,…,ann))（3）與樹的關系樹也可以用廣義表來表示。廣義表的運算定義218創建廣義表輸出廣義表求廣義表的長度和深度從廣義表中查找或刪除元素5.8廣義表5.8.15.8.2廣義表的定義廣義表的存儲5.8.3廣義表的基本運算廣義表鏈式存儲結構設計220廣義表頭尾表示法1——表頭表尾分析法221廣義表頭尾表示法2——子表分析法222廣義表表示法——兄弟孩子表示法223一棵樹采用孩子兄弟表示法所建立的存儲結構與它所對應的二叉樹的二叉鏈表存儲結構是完全相同的，在廣義表鏈式存儲中，通常把此種存儲方式稱為“孩子兄弟表示法”224廣義表頭尾表示法結點設計表頭指針hPtr：子表首結點的地址后繼指針tPtr：存放同層后繼結點鏈接地址標志tag——區分表結點和元素結點的標志；元素值data——存放原子的值。頭尾表示法結點類型描述typedefenum{ATOM,LIST}ElemTag;

//ATOM==0:原子,LIST==1:子表TypedefstructGLNode{ElemTagtag;//標志域union

{AtomTypedata;struct{structGLNode*hPtr,*tPtr;}ptr;};}Glist;225226【例5-11】用表頭表尾分解法給出廣義表E=(a,(b,c,d))的鏈表存儲形式圖表頭表尾分解法子表分解法227【例5-12】子表分解法給出廣義表L=(a,(x,y),((z)))的鏈表存儲形式圖。廣義表的孩子兄弟表示法228typedefenum{ATOM,LIST}ElemTag; //ATOM=0：單元素；LIST=1：子表typedefstructGLENode{ElemTagtag; //標志域，用于區分原子結點和表結點union{ //原子結點和表結點的聯合部分AtomTypedata; //原子結點的值域structGLENode*firstchildPtr; //表結點的表頭指針};structGLENode*siblingPtr; //指向下一個結點}GList //廣義表類型廣義表的孩子兄弟表示法229【例5-13】用孩子兄弟表示法表示下列各廣義表的存儲空表： A=()線性表： L=(a,b,c,d)純表： D=(a,(b,c))純表： D=(A,B,C)=((),(e),(a,(b,c)))再入表： G(d,L(a,b),T(c,L(a,b)))遞歸表： E=(a,E)230本章小結231樹存儲結構基本概念基本操作連續存儲鏈式存儲構造、查找插入、刪除遍歷、求深度等樹的定義、表示形式相關術語：結點、孩子、祖先、子孫、層數、高度、結點的度、有序樹、無序樹邏輯特征分層非線性結構特例情形：二叉樹本章小結232二叉樹相關概念運算—遍歷二叉樹的定義特例：滿二叉樹、完全二叉樹基本性質：結點、深度、層數等之間的關系廣度優先深度優先遍歷應用求深度統計葉子數目先序遍歷中序遍歷后序遍歷運算—應用表達式樹線索二叉樹哈夫曼樹與哈夫曼編碼本章小結233樹中有子樹按層級排列前后輩分等級森嚴不能亂，二叉樹形態最簡，專門把它的特性仔細研：順序表存結點聯系隱藏在下標位里面；二叉鏈表很形象，分支結構聯系記錄在左右孩子域中間。

借隊列建鏈表，線性結構把非線性關系存里邊，樹結點逐個出隊，添加指針域，二叉鏈表即展現。

樹的結構為遞歸，操作處理有方案兩類：按層橫向處理基于順序表的結構上看，自根沿路徑縱向處理基于鏈表按遞歸辦，先中后序三遍歷將左右孩子與根遞歸地把每個結點都只跑一遍。

本章小結234

樹的應用介紹哈夫曼編碼是重點。哈夫曼樹帶權路徑長度為最小，設計異前綴編碼方法巧妙堪經典。哈夫曼樹構造方法，找結點權值最小次小加起來為根逐步完善，左分支為0，右分支為1做好標記，根到葉沿途的各01連起來即是葉上字符的編碼串。發送的信息傳輸前要將報文按字符編碼寫成01的序列串，通過有線或無線傳遞到接收的一端，天書般的報文1001串組成其意難辨，

要譯碼到哈夫曼樹上，從根開始沿著路徑逐個兒分辨，遇0左拐遇1右轉，千回百轉直到葉子上破譯的字符展現。（注：哈夫曼編碼中，左分支為0，則右分支為1；或者左分支為1，右分支為0；兩種方案都可以）

本章小結235

樹中有樹是遞歸的樹，表中有表為廣義的表；廣義表含義廣泛，把線性非線性各種關系統統包含，頭尾法兄弟孩子法描述紛繁的結點聯系真不簡單。元素有原子與子表兩類，類型大不同，存儲起來可是有點麻煩，用標記巧區分，結點結構設計統一在union中間。

結點邏輯關系任意的非線性結構圖Chapter

6DataStructuresandAlgorithmAnalysis主要內容圖的邏輯結構定義圖的存儲結構圖的遍歷圖的應用學習目標 熟練掌握圖的邏輯結構特點 掌握圖的存儲結構 掌握圖的遍歷 熟悉圖的相關應用實際問題中的圖及抽象圖的邏輯結構圖的存儲結構及實現圖的基本操作圖的遍歷圖中的樹問題圖中的最短路徑問題活動頂點與活動邊的問題CONTENTS6.16.26.36.46.56.66.76.8實際問題中的圖及抽象圖的邏輯結構圖的存儲結構及實現圖的基本操作圖的遍歷圖中的樹問題圖中的最短路徑問題活動頂點與活動邊的問題CONTENTS6.16.26.36.46.56.66.76.86.1實際問題中的圖及抽象幾何圖與拓撲圖242所有多邊形和圓周在拓撲意義下是一樣的圓和方形、三角形的形狀、大小不同，在拓撲變換下，它們都是等價圖形。幾何圖與拓撲圖243圖引例1——地圖染色問題24431232334四色猜想

四色定理1852年英國人發現現象1976年美國人計算機證明每幅地圖都最多可以用四種顏色著色圖引例1——地圖染色問題245圖引例1——地圖染色問題246信息與信息間的聯系如何抽象后存儲到計算機中陜西河南安徽湖北四川山西貴州湖南廣東廣西福建浙江江西江蘇山東圖引例2——搜索引擎與網站的結構247搜索引擎的工作原理是按照一定的搜索策略搜索網絡并搜集信息，在對信息進行組織和處理后存儲在自己的數據庫中，以便為用戶提供快速檢索服務。完成網絡信息搜索任務的軟件俗稱“網絡蜘蛛”或“網絡爬蟲”，網絡蜘蛛是通過網站的站內鏈接來遍歷網站內容的。網站內鏈接結構圖引例2——搜索引擎與網站的結構248（a）網站鏈接（b）網站間的鏈接抽象圖引例2——搜索引擎與網站的結構249拓撲意義上的圖用點表示對象，有直接聯系的對象用線連接起來。圖形中連線的長短曲直和結點的位置無關緊要，每一條線兩端都有結點。

從實際問題中抽象出來的數據結構的“圖”有什么特點？圖引例3——最短航線問題250航線圖城市：頂點={a,b,c,d,e}航線：頂點間連線={ab,ad,bc,be,de}問題描述：求出從d到c的最短航線。圖引例4——電路圖的表示方法251無向圖和有向圖把電路中每一條支路畫成抽象的線段形成的一個結點和支路的集合，見圖6.10，其中沒有考慮電流方向的圖為無向圖，有向圖的方向一般為該支路電流的參考方向圖的討論【思考與討論】從實際問題中抽象出來的數據結構的“圖”有什么特點？討論：數據結構中的圖是拓撲意義上的圖，其特點為：

用點表示對象，有直接聯系的對象用線連接起來。

圖形中連線的長短曲直和結點的位置無關緊要，每一條線兩端都有結點。252實際問題中的圖及抽象圖的邏輯結構圖的存儲結構及實現圖的基本操作圖的遍歷圖中的樹問題圖中的最短路徑問題活動頂點與活動邊的問題CONTENT