數(shù)據(jù)結(jié)構(gòu)與算法分析新視角（第2版） 課件 周幸妮 第5-9章 樹-經(jīng)典算法

數(shù)據(jù)結(jié)構(gòu)與算法分析

新視角

結(jié)點(diǎn)邏輯關(guān)系分層次的非線性結(jié)構(gòu)樹Chapter

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

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

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

i/2

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

∴1～10層全滿，k=10最下層葉子結(jié)點(diǎn)的個(gè)數(shù)=n-（2k

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

刪除在指定位置插入/刪除結(jié)點(diǎn)遍歷

對(duì)樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)求深度計(jì)算樹的高度實(shí)際問(wèn)題中的樹及抽象樹的邏輯結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)樹的遍歷樹的應(yīng)用廣義表*CONTENTS5.15.25.35.45.55.65.75.8普通樹二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)已討論過(guò)一般形式樹的存儲(chǔ)方案簡(jiǎn)化對(duì)照樹的一般形式來(lái)討論二叉樹的存儲(chǔ)方案5.5二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)5.5.15.5.2二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)5.5.3建立動(dòng)態(tài)二叉鏈表二叉樹順序存儲(chǔ)——結(jié)點(diǎn)間關(guān)系分析68二叉樹順序存儲(chǔ)——結(jié)點(diǎn)間關(guān)系分析69二叉樹順序存儲(chǔ)——結(jié)點(diǎn)位置分析70二叉樹順序存儲(chǔ)——結(jié)點(diǎn)位置分析71完全二叉樹存儲(chǔ)方案是否適用一般的二叉樹存儲(chǔ)？將二叉樹的所有結(jié)點(diǎn)，按照完全二叉樹的編號(hào)方法進(jìn)行編號(hào)，按序存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。結(jié)點(diǎn)的順序?qū)⒎从吵鼋Y(jié)點(diǎn)之間邏輯關(guān)系。二叉樹的順序存儲(chǔ)思考&討論二叉樹順序存儲(chǔ)——結(jié)點(diǎn)位置分析72退化的二叉樹的存儲(chǔ)5.5二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)5.5.15.5.2二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)5.5.3建立動(dòng)態(tài)二叉鏈表二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)74

二叉樹的每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域來(lái)分別指向相應(yīng)的分支，稱其為二叉鏈表二叉鏈表二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)75二叉樹的每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域來(lái)分別指向相應(yīng)的分支。二叉樹的鏈?zhǔn)酱鎯?chǔ)二叉樹的三叉鏈存儲(chǔ)結(jié)構(gòu)76樹的三重鏈表表示77靜態(tài)二叉鏈表78ADBCFE021435孩子結(jié)點(diǎn)在數(shù)組中的位置。用-1表示無(wú)左孩子或右孩子采用數(shù)組存儲(chǔ)的靜態(tài)二叉鏈表5.5二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)5.5.15.5.2二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)5.5.3建立動(dòng)態(tài)二叉鏈表層次輸入法創(chuàng)建二叉鏈表方法一80層次輸入法創(chuàng)建二叉鏈表方法一81

Q隊(duì)列元素A出列，A的下標(biāo)i=1

將A的左孩子結(jié)點(diǎn)地址（在下標(biāo)為2*i處）填入A結(jié)點(diǎn)的左指針域

將A的右孩子結(jié)點(diǎn)地址（在下標(biāo)為2*i+1處）填入A結(jié)點(diǎn)的右指針域?qū)哟屋斎敕▌?chuàng)建二叉鏈表方法一82

Q隊(duì)列元素A出列，A的下標(biāo)i=1

將A的左孩子結(jié)點(diǎn)地址（在下標(biāo)為2*i處）填入A結(jié)點(diǎn)的左指針域

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

Q隊(duì)列元素i出列將i的左孩子結(jié)點(diǎn)地址(下標(biāo)2*i）填入i的左指針域?qū)的右孩子結(jié)點(diǎn)地址(下標(biāo)2*i+1的結(jié)點(diǎn)）填入i的右指針域返回根結(jié)點(diǎn)地址層次輸入法創(chuàng)建二叉鏈表方法二84

輸入結(jié)點(diǎn)信息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個(gè)新結(jié)點(diǎn)。若新結(jié)點(diǎn)是第1個(gè)結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)，否則將新結(jié)點(diǎn)作為孩子鏈接到它的雙親結(jié)點(diǎn)上。如此反復(fù)進(jìn)行，直到輸入結(jié)束標(biāo)志“＃”為止層次輸入法創(chuàng)建二叉鏈表方法二85

輸入結(jié)點(diǎn)信息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個(gè)新結(jié)點(diǎn)。若新結(jié)點(diǎn)是第1個(gè)結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)，否則將新結(jié)點(diǎn)作為孩子鏈接到它的雙親結(jié)點(diǎn)上。如此反復(fù)進(jìn)行，直到輸入結(jié)束標(biāo)志“?！睘橹?6層次輸入法創(chuàng)建二叉鏈表方法二偽代碼細(xì)化描述設(shè)二叉樹的深度為k，則隊(duì)列Q的長(zhǎng)度設(shè)置按完全二叉樹編號(hào)至樹的最后一個(gè)結(jié)點(diǎn)當(dāng)輸入結(jié)點(diǎn)信息不是結(jié)束標(biāo)志‘#’若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個(gè)新結(jié)點(diǎn)并入隊(duì)若新結(jié)點(diǎn)是第1個(gè)結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)，否則將新結(jié)點(diǎn)作為孩子鏈接到它的雙親結(jié)點(diǎn)上。若新結(jié)點(diǎn)是雙親結(jié)點(diǎn)的右孩子，則雙親結(jié)點(diǎn)出隊(duì)。返回根結(jié)點(diǎn)地址87層次輸入法創(chuàng)建二叉鏈表方法二功能描述輸入輸出CreaTree無(wú)根地址函數(shù)名形參函數(shù)類型

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)函數(shù)框架設(shè)計(jì)層次輸入法創(chuàng)建二叉鏈表方法二/*===============================================函數(shù)功能：層次輸入法創(chuàng)建二叉鏈表函數(shù)輸入：無(wú)函數(shù)輸出：二叉鏈表根結(jié)點(diǎn)鍵盤輸入：按完全二叉樹結(jié)點(diǎn)編號(hào)規(guī)則順序輸入結(jié)點(diǎn)值，空結(jié)點(diǎn)為@====================================================*/885.6樹的遍歷5.6.15.6.2樹的廣度優(yōu)先遍歷樹的深度優(yōu)先遍歷5.6.3樹的遍歷的應(yīng)用引例1——機(jī)電設(shè)備通電自檢模型90設(shè)備通電自檢步驟應(yīng)該如何進(jìn)行檢測(cè)步驟：左子樹：網(wǎng)卡等正常→PCI正?！@卡等正常→非PCI正?！蹇ㄕＳ易訕洌河脖P等正常→外存正?！I盤等正常→其他正?！前蹇ㄕＵ脴洌喊蹇ㄕ！前蹇ㄕ！?jì)算機(jī)正常在上述的檢測(cè)過(guò)程中，“后序遍歷”的意思是指樹的根結(jié)點(diǎn)是最后被訪問(wèn)到的，無(wú)論是整棵樹還是左右子樹?！昂笮虮闅v”引例2——網(wǎng)購(gòu)商品的管理91FoodMeatPorkBeefFruitYellowBananMangoRedCherry如何打印商品清單“先序遍歷”根結(jié)點(diǎn)：Food左子樹：Meat→Pork/Beef右子樹：Fruit→（左子樹）Yellow→Banan/MangoFruit→（右子樹）Red→Cherry引例3——樹中結(jié)點(diǎn)的快速查找策略92“中序遍歷”如何得到有序序列？二分查找遞歸過(guò)程根為1的樹：左子樹（空）→根1→右子樹（2）→結(jié)果為1、2根為3的樹：左子樹（1,2）→根3→右子樹（4,5）→結(jié)果為1、2、3、4、5根為9的樹：左子樹（7,8）→根9→右子樹（10,11）→結(jié)果為7、8、9、10、1193遍歷的基本概念對(duì)結(jié)點(diǎn)的處理。如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。

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

基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹廣度優(yōu)先遍歷97基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹廣度優(yōu)先遍歷98(1)初始化一個(gè)隊(duì)列，并把根結(jié)點(diǎn)入列隊(duì)；

(2)隊(duì)列元素出隊(duì)，取得一個(gè)結(jié)點(diǎn)，訪問(wèn)該結(jié)點(diǎn)；

(3)若該結(jié)點(diǎn)的左孩子非空，則將該結(jié)點(diǎn)的左子樹入隊(duì)列；

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

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

117深度優(yōu)先遍歷遞歸算法118深度優(yōu)先遍歷方法深度優(yōu)先遍歷遞歸算法深度優(yōu)先遍歷非遞歸算法先序遍歷的遞歸算法119功能描述輸入輸出輸出DLR遍歷序列PreOrder根地址無(wú)函數(shù)名形參函數(shù)類型偽代碼描述輸入：樹的當(dāng)前根結(jié)點(diǎn)t；設(shè)樹的結(jié)點(diǎn)指針bitree*t遞歸的邊界條件：t為空結(jié)點(diǎn)，返回；遞歸繼續(xù)的條件：訪問(wèn)t結(jié)點(diǎn)；

前序遍歷t的左子樹；

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

函數(shù)功能：后序遍歷樹的遞歸算法

函數(shù)輸入：樹的根結(jié)點(diǎn)

函數(shù)輸出：無(wú)

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

{

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

遞歸的深度優(yōu)先遍歷130深度優(yōu)先遍歷非遞歸算法非遞歸先序遍歷非遞歸中序遍歷非遞歸后序遍歷非遞歸先序遍歷131算法設(shè)計(jì)（1）當(dāng)前指針指向根結(jié)點(diǎn)；（2）打印當(dāng)前結(jié)點(diǎn)，當(dāng)前指針指向其左孩子并進(jìn)棧，重復(fù)(2)，直到左孩子為NULL；（3）依次退棧，將當(dāng)前指針指向右孩子；（4）若棧非空或當(dāng)前指針?lè)荖ULL，執(zhí)行（2），否則結(jié)束。對(duì)二叉樹各結(jié)點(diǎn)的訪問(wèn)順序是沿其左鏈一路訪問(wèn)下來(lái)，在訪問(wèn)結(jié)點(diǎn)的同時(shí)將其入棧，直到左鏈為空。然后結(jié)點(diǎn)出棧，對(duì)于每個(gè)出棧結(jié)點(diǎn)，即表示該結(jié)點(diǎn)和其左子樹已被訪問(wèn)結(jié)束，應(yīng)該訪問(wèn)該結(jié)點(diǎn)的右子樹。非遞歸前序遍歷/*==================================函數(shù)功能：先序遍歷樹的非遞歸算法函數(shù)輸入：樹的根結(jié)點(diǎn)函數(shù)輸出：無(wú)屏幕輸出：樹的先序遍歷序列=========================================*/132非遞歸中序遍歷133算法設(shè)計(jì)

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

非遞歸后序遍歷134

遇到一個(gè)結(jié)點(diǎn)，壓棧遍歷結(jié)點(diǎn)的左子樹遍歷結(jié)點(diǎn)的右子樹出棧該結(jié)點(diǎn)并訪問(wèn)之給棧中的每個(gè)元素加上一個(gè)特征位特征為L(zhǎng)eft表示已進(jìn)入該結(jié)點(diǎn)的左子樹，將從左子樹返回特征為Right表示已進(jìn)入該結(jié)點(diǎn)的右子樹，將從右子樹返回

算法設(shè)計(jì)樹的遍歷程序的測(cè)試/*=========================================測(cè)試功能：樹的各種遍歷算法測(cè)試測(cè)試函數(shù)： 1.用先序遍歷的方法建立二叉鏈表CreatBTree_DLR 2.非遞歸先序遍歷序列PreOrder_NR 3.遞歸先序遍歷序列PreOrder 4.遞歸中序遍歷序列inorder 5.遞歸后序遍歷序列postorder==========================================*/1355.6樹的遍歷5.6.15.6.2樹的廣度優(yōu)先遍歷樹的深度優(yōu)先遍歷5.6.3樹的遍歷的應(yīng)用137樹的遍歷的應(yīng)用求二叉樹深度統(tǒng)計(jì)葉子數(shù)目138樹的遍歷的應(yīng)用求二叉樹深度統(tǒng)計(jì)葉子數(shù)目樹的遍歷的應(yīng)用139二叉樹的深度是二叉樹中結(jié)點(diǎn)層次的最大值?？赏ㄟ^(guò)先序遍歷來(lái)計(jì)算二叉樹中每個(gè)結(jié)點(diǎn)的層次,其中的最大值即為二叉樹的深度。求二叉樹深度求二叉樹深度2——先序遍歷法140DLR序列ABDEGHCF層數(shù)leve12334423最大高度h12334444求二叉樹深度1——先序遍歷法141按先序遍歷的方式求二叉樹深度輸入：樹的當(dāng)前根結(jié)點(diǎn)；樹的當(dāng)前根結(jié)點(diǎn)所處的層數(shù)leve設(shè)樹的結(jié)點(diǎn)指針bitree*p，樹的高度h，樹的層數(shù)leve遞歸的邊界條件：P為空結(jié)點(diǎn)，返回h；遞歸繼續(xù)的條件：leve增1，h取左右子樹中l(wèi)eve的大者

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

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

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

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

利用遍歷的方式來(lái)訪問(wèn)樹的各個(gè)結(jié)點(diǎn)，由于葉子結(jié)點(diǎn)的特殊性，因此可以統(tǒng)計(jì)出一棵樹中葉子的數(shù)目。葉子結(jié)點(diǎn)判斷條件：root->lchild==NULL&&root->rchild==NULL或者：!root->lchild&&!root->rchild統(tǒng)計(jì)葉子數(shù)目求葉子結(jié)點(diǎn)數(shù)1——先序遍歷法【例5-4】統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的數(shù)目并打印出葉子結(jié)點(diǎn)的值。解：若結(jié)點(diǎn)root的左右指針均空，則為葉子?？蛇x用任何一種遍歷算法查找葉子，將其統(tǒng)計(jì)并打印出來(lái)。

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

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

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

結(jié)點(diǎn)的權(quán)

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

(WeightedPathLength)從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的若干個(gè)分支具有一定含義的比例系數(shù)。如“詞頻”路徑長(zhǎng)度

路徑上的分支數(shù)目稱為路徑長(zhǎng)度結(jié)點(diǎn)的路徑長(zhǎng)度

從根到該結(jié)點(diǎn)的路徑長(zhǎng)度從根到該結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積n——葉子結(jié)點(diǎn)的數(shù)目Wi——第i個(gè)葉結(jié)點(diǎn)的權(quán)值，i=1,2,...nLi——第i個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度，i=1,2,...n哈夫曼樹183DCAB4752CDAB4752

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

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

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

函數(shù)功能：對(duì)給定字符串進(jìn)行編碼

函數(shù)輸入：哈夫曼樹、哈夫曼碼編碼表

函數(shù)輸出：無(wú)

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

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

北京,上海,

江蘇(南京,蘇州),

浙江(杭州，寧波)，

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

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

比利時(shí)(布魯塞爾)，

法國(guó)(巴黎)，

英國(guó)(倫敦))線性表及相關(guān)形式2095.8廣義表5.8.15.8.2廣義表的定義廣義表的存儲(chǔ)5.8.3廣義表的基本運(yùn)算廣義表定義211說(shuō)明：

廣義表名——LS

表頭——廣義表LS非空時(shí)，稱第一個(gè)元素為L(zhǎng)S的表頭。

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

長(zhǎng)度——廣義表LS中的直接元素的個(gè)數(shù)。

深度——廣義表LS中括號(hào)的最大嵌套層數(shù)。原子的深度為0，空表的深度為1。

單元素——ai可以是單個(gè)的數(shù)據(jù)元素，單元素也稱為原子，是指結(jié)構(gòu)上不可再分的一個(gè)數(shù)或一個(gè)結(jié)構(gòu)。

子表——ai可以是一個(gè)廣義表。

廣義表是n（n≥0）個(gè)數(shù)據(jù)元素的有限序列，記作：LS=(a1，a2，……，an)廣義表廣義表特性1）廣義表是一個(gè)多層次的結(jié)構(gòu)。因?yàn)閺V義表的元素可以是一個(gè)子表，而子表的元素還可以是子表。2）一個(gè)廣義表可以為其他廣義表共享，這種共享廣義表稱為再入表；3）廣義表可以是一個(gè)遞歸的表。一個(gè)廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無(wú)窮值,長(zhǎng)度是有限值；4）廣義表與樹形結(jié)構(gòu)相對(duì)應(yīng)，這個(gè)廣義表就是純表。廣義表是對(duì)線性表和樹的推廣。各種表的關(guān)系如下：線性表∈純表（樹）∈再入表∈遞歸表

212廣義表表示法1213不帶名字的廣義表表示廣義表表示法2214帶名字的廣義表表示廣義表表示示例215廣義表常用表示等價(jià)寫法帶名字的表示法表長(zhǎng)原子子表說(shuō)明E=()E()0無(wú)無(wú)E為空表L=(a，b)L(a，b)2a，b無(wú)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無(wú)A,BD=(a，D)D=(a，(a，(a，(…))))D(a，D(a，D(…)))2aDD為遞歸表廣義表的圖形表示216廣義表與其他數(shù)據(jù)結(jié)構(gòu)的關(guān)系217（1）與線性表的關(guān)系當(dāng)限定廣義表的每一項(xiàng)只能是基本元素而非子表時(shí)，廣義表就退化為線性表：(a1,a2,…,an)；（2）與二維數(shù)組的關(guān)系當(dāng)將數(shù)組的每行（或每列）看作為子表時(shí)，數(shù)組即為一個(gè)廣義表：((a11,a12,…,a1n),(a21,a22,…,a2n),…(an1,an2,…,ann))（3）與樹的關(guān)系樹也可以用廣義表來(lái)表示。廣義表的運(yùn)算定義218創(chuàng)建廣義表輸出廣義表求廣義表的長(zhǎng)度和深度從廣義表中查找或刪除元素5.8廣義表5.8.15.8.2廣義表的定義廣義表的存儲(chǔ)5.8.3廣義表的基本運(yùn)算廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)設(shè)計(jì)220廣義表頭尾表示法1——表頭表尾分析法221廣義表頭尾表示法2——子表分析法222廣義表表示法——兄弟孩子表示法223一棵樹采用孩子兄弟表示法所建立的存儲(chǔ)結(jié)構(gòu)與它所對(duì)應(yīng)的二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)是完全相同的，在廣義表鏈?zhǔn)酱鎯?chǔ)中，通常把此種存儲(chǔ)方式稱為“孩子兄弟表示法”224廣義表頭尾表示法結(jié)點(diǎn)設(shè)計(jì)表頭指針hPtr：子表首結(jié)點(diǎn)的地址后繼指針tPtr：存放同層后繼結(jié)點(diǎn)鏈接地址標(biāo)志tag——區(qū)分表結(jié)點(diǎn)和元素結(jié)點(diǎn)的標(biāo)志；元素值data——存放原子的值。頭尾表示法結(jié)點(diǎn)類型描述typedefenum{ATOM,LIST}ElemTag;

//ATOM==0:原子,LIST==1:子表TypedefstructGLNode{ElemTagtag;//標(biāo)志域union

{AtomTypedata;struct{structGLNode*hPtr,*tPtr;}ptr;};}Glist;225226【例5-11】用表頭表尾分解法給出廣義表E=(a,(b,c,d))的鏈表存儲(chǔ)形式圖表頭表尾分解法子表分解法227【例5-12】子表分解法給出廣義表L=(a,(x,y),((z)))的鏈表存儲(chǔ)形式圖。廣義表的孩子兄弟表示法228typedefenum{ATOM,LIST}ElemTag; //ATOM=0：?jiǎn)卧?；LIST=1：子表typedefstructGLENode{ElemTagtag; //標(biāo)志域，用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)union{ //原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分AtomTypedata; //原子結(jié)點(diǎn)的值域structGLENode*firstchildPtr; //表結(jié)點(diǎn)的表頭指針};structGLENode*siblingPtr; //指向下一個(gè)結(jié)點(diǎn)}GList //廣義表類型廣義表的孩子兄弟表示法229【例5-13】用孩子兄弟表示法表示下列各廣義表的存儲(chǔ)空表： 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本章小結(jié)231樹存儲(chǔ)結(jié)構(gòu)基本概念基本操作連續(xù)存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)構(gòu)造、查找插入、刪除遍歷、求深度等樹的定義、表示形式相關(guān)術(shù)語(yǔ)：結(jié)點(diǎn)、孩子、祖先、子孫、層數(shù)、高度、結(jié)點(diǎn)的度、有序樹、無(wú)序樹邏輯特征分層非線性結(jié)構(gòu)特例情形：二叉樹本章小結(jié)232二叉樹相關(guān)概念運(yùn)算—遍歷二叉樹的定義特例：滿二叉樹、完全二叉樹基本性質(zhì)：結(jié)點(diǎn)、深度、層數(shù)等之間的關(guān)系廣度優(yōu)先深度優(yōu)先遍歷應(yīng)用求深度統(tǒng)計(jì)葉子數(shù)目先序遍歷中序遍歷后序遍歷運(yùn)算—應(yīng)用表達(dá)式樹線索二叉樹哈夫曼樹與哈夫曼編碼本章小結(jié)233樹中有子樹按層級(jí)排列前后輩分等級(jí)森嚴(yán)不能亂，二叉樹形態(tài)最簡(jiǎn)，專門把它的特性仔細(xì)研：順序表存結(jié)點(diǎn)聯(lián)系隱藏在下標(biāo)位里面；二叉鏈表很形象，分支結(jié)構(gòu)聯(lián)系記錄在左右孩子域中間。

借隊(duì)列建鏈表，線性結(jié)構(gòu)把非線性關(guān)系存里邊，樹結(jié)點(diǎn)逐個(gè)出隊(duì)，添加指針域，二叉鏈表即展現(xiàn)。

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

本章小結(jié)234

樹的應(yīng)用介紹哈夫曼編碼是重點(diǎn)。哈夫曼樹帶權(quán)路徑長(zhǎng)度為最小，設(shè)計(jì)異前綴編碼方法巧妙堪經(jīng)典。哈夫曼樹構(gòu)造方法，找結(jié)點(diǎn)權(quán)值最小次小加起來(lái)為根逐步完善，左分支為0，右分支為1做好標(biāo)記，根到葉沿途的各01連起來(lái)即是葉上字符的編碼串。發(fā)送的信息傳輸前要將報(bào)文按字符編碼寫成01的序列串，通過(guò)有線或無(wú)線傳遞到接收的一端，天書般的報(bào)文1001串組成其意難辨，

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

本章小結(jié)235

樹中有樹是遞歸的樹，表中有表為廣義的表；廣義表含義廣泛，把線性非線性各種關(guān)系統(tǒng)統(tǒng)包含，頭尾法兄弟孩子法描述紛繁的結(jié)點(diǎn)聯(lián)系真不簡(jiǎn)單。元素有原子與子表兩類，類型大不同，存儲(chǔ)起來(lái)可是有點(diǎn)麻煩，用標(biāo)記巧區(qū)分，結(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)統(tǒng)一在union中間。

結(jié)點(diǎn)邏輯關(guān)系任意的非線性結(jié)構(gòu)圖Chapter

6DataStructuresandAlgorithmAnalysis主要內(nèi)容圖的邏輯結(jié)構(gòu)定義圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷圖的應(yīng)用學(xué)習(xí)目標(biāo) 熟練掌握?qǐng)D的邏輯結(jié)構(gòu)特點(diǎn) 掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu) 掌握?qǐng)D的遍歷 熟悉圖的相關(guān)應(yīng)用實(shí)際問(wèn)題中的圖及抽象圖的邏輯結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)圖的基本操作圖的遍歷圖中的樹問(wèn)題圖中的最短路徑問(wèn)題活動(dòng)頂點(diǎn)與活動(dòng)邊的問(wèn)題CONTENTS6.16.26.36.46.56.66.76.8實(shí)際問(wèn)題中的圖及抽象圖的邏輯結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)圖的基本操作圖的遍歷圖中的樹問(wèn)題圖中的最短路徑問(wèn)題活動(dòng)頂點(diǎn)與活動(dòng)邊的問(wèn)題CONTENTS6.16.26.36.46.56.66.76.86.1實(shí)際問(wèn)題中的圖及抽象幾何圖與拓?fù)鋱D242所有多邊形和圓周在拓?fù)湟饬x下是一樣的圓和方形、三角形的形狀、大小不同，在拓?fù)渥儞Q下，它們都是等價(jià)圖形。幾何圖與拓?fù)鋱D243圖引例1——地圖染色問(wèn)題24431232334四色猜想

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

從實(shí)際問(wèn)題中抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)的“圖”有什么特點(diǎn)？圖引例3——最短航線問(wèn)題250航線圖城市：頂點(diǎn)={a,b,c,d,e}航線：頂點(diǎn)間連線={ab,ad,bc,be,de}問(wèn)題描述：求出從d到c的最短航線。圖引例4——電路圖的表示方法251無(wú)向圖和有向圖把電路中每一條支路畫成抽象的線段形成的一個(gè)結(jié)點(diǎn)和支路的集合，見圖6.10，其中沒有考慮電流方向的圖為無(wú)向圖，有向圖的方向一般為該支路電流的參考方向圖的討論【思考與討論】從實(shí)際問(wèn)題中抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)的“圖”有什么特點(diǎn)？討論：數(shù)據(jù)結(jié)構(gòu)中的圖是拓?fù)湟饬x上的圖，其特點(diǎn)為：

用點(diǎn)表示對(duì)象，有直接聯(lián)系的對(duì)象用線連接起來(lái)。

圖形中連線的長(zhǎng)短曲直和結(jié)點(diǎn)的位置無(wú)關(guān)緊要，每一條線兩端都有結(jié)點(diǎn)。252實(shí)際問(wèn)題中的圖及抽象圖的邏輯結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)圖的基本操作圖的遍歷圖中的樹問(wèn)題圖中的最短路徑問(wèn)題活動(dòng)頂點(diǎn)與活動(dòng)邊的問(wèn)題CONTENT