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

第一章數(shù)據(jù)結(jié)構(gòu)與算法主要內(nèi)容1.1算法與數(shù)據(jù)結(jié)構(gòu)概念

1.2線性表1.3棧和隊(duì)列1.4樹和二叉樹

1.5查找1.6內(nèi)部排序1.1.1算法的根本概念定義：解題方案的準(zhǔn)確而完整描述。特點(diǎn)(四個(gè))：(一般填空題或選擇題)有窮性：包含有限個(gè)操作步驟，每個(gè)步驟都能在有限時(shí)間內(nèi)完成。確定性：每一條指令無二義性。〔相同輸入只能得到相同輸出〕可行性：指定操作都可以實(shí)現(xiàn)。擁有足夠的情報(bào)：有輸入有輸出?！埠w面廣〕算法：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)那么，并且每個(gè)規(guī)那么都是有效的、明確的，此順序在有限的次數(shù)下終止。2.算法根本要素及描述根本要素：算法中對數(shù)據(jù)的運(yùn)算和操作(算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸)算法的控制結(jié)構(gòu)算法的控制結(jié)構(gòu)：順序、選擇、循環(huán)。3.算法的設(shè)計(jì)方法(1)列舉法：列舉出所有可能情況，用給定條件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的。例：百錢百雞問題。(2)歸納法：列舉少量簡單而又特殊的情況，分析歸納出一般結(jié)論。(3)遞推法：從初始條件出發(fā)，逐步推出各種中間結(jié)果和最后結(jié)果。例：猴子摘桃子問題。(5)回溯法：嘗試。分析找出解決線索，逐步試探成功：求得解失?。褐鸩交赝?，換線索再試探。(4)遞歸法：解決復(fù)雜問題時(shí)，將問題逐層分解，歸納為一些簡單問題，解決了最后簡單問題后，再沿原來的逆過程逐步綜合。例：求3！。(6)減半遞推技術(shù)：減少：問題規(guī)模減半，而性質(zhì)不變遞推：重復(fù)減半的過程例：二分查找〔游戲猜數(shù)字〕1.1.2算法復(fù)雜度評價(jià)算法標(biāo)準(zhǔn)：時(shí)間復(fù)雜度和空間復(fù)雜度。

1算法的時(shí)間復(fù)雜度：定義：算法運(yùn)行從開始到結(jié)束所需要的計(jì)算工作量。計(jì)算工作量：算法執(zhí)行過程中所需要的根本運(yùn)算的執(zhí)行次數(shù)。算法的時(shí)間復(fù)雜度不僅依賴于問題的規(guī)模，也取決于輸入實(shí)例的初始狀態(tài)。

平均時(shí)間復(fù)雜度：所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。最壞時(shí)間復(fù)雜度：最壞情況下算法的時(shí)間復(fù)雜度。最優(yōu)算法：隨n的增大，T(n)增長較慢的算法。2算法的空間復(fù)雜度：定義：算法運(yùn)行從開始到結(jié)束所需的存儲(chǔ)空間量。一個(gè)算法在執(zhí)行時(shí)所占的空間包括算法程序所占的空間、輸入數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間。用While語句求計(jì)算：s=1+2+3+…+100，代碼如下。main(){inti=1,s=0;while(i<=100){s=s+ii=i+1}}printf(“%d〞,s);此算法的時(shí)間復(fù)雜度為：1+2*100+1=202空間復(fù)雜度為：2假設(shè)100改為n,那么時(shí)間復(fù)雜度為:o(2n+2)1.2數(shù)據(jù)結(jié)構(gòu)根本概念1.2.1數(shù)據(jù)結(jié)構(gòu)的定義(1)數(shù)據(jù)：信息載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理?？梢允菙?shù)值數(shù)據(jù)(整數(shù)、實(shí)數(shù))，也可以是非數(shù)值數(shù)據(jù)(聲音、圖像等)。(2)數(shù)據(jù)元素：數(shù)據(jù)的根本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理(又稱結(jié)點(diǎn)、記錄)。數(shù)據(jù)模型包括數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束。數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素由假設(shè)干數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)的不可分割的最小單位。關(guān)鍵碼：其值能唯一確定一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。舉例：圖書管理系統(tǒng)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)關(guān)鍵碼書目信息中的一本書書目信息的每一項(xiàng)書號(hào)VisualBasic6.0作者(或出版社或定價(jià))978-7(3)數(shù)據(jù)結(jié)構(gòu)：定義：相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。研究內(nèi)容:(記住兩種結(jié)構(gòu))如:(2-1空)①數(shù)據(jù)的邏輯結(jié)構(gòu)：各數(shù)據(jù)元素之間的邏輯關(guān)系；②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系；③對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算：添加，刪除，排序等。1.數(shù)據(jù)的邏輯結(jié)構(gòu)四類根本邏輯結(jié)構(gòu)：(1)集合結(jié)構(gòu)：數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合〞。(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一個(gè)對一個(gè)的關(guān)系。(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一個(gè)對多個(gè)的關(guān)系。(4)圖形結(jié)構(gòu)：數(shù)據(jù)元素之間存在多個(gè)對多個(gè)的關(guān)系。學(xué)號(hào)姓名系別住址電話…...981111李洪機(jī)械六舍5371111982111王剛電子四舍5372111983211王將計(jì)算機(jī)五舍5373211983212張強(qiáng)機(jī)械六舎5372221…………………………線性結(jié)構(gòu)樹型結(jié)構(gòu)學(xué)校教研室部、處實(shí)驗(yàn)室醫(yī)學(xué)院計(jì)算機(jī)…線性結(jié)構(gòu)與非線性結(jié)構(gòu)概念結(jié)點(diǎn)：組成數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素稱為一個(gè)結(jié)點(diǎn)。前后件關(guān)系：數(shù)據(jù)元素之間的固有關(guān)系可以用前后件關(guān)系(前驅(qū)與后繼關(guān)系)描述。舉例：家庭成員輩分關(guān)系(父親、兒子、女兒)，“父親〞是“兒子〞和“女兒〞的前件，“兒子〞和“女兒〞是“父親〞后件。線性結(jié)構(gòu)有且只有一個(gè)根結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件非線性結(jié)構(gòu)一個(gè)數(shù)據(jù)結(jié)構(gòu)如果不是線性結(jié)構(gòu)，那么稱之為非線性結(jié)構(gòu)。數(shù)據(jù)元素的前后關(guān)系復(fù)雜，一個(gè)結(jié)點(diǎn)既可以有多個(gè)前件，也可以有多個(gè)后件。樹型、圖形結(jié)構(gòu)屬于非線性結(jié)構(gòu)。2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)定義：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。

數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)中不僅存放各數(shù)據(jù)元素信息，還存放前后件關(guān)系的信息。實(shí)現(xiàn)方式：

(1)順序存儲(chǔ)方式：邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中。主要用于線性結(jié)構(gòu)。通常借助于數(shù)組來實(shí)現(xiàn)。(2)鏈?zhǔn)酱鎯?chǔ)方式：對邏輯上相鄰的元素不要求其物理地址相鄰，元素間邏輯關(guān)系通過附加的指針字段來表示。通常借助于指針類型實(shí)現(xiàn)。(3)索引存儲(chǔ)方法和散列存儲(chǔ)方法〔為了查找方便〕。1.3線性表

線性表的根本概念定義：具有相同數(shù)據(jù)類型的n(n≥0)個(gè)數(shù)據(jù)元素組成的有限序列。最簡單、最常用的數(shù)據(jù)結(jié)構(gòu)。

結(jié)構(gòu)特點(diǎn)：(1)有且只有一個(gè)根結(jié)點(diǎn)，無前驅(qū)

。(2)有且只有一個(gè)終端結(jié)點(diǎn)

，無后繼。(3)其他結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。1.3.2線性表的順序存儲(chǔ)結(jié)構(gòu)

順序表：采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表(一維數(shù)組)。

順序存儲(chǔ)：用一組地址連續(xù)的存儲(chǔ)空間依次存儲(chǔ)線性表的各元素。特點(diǎn)(順序存儲(chǔ)結(jié)構(gòu))：表中的所有元素所占存儲(chǔ)空間連續(xù)表中各元素在存儲(chǔ)空間中按邏輯順序存放

第i個(gè)元素地址：m：每個(gè)元素占m個(gè)存儲(chǔ)單元Loc(a1)第一個(gè)元素地址(基址)

1.順序表(線性表)根本概念順序表的順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)地址內(nèi)存狀態(tài)元素在線性表中的位序bb+m...b+(i-1)m...b+(n-1)mb+nm...b+(maxlen-1)ma1a2......12...

i...n空閑aian2.順序表根本運(yùn)算根本運(yùn)算：插入：在線性表指定位置插入一個(gè)新元素刪除：刪除線性表中指定的元素查找：在線性表中查找特定元素排序：線性表中元素按關(guān)鍵字升序或降序排序分解：將一個(gè)線性表分解為多個(gè)合并復(fù)制逆轉(zhuǎn)

3插入運(yùn)算：定義：是指在表的第i個(gè)位置上插入一個(gè)值為b的新元素原表長為n：(a1，a2，…ai-1，ai，ai+1，…

an)

新表長為n+1：(a1，a2，…ai-1，b，ai，ai+1，…，

an)

步驟：(1)將ai

~

an順序向后移動(dòng),為新元素讓出位置(2)將b置入空出的第i個(gè)位置舉例：(在第4個(gè)和第5個(gè)元素之間插入元素91)67412621489160123456786741262148916012345678674126214891601234567891時(shí)間性能分析：插入運(yùn)算，時(shí)間主要消耗在數(shù)據(jù)移動(dòng)上。在長度為n的線性表中插入一個(gè)元素，那么平均移動(dòng)元素次數(shù)：Pi：在第i個(gè)位置上作插入的概率。設(shè)Pi=1/(n+1)共需移動(dòng)(n-i+1)個(gè)元素。4刪除運(yùn)算：定義：指將表中第i個(gè)元素從線性表中去掉。原表長為n：(a1，a2，…ai-1，ai

，ai+1，…

an)

新表長為n-1：(a1，a2，…ai-1，ai+1，…，

an)

步驟：(1)刪除ai(2)將ai+1

~an

順序向前移動(dòng)舉例：(刪除第五個(gè)元素21)674126214891601234567867412648916012345678平均移動(dòng)元素次數(shù)：5.順序表優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：邏輯上相鄰元素存儲(chǔ)位置也相鄰，無需增加額外存儲(chǔ)空間；可方便隨機(jī)存取表中任一元素。缺點(diǎn)：插入和刪除運(yùn)算不方便，必須移動(dòng)大量結(jié)點(diǎn)，效率較低；不適合元素經(jīng)常變動(dòng)的大的線性表。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn):每個(gè)結(jié)點(diǎn)由兩局部組成：一局部存放數(shù)據(jù)，另一局部存儲(chǔ)指向前件或后件結(jié)點(diǎn)的指針域。邏輯上相鄰的結(jié)點(diǎn)物理上不必相連。數(shù)據(jù)運(yùn)算〔插入和刪除等〕靈活。1.3.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

結(jié)點(diǎn)組成：數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)結(jié)點(diǎn)對應(yīng)一個(gè)存儲(chǔ)單元，簡稱結(jié)點(diǎn)。

兩局部：數(shù)據(jù)域：存放數(shù)據(jù)元素值指針域：存放指針，指向后繼結(jié)點(diǎn)線性鏈表中用專門的HEAD指針指向第一個(gè)元素的結(jié)點(diǎn)，其最后一個(gè)元素沒有后件，因此最后一個(gè)結(jié)點(diǎn)指針域?yàn)榭铡灿肗ULL或0表示〕。1線性鏈表定義：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。

分類：單鏈表、循環(huán)單鏈表、雙向鏈表2單鏈表定義：由n個(gè)結(jié)點(diǎn)鏈接，且每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域的鏈表。線性單鏈表(A,B,C,D,E,F)：邏輯狀態(tài)：

ABCDEHF物理狀態(tài)：E7FNULLB25A13C31D11713192531單鏈表存?。罕仨殢念^指針開始進(jìn)行，依次順著指針向鏈尾方向掃描。找到各個(gè)元素。(1)單鏈表插入：增加新結(jié)點(diǎn),修改鏈接指針步驟：PBCXSA修改s指針域,s結(jié)點(diǎn)的后繼是p結(jié)點(diǎn)的后繼修改p指針域,使其指向新結(jié)點(diǎn)s(2)單鏈表刪除：不需要移動(dòng)元素,僅修改指針鏈接。步驟：先找到p的前驅(qū)結(jié)點(diǎn)q刪除p結(jié)點(diǎn)，修改q結(jié)點(diǎn)指針域

q

next＝p

nextCPBA刪除前P刪除后qCBA1.4棧和隊(duì)列

1.4.1棧

1.棧的定義〔用于子程序調(diào)用等〕只允許在線性表的一端進(jìn)行插入和刪除的線性表。

相關(guān)術(shù)語：(1)棧頂：允許插入與刪除的一端稱為棧頂。指針top指向棧頂位置。(2)棧底：不允許插入與刪除的一端稱為棧底。指針base指向棧底。(3)入棧：棧的插入操作(往棧中插入一個(gè)元素)(4)出棧：棧的刪除操作(從棧中刪除一個(gè)元素)(5)?？眨簍op=base(6)棧滿：top=m(m為棧最大容量)棧示意圖：原那么：先進(jìn)后出或后進(jìn)先出2順序棧及其運(yùn)算棧的兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：也稱可利用棧。用于收集計(jì)算機(jī)存儲(chǔ)器中所有空閑存儲(chǔ)空間。順序棧：順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧。鏈棧：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧稱為鏈棧。根本運(yùn)算：入棧、退棧與讀棧頂元素(2)出棧步驟：棧頂元素賦給一個(gè)指定的變量。棧頂指針top減1。棧頂指針為0時(shí)，?？?，不能再退棧。稱為?！跋乱绋曞e(cuò)誤。(1)入棧步驟：棧頂指針top加1。新元素插入到棧頂指針指向位置。棧頂指針指向存儲(chǔ)空間最后一個(gè)位置時(shí)，棧已滿，不能再入棧。稱為?！吧弦绋曞e(cuò)誤。(3)讀棧頂元素概念：將棧頂元素賦給一個(gè)指定變量。注意：不刪除棧頂元素，棧頂指針不會(huì)改變。讀棧頂元素和出棧區(qū)別？舉例：topbottomABCDEF10987654321S(1:10)有6個(gè)元素的棧ABCDEFXYS(1:10)topbottom插入X和Y后的棧10987654321bottomABCDEFX10987654321S(1:10)top退出一個(gè)元素后的棧1.4.2隊(duì)列

定義：指允許在一端插入，而在另一端進(jìn)行刪除的線性表。

相關(guān)術(shù)語(5個(gè))：(1)隊(duì)尾：允許插入的一端稱為隊(duì)尾。rear隊(duì)尾指針，始終指向隊(duì)尾元素的下一個(gè)位置。(2)隊(duì)頭：允許進(jìn)行刪除的一端稱為隊(duì)頭。front隊(duì)頭指針，始終指向隊(duì)頭元素。(3)入隊(duì)列：隊(duì)列插入操作(進(jìn)隊(duì)列)(4)出隊(duì)列：隊(duì)列的刪除操作(退隊(duì)列)(5)空隊(duì)列：隊(duì)列中無數(shù)據(jù)元素原那么：先進(jìn)先出或后進(jìn)后出隊(duì)頭元素總是最先進(jìn)隊(duì)列的,也總是最先出隊(duì)列隊(duì)尾元素總是最后進(jìn)隊(duì)列,也是最后出隊(duì)列隊(duì)列結(jié)構(gòu)示意圖：隊(duì)列Q=(a1，a2,…,an

)a1aia2an……隊(duì)頭隊(duì)尾退隊(duì)入隊(duì)1順序隊(duì)列定義：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，利用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的數(shù)據(jù)元素。約定：初始化隊(duì)列：front=rear=0隊(duì)尾插入新元素，rear加1隊(duì)頭元素出隊(duì)列，front加1舉例：順序隊(duì)列頭尾指針變化情況：543210空隊(duì)rearfront

a1

a2

a3543210frontrear

a3543210frontrear

a3

a4

a5

a6543210frontrear缺點(diǎn)：如上例,隊(duì)列最大存儲(chǔ)空間為6，隊(duì)滿時(shí)再繼續(xù)插入元素就會(huì)上溢。隊(duì)尾指針已到達(dá)數(shù)組上界，不能在增大。而當(dāng)前隊(duì)列可用空間并未占滿，“假滿〞現(xiàn)象。2循環(huán)隊(duì)列定義：將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，相成邏輯上的環(huán)形空間。判定條件：隊(duì)空：rear=front隊(duì)滿：方法1：rear=front，設(shè)一個(gè)標(biāo)志變量S=0隊(duì)空1隊(duì)滿約定循環(huán)數(shù)組中元素個(gè)數(shù)到達(dá)M-1隊(duì)滿頭指針在尾指針下一位置上方法2：少一個(gè)元素空間循環(huán)隊(duì)列示意圖：02134567frontrear隊(duì)空02134567一般情況a1a2frontrear02134567隊(duì)滿(少一個(gè)元素)a1a2frontreara3a4a5a6a7設(shè)循環(huán)隊(duì)列中最多可容M個(gè)元素，那么循環(huán)隊(duì)列中元素的個(gè)數(shù)為：=rear-front(當(dāng)rear>front)=(rear+M-front)(當(dāng)rear>front)如左圖中元素個(gè)數(shù):4+7-5=6設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a,b,c,d,e,f依次通過棧S，并且一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，假設(shè)出隊(duì)的順序?yàn)閎,d,c,f,e,a，那么棧S的容量至少應(yīng)該為〔〕

〔A〕3〔B〕4〔C〕5〔D〕6一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，那么元素出棧的順序是〔〕〔A〕12345ABCDE〔B〕EDCBA54321〔C〕ABCDE12345〔D〕54321EDCBA如果不是依次入棧，然后再依次出棧，那么ABD均有可能。類似題：(2-3)AB★樹結(jié)構(gòu)中結(jié)點(diǎn)之間有分支關(guān)系，層次關(guān)系，樹中無環(huán)路樹的一般表示：

ABCDEFGHIJK1.5樹與二叉樹1.5.1樹的根本概念樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。根結(jié)點(diǎn)在第一層。1.5.2二叉樹及其根本性質(zhì)二叉樹的特點(diǎn)：〔1〕非空二叉樹只有一個(gè)根結(jié)點(diǎn)；〔2〕每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。二叉樹的五種根本形態(tài)(a)(b)(c)(d)(e)1什么是二叉樹2二叉樹的根本性質(zhì)性質(zhì)1二叉樹第i(i≥1)層上至多有2i-1個(gè)結(jié)點(diǎn)。證明：根結(jié)點(diǎn)在二叉樹的第一層上，這層結(jié)點(diǎn)數(shù)最多為1個(gè)，即20；第二層上最多有2個(gè)結(jié)點(diǎn)，即21個(gè)；…那么第i層上結(jié)點(diǎn)最多有2i-1個(gè)。性質(zhì)2深度為k(k≥1)的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。證明：由性質(zhì)(1)可知各層結(jié)點(diǎn)最多數(shù)目之和為：20+21+22+…+2k-1；由二進(jìn)制換算關(guān)系可得2k–1，因此二叉樹樹中結(jié)點(diǎn)的最大數(shù)目為2k-1。性質(zhì)3：度為0的結(jié)點(diǎn)〔即葉子結(jié)點(diǎn)〕總是比度為2的結(jié)點(diǎn)多一個(gè)。證明：設(shè)n代表二叉樹結(jié)點(diǎn)的總數(shù)，葉子結(jié)點(diǎn)(即度為零的結(jié)點(diǎn))個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2。那么n=n0+n1+n2(1)有n個(gè)結(jié)點(diǎn)的二叉樹總邊數(shù)為n-1條：n-1=0*n0+1*n1+2*n2(2)將(1)式代入(2)式得：n0=n2+1滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，那么k層上有2k-1個(gè)結(jié)點(diǎn),深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均到達(dá)最大值，在最后一層上只缺少右邊的假設(shè)干結(jié)點(diǎn)。根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或1。設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，那么在該樹中有多少個(gè)葉子結(jié)點(diǎn)？設(shè)該完全二叉樹中有x個(gè)度為０的結(jié)點(diǎn)〔即葉子結(jié)點(diǎn)〕，y個(gè)度為１的結(jié)點(diǎn)，ｚ個(gè)度為２的結(jié)點(diǎn)，那么：x+y+z=700①z=x-1②將②代入①可得：x=(700+1-y)/2③又y只能取0或1，分別代入③可得：x=350.5④〔不合理舍去〕或350⑤所以葉子結(jié)點(diǎn)數(shù)x=350思考：將700改成739，那么結(jié)果為多少？370滿二叉樹和完全二叉樹(a)滿二叉樹；(b)完全二叉樹；(c)非完全二叉樹FGDE1376542ABC(a)FDE136542ABC(b)FG13762ABC(c)性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹樹深為[log2n]+1?；蛘撸壕哂衝個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1。其中[log2n]表示取[log2n]的整數(shù)局部。性質(zhì)5設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序〔每一層從左到右〕用自然數(shù)1，2，…n給結(jié)點(diǎn)進(jìn)行編號(hào)〔k=1,2….n〕，有以下結(jié)論：①假設(shè)k=1，那么該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；假設(shè)k>1，那么該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)；②假設(shè)2k≤n，那么編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否那么該結(jié)點(diǎn)無左子結(jié)點(diǎn)〔也無右子結(jié)點(diǎn)〕；③假設(shè)2k+1≤n，那么編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否那么該結(jié)點(diǎn)無右子結(jié)點(diǎn)。1.5.3二叉樹的遍歷遍歷二叉樹是指以一定的