大學(xué)計算機基礎(chǔ)第4章數(shù)據(jù)結(jié)構(gòu)

1、第4章 數(shù)據(jù)結(jié)構(gòu)(sh j ji u)共八十五頁主要(zhyo)內(nèi)容數(shù)據(jù)結(jié)構(gòu)(sh j ji u)概述線性表及其操作樹與二叉樹數(shù)據(jù)結(jié)構(gòu)共八十五頁數(shù)據(jù)結(jié)構(gòu)(sh j ji u)概述080611 班號 82519610 計算機學(xué)院辦公室電話號碼10001 哈工程(gngchng)大學(xué)郵編230102780618748 身份證號碼 例1：0806118251961010004230102780618748結(jié)論1.雜亂的數(shù)據(jù)不能表達和交流信息結(jié)論2.數(shù)據(jù)之間是有聯(lián)系的 結(jié)論數(shù)據(jù)之間是有結(jié)構(gòu)的結(jié)論在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運算數(shù)據(jù)結(jié)構(gòu)共八十五頁的主要(zhyo)內(nèi)容例2 電話號碼查詢(chxn)系統(tǒng) 設(shè)

2、有一個電話號碼薄，它記錄了n個人的名字和其相應(yīng)的電話號碼，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn)其中ai，bi(i=1，2n) 分別表示某人的名字和對應(yīng)電話號碼問題：設(shè)計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。要做的事情：設(shè)計恰當?shù)臄?shù)學(xué)模型表示電話號碼簿的所有信息采用相應(yīng)查找算法,實現(xiàn)快速查詢與打印.結(jié)論2.數(shù)據(jù)之間是有聯(lián)系的 這些聯(lián)系常常影響算法的選擇和效率。 數(shù)據(jù)結(jié)構(gòu)共八十五頁的主要(zhyo)內(nèi)容例3: 鋪設(shè)煤氣管道問題n個居民區(qū)之間鋪設(shè)煤氣管道，只要鋪設(shè)n-1條管道

3、即可。假設(shè): 任意兩個居民區(qū)之間都可以架設(shè)管道， 每條管道的費用成本不同，要解決的問題: 用一定(ydng)的數(shù)據(jù)模型表示該問題，在此基礎(chǔ)上計算投資最少（或盡可能少的）的管道鋪設(shè)方案。CBAED325416216945364740CBAED32162136數(shù)據(jù)結(jié)構(gòu)共八十五頁職工號姓名性別出生年月職務(wù)單位01郭建成男1952年8月處長02肖明男1958年6月科長教材科03晨曦女1954年12月科長考務(wù)科04趙麗霞女1962年8月主任辦公室05崔小龍男1949年8月科員教材科06袁莉女1965年4月科員教材科07王芳女1962年6月科員考務(wù)科08張宏愿男1957年3月科員考務(wù)科09馬明華男1965

4、年10月科員考務(wù)科10李冰男1966年7月科員辦公室例3 表1-1 教務(wù)處人事(rnsh)簡表 10條記錄，每條記錄有6個數(shù)據(jù)項，每條記錄的職工(zhgng)號不同， 用職工號來代表整個職工記錄。 03080207040609100501按職工年齡從大到小排列03080207040609100501領(lǐng)導(dǎo)和被領(lǐng)導(dǎo)的關(guān)系07040810090205060301朋友關(guān)系線性結(jié)構(gòu)樹型結(jié)構(gòu)圖形結(jié)構(gòu)結(jié)論數(shù)據(jù)之間是有結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)共八十五頁的主要內(nèi)容例4：圖書目錄管理書目信息： 書名，作者，登錄號，分類，出版年月對圖書目錄操作： 查找：某書在書庫中是否存在？ 插入：購進新書時的登錄； 刪除：報廢或丟失的書，

5、需從目錄(ml)中去掉；結(jié)論在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運算數(shù)據(jù)結(jié)構(gòu)共八十五頁 DS主要研究內(nèi)容(nirng)：數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系并對每種結(jié)構(gòu)定義相適應(yīng)的各種運算設(shè)計出相應(yīng)的算法分析算法的效率的主要(zhyo)內(nèi)容數(shù)據(jù)結(jié)構(gòu)共八十五頁基本(jbn)術(shù)語數(shù)據(jù) 描述客觀事物的符號的集合結(jié)構(gòu) 數(shù)據(jù)元素之間具有的關(guān)系。數(shù)據(jù)結(jié)構(gòu) 具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)元素 數(shù)據(jù)整體中相對獨立的基本單位,也稱為數(shù)據(jù)結(jié)點。 數(shù)據(jù)對象 具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)(sh j ji u)共八十五頁數(shù)據(jù)(shj)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)某種邏輯結(jié)構(gòu)(jigu)的數(shù)據(jù)在計算機存儲器中的存

6、儲方式。數(shù)據(jù)元素之間具有的邏輯關(guān)系(結(jié)構(gòu))邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁數(shù)據(jù)的邏輯結(jié)構(gòu)(jigu)和存儲結(jié)構(gòu)(jigu)線性結(jié)構(gòu)(jigu)樹型結(jié)構(gòu)圖狀結(jié)構(gòu)邏輯結(jié)構(gòu)純集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁職工號姓名性別出生年月職務(wù)單位01郭建成男1952年8月處長02肖明男1958年6月科長教材科03晨曦女1954年12月科長考務(wù)科04趙麗霞女1962年8月主任辦公室05崔小龍男1949年8月科員教材科06袁莉女1965年4月科員教材科07王芳女1962年6月科員考務(wù)科08張宏愿男1957年3月科員考務(wù)科09馬明華男1965年10月科員考務(wù)科10李冰男1966年7月科員辦公室例5 表1-1 教務(wù)處人事

7、(rnsh)簡表 10條記錄，每條記錄有6個數(shù)據(jù)項，每條記錄的職工號不同， 用職工號來代表(dibio)整個職工記錄。 03080207040609100501按職工年齡從大到小排列03080207040609100501領(lǐng)導(dǎo)和被領(lǐng)導(dǎo)的關(guān)系07040810090205060301朋友關(guān)系線性結(jié)構(gòu)樹型結(jié)構(gòu)圖形結(jié)構(gòu)07040603性別關(guān)系集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁數(shù)據(jù)的邏輯結(jié)構(gòu)(jigu)和存儲結(jié)構(gòu)(jigu)順序存儲結(jié)構(gòu)(jigu)鏈式存儲結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表及其基本操作學(xué)生(xu sheng)成績登記表姓 名英語(yn y)C語言高數(shù)學(xué)號丁一9678870101李二879078

8、0102張三6786860103孫紅6981960104王冬8774660105數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表及其基本操作職工工資登記表(線性表)姓 名崗位津貼基本工資(j bn n z)獎金(jingjn)職工號丁一6002782000101李二3001901000102張三3001861000103孫紅5002182000104王冬3001901000105數(shù)據(jù)元素可以有若干數(shù)據(jù)項構(gòu)成，比如1個記錄那么數(shù)據(jù)元素之間的是什么關(guān)系？數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表及其基本操作線性表：簡稱表，是n（n0）個具有相同類型的數(shù)據(jù)(shj)元素的有限序列。線性表的長度：線性表中數(shù)據(jù)元素的個數(shù)?？毡恚洪L度等于零的線性

9、表，記為：L=( )。非空表記為：L（a1, a2 , , ai-1, ai , , an)線性表的定義(dngy)其中，ai（1in）稱為數(shù)據(jù)元素；下角標 i 表示該元素在線性表中的位置或序號 。數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表及其基本操作a1a3a4ana2線性表的圖形(txng)表示線性表（a1, a2 , , ai-1, ai , , an)的圖形(txng)表示如下：幾個線性表的例子 數(shù)列： ( 25， 12， 78， 34， 100， 88)1a1 a2 a3 a4 a5 a6數(shù)據(jù)元素為整數(shù)2字母表： ( A， B， C， , Z)a1 a2 a3 a26數(shù)據(jù)元素字母數(shù)據(jù)結(jié)構(gòu)共八十五頁線性

10、表及其基本操作a1a3a4ana2線性表的特性(txng)1.有限性：線性表中數(shù)據(jù)(shj)元素的個數(shù)是有窮的。2.相同性：線性表中數(shù)據(jù)元素的類型是同一的。3.順序性：線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系(ai-1, ai)，即ai-1是ai的前驅(qū)， ai是ai-1的后繼；a1 無前驅(qū)，an無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。 數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的順序存儲結(jié)構(gòu)(jigu)順序(shnx)表線性表的順序存儲結(jié)構(gòu)例：（34, 23, 67, 43）34236743 4存儲要點用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的順序存儲結(jié)構(gòu)(

11、jigu)如何求得任意元素的存儲地址？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑(kngxin) 長度順序表一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：cLoc(ai)Loc(a1)數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的順序存儲結(jié)構(gòu)(jigu) 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑(kngxin) 長度Loc(ai)=Loc(a1) + (i -1)c順序表cLoc(ai)Loc(a1)一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的順序存儲結(jié)構(gòu)(jigu)33

12、例：（35，12，24，42），在i=2的位置(wi zhi)上插入33。順序表的插入 435122442a1a2a3a40 1 2 3 4422412335什么時候不能插入？注意邊界條件表滿：length=MaxSize合理的插入位置：1in（i是元素的序號）數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的順序存儲結(jié)構(gòu)(jigu)例：（35, 33, 12, 24, 42），刪除i=2的數(shù)據(jù)(shj)元素。順序表的刪除 535a1a2a3a40 1 2 3 4422412334a5122442刪除后順序表的內(nèi)容需要考慮的異常情況：(1).是否表空？(2).刪除位置是否合適？(正常位置：1in)數(shù)據(jù)結(jié)構(gòu)共八十五頁線

13、性表的鏈式存儲(cn ch)結(jié)構(gòu)存儲思想：用一組任意的存儲單元存放(cnfng)線性表的元素。連續(xù)不連續(xù)零散分布單鏈表：線性表的鏈接存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的鏈式存儲(cn ch)結(jié)構(gòu)單鏈表結(jié)點數(shù)據(jù)(shj)域指針域單鏈表是由若干結(jié)點構(gòu)成的；單鏈表的結(jié)點只有一個指針域。data：存儲數(shù)據(jù)元素next：存儲指向后繼結(jié)點的地址 data next單鏈表的結(jié)點結(jié)構(gòu)：數(shù)據(jù)域指針域0200020803000325 a10200 a20325 a30300 a4 數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的鏈式存儲(cn ch)結(jié)構(gòu)0200020803000325存儲特點：邏輯次序和物理次序 不一定相同(xin

14、tn)。 2.元素之間的邏輯關(guān)系 用指針表示。例：(a1, a2 ,a3, a4)的存儲示意圖單鏈表 a10200 a20325 a30300 a4 data next數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的鏈式存儲(cn ch)結(jié)構(gòu)單鏈表的插入(ch r)：在第i個結(jié)點后插入一個新結(jié)點思想： 1) 從第1個結(jié)點出發(fā)，找到第i個結(jié)點； 2) 將新結(jié)點插入其后 3) 返回操作結(jié)果信息(成功與否)plista2a1aianai+1ppxq 頭指針空指針p數(shù)據(jù)結(jié)構(gòu)共八十五頁線性表的鏈式存儲(cn ch)結(jié)構(gòu)單鏈表的刪除(shnch)：刪除(shnch)第i個結(jié)點思想： 1) 從第1個結(jié)點出發(fā)，找到第i-1個結(jié)點；

15、 2) 刪除第i個結(jié)點 3) 返回操作結(jié)果信息(成功與否)plista2a1ai-1ai+1aippq數(shù)據(jù)結(jié)構(gòu)共八十五頁棧的概念(ginin)及實現(xiàn)棧：限定僅在表尾進行插入(ch r)和刪除操作的線性表?？諚＃翰缓魏螖?shù)據(jù)元素的棧。 （a1, a2, , an）棧頂棧底允許插入和刪除的一端稱為棧頂，另一端稱為棧底。 a1a2a3數(shù)據(jù)結(jié)構(gòu)共八十五頁棧的概念(ginin)及實現(xiàn)a1a2a3入棧出棧棧底棧頂插入(ch r)：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖數(shù)據(jù)結(jié)構(gòu)共八十五頁棧的概念(ginin)及實現(xiàn)棧的操作(cozu)特性：后進先出a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓

16、棧刪除：出棧、彈棧棧頂棧的示意圖數(shù)據(jù)結(jié)構(gòu)共八十五頁棧的概念(ginin)及實現(xiàn)例：有三個元素按a、b、c的次序依次(yc)進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂 情況1：出棧序列：cba數(shù)據(jù)結(jié)構(gòu)共八十五頁棧的概念(ginin)及實現(xiàn)例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能(knng)的出棧序列有多少種？ 情況2：棧底棧頂ab棧頂c出棧序列：bca注意：棧只限制插入和刪除位置， 沒有限定插入和 刪除的次序。a,b,c: abc(a進a出，b進b出，c進c出）a,bc : acb (a進a出，bc進，cb出）ab,c :

17、bac (ab進，ba出，c進c出） bca (ab進，b出，ca出）abc : cba (abc進，cba出）只一種情況數(shù)據(jù)結(jié)構(gòu)共八十五頁進一步的例題(lt)（P145四1）：已知四個入棧元素。寫出全部出棧序列A,B,C,D: ABCD A,BC,D: ACBD/ACDB A,B,CD: ABDC A,BCD: ADCB AB,C,D: BACD/BCAD/BCDA AB,CD: BADC/BDCA ABC,D: CDBA/CBDA/CBAD ABCD: DCBA特點：D開頭(ki tu)的只有一種數(shù)據(jù)結(jié)構(gòu)共八十五頁 一個棧的輸入序列(xli)為1 2 3 4 5，則下列序列中不可能是棧的輸

18、出序列的是_ A） 2 3 4 1 5 B） 2 3 1 4 5 C） 5 4 1 3 2 D） 1 5 4 3 2數(shù)據(jù)結(jié)構(gòu)(sh j ji u)共八十五頁棧的概念(ginin)及實現(xiàn)棧的順序存儲結(jié)構(gòu)(jigu)及實現(xiàn) 順序棧棧的順序存儲結(jié)構(gòu)如何改造數(shù)組實現(xiàn)棧的順序存儲？ 0 1 2 3 4 5 6 7 8a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。 top數(shù)據(jù)結(jié)構(gòu)共八十五頁棧的概念(ginin)及實現(xiàn)出棧：top減1進棧：top加1棧空：top= -1 0 1 2 3 4 5 6 7 8a1topa2topa3top棧滿：top= MAX_SIZE棧的順序存儲結(jié)

19、構(gòu)(jigu)及實現(xiàn) 插入一般稱為進棧（PUSH），刪除則稱為退棧（POP） 數(shù)據(jù)結(jié)構(gòu)共八十五頁隊列(duli)隊列(duli)的邏輯結(jié)構(gòu)空隊列：不含任何數(shù)據(jù)元素的隊列。 隊列：只允許在一端進行插入操作，而另一端進行刪除操作的線性表。允許插入（也稱入隊、進隊）的一端稱為隊尾，允許刪除（也稱出隊）的一端稱為隊頭。 （a1, a2, , an）隊尾隊頭數(shù)據(jù)結(jié)構(gòu)共八十五頁隊列的操作(cozu)特性：先進先出a1a2a3入隊(r du)隊尾隊頭出隊隊頭隊列的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁0 1 2 3 4 入隊出隊例：a1a2a3a4依次(yc)入隊a1a2a3a4rearrearrearrearfron

20、t rear隊列(duli)的順序存儲結(jié)構(gòu)及實現(xiàn) 設(shè)置隊頭、隊尾兩個指針 數(shù)據(jù)結(jié)構(gòu)共八十五頁例：a1a2依次(yc)出隊0 1 2 3 4 入隊出隊a1a2a3a4rearfrontfrontfront隊列(duli)的順序存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)共八十五頁例：a1a2依次(yc)出隊特殊(tsh)線性表隊列0 1 2 3 4 入隊出隊a3a4rearfront隊列的移動有什么特點？隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)共八十五頁例：a1a2依次(yc)出隊特殊(tsh)線性表隊列0 1 2 3 4 入隊出隊a3a4rearfront整個隊列向數(shù)組下標較大方向移動單向移動性隊列的順序存儲結(jié)構(gòu)及實現(xiàn)

21、 數(shù)據(jù)結(jié)構(gòu)共八十五頁假溢出：當元素被插入到數(shù)組中下標(xi bio)最大的位置上之后，隊列的空間就用盡了，盡管此時數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。特殊(tsh)線性表隊列繼續(xù)入隊會出現(xiàn)什么情況？0 1 2 3 4 入隊出隊a3a4rearfronta5rear隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)共八十五頁循環(huán)隊列：將存儲隊列的數(shù)組頭尾(tu wi)相接。特殊(tsh)線性表隊列如何解決假溢出？0 1 2 3 4 入隊出隊a3a4fronta5rearreara6隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 隊列的鏈式存儲結(jié)構(gòu)，需要隊頭和隊尾的兩個指針。數(shù)據(jù)結(jié)構(gòu)共八十五頁樹的基本概念及存儲(cn ch)結(jié)

22、構(gòu)樹的定義(dngy)樹：n（n0）個結(jié)點的有限集合。當n0時，稱為空樹；任意一棵非空樹滿足以下條件： 有且僅有一個特定的稱為根的結(jié)點； 當n1時，除根結(jié)點之外的其余結(jié)點被分成m（m0）個互不相交的有限集合T1,T2, ,Tm，其中每個集合又是一棵樹，并稱為這個根結(jié)點的子樹。樹的定義是采用遞歸方法數(shù)據(jù)結(jié)構(gòu)共八十五頁樹的基本概念及存儲(cn ch)結(jié)構(gòu)A只有根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹根子樹數(shù)據(jù)結(jié)構(gòu)(sh j ji u)共八十五頁樹的基本概念及存儲(cn ch)結(jié)構(gòu)樹與非樹結(jié)構(gòu)？ 樹的定義(dngy)ACBGFEDHIACBGFDACBGFDE數(shù)據(jù)結(jié)構(gòu)共八十五頁樹的基本概念及存

23、儲(cn ch)結(jié)構(gòu)樹的應(yīng)用(yngyng)舉例文件結(jié)構(gòu)My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic數(shù)據(jù)結(jié)構(gòu)共八十五頁樹的基本概念及存儲(cn ch)結(jié)構(gòu)樹的基本(jbn)術(shù)語結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)。樹的度：樹中各結(jié)點度的最大值。CGBDEFKLHMIJA數(shù)據(jù)結(jié)構(gòu)共八十五頁葉子結(jié)點(ji din)：度為0的結(jié)點，也稱為終端結(jié)點。分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點。CGBDEFKLHMIJA樹的基本(jbn)術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁孩子、雙親：樹中某結(jié)點子(din zi)樹的根結(jié)點稱為這個結(jié)點的孩子

24、結(jié)點，這個結(jié)點稱為它孩子結(jié)點的雙親結(jié)點；兄弟：具有同一個雙親的孩子結(jié)點互稱為兄弟。 CGBDEFKLHMIJA樹的基本(jbn)術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁路徑：如果樹的結(jié)點序列(xli)n1, n2, , nk有如下關(guān)系：結(jié)點ni是ni+1的雙親（1=ik），則把n1, n2, , nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。 CGBDEFKLHMIJA樹的基本(jbn)術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁祖先、子孫(z sn)：在樹中，如果有一條路徑從結(jié)點A到結(jié)點L，那么A、B、E都稱為L的祖先，而B、E、L都稱為A的子孫。CGBDEFKLHM

25、IJA樹的基本(jbn)術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁結(jié)點所在層數(shù)：根結(jié)點的層數(shù)為1；對其余任何(rnh)結(jié)點，若某結(jié)點在第k層，則其孩子結(jié)點在第k+1層。樹的深度：樹中所有結(jié)點的最大層數(shù)，也稱高度。1層2層4層3層高度4CGBDEFKLHMIJC樹的基本(jbn)術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁CBDEFKLHJA71234568910層序編號：將樹中結(jié)點按照從上層到下層、同層從左到右的次序依次給他們(t men)編以從1開始的連續(xù)自然數(shù)。樹的基本(jbn)術(shù)語樹的基本概念及存儲結(jié)構(gòu)在樹的每一組兄弟結(jié)點之間定義一個從左到右的次序，則得到一棵有序樹；否則稱為無序樹 數(shù)

26、據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)二叉樹的定義(dngy) 二叉樹是n（n0）個結(jié)點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。問題轉(zhuǎn)化：將樹轉(zhuǎn)換為二叉樹，從而利用二叉樹解決樹的有關(guān)問題。研究二叉樹的意義？數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)二叉樹的特點(tdin)： 每個結(jié)點最多有兩棵子樹； 二叉樹是有序的，其次序不能任意顛倒。 注意：二叉樹和樹是兩種樹結(jié)構(gòu)。ABCDEFGABAB數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)二叉樹的基本(jbn)形態(tài)空二叉樹只有一個根結(jié)點左子樹右子樹根

27、結(jié)點同時有左右子樹左子樹根結(jié)點只有左子樹右子樹根結(jié)點只有右子樹數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)具有3個結(jié)點(ji din)的樹和具有3個結(jié)點的二叉樹的形態(tài)二叉樹和樹是兩種樹結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)斜樹1 .所有結(jié)點(ji din)都只有左子樹的二叉樹稱為左斜樹；2 .所有結(jié)點都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統(tǒng)稱為斜樹。1. 在斜樹中，每一層只有一個結(jié)點；2.斜樹的結(jié)點個數(shù)與其深度相同。 斜樹的特點：ABCABC數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點(ji din)都存在左子樹和右子

28、樹，并且所有葉子都在同一層上。滿二叉樹的特點： 1. 葉子只能出現(xiàn)在最下一層； 2. 只有度為0和度為2的結(jié)點。特殊的二叉樹CDEFGHIJKLMNO1112131415數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)滿二叉樹不是滿二叉樹，雖然所有分支結(jié)點都有左右(zuyu)子樹，但葉子不在同一層上。滿二叉樹在同樣深度的二叉樹中結(jié)點個數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點個數(shù)最多A1523467BCDEFGLM89數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)完全二叉樹 對一棵具有n個結(jié)點的二叉樹按層序編號(bin ho)，如果編號(bin ho)為i（1in）

29、的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中的位置完全相同。特殊的二叉樹CDEFGHIJKLMNO1112131415CDEFGHIJ數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)在滿二叉樹中，從最后一個結(jié)點開始，連續(xù)去掉任意(rny)個結(jié)點，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結(jié)點10與滿二叉樹中的結(jié)點10不是同一個結(jié)點數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)1. 葉子結(jié)點只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點

30、都集中在二叉樹的左部；2. 完全二叉樹中如果(rgu)有度為1的結(jié)點，只可能有一個，且該結(jié)點只有左孩子。 3. 深度為k的完全二叉樹在k-1層上一定是滿二叉樹。完全二叉樹的特點CDEFGHIJ數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)二叉樹的基本(jbn)性質(zhì) 性質(zhì)5-1 二叉樹的第i層上最多有2i-1個結(jié)點（i1）。 證明：當i=1時，第1層只有一個根結(jié)點，而 2i-1=20 =1，結(jié)論顯然成立。假定i=k（1ki）時結(jié)論成立，即第k層上至多有2k-1個結(jié)點。 i=k+1時，因為第k+1層上的結(jié)點是第k層上結(jié)點的孩子，而二叉樹中每個結(jié)點最多有2個孩子，故在第k

31、+1層上最大結(jié)點個數(shù)為第k層上的最大結(jié)點個數(shù)的二倍，即22k-12k。結(jié)論成立。CDEFGHIJKLMNO1112131415數(shù)據(jù)結(jié)構(gòu)共八十五頁性質(zhì)5-2 一棵深度(shnd)為k的二叉樹中，最多有2k-1個結(jié)點，最少有k個結(jié)點。 證明：由性質(zhì)1可知，深度為k的二叉樹中結(jié)點個數(shù)最多= =2k-1；每一層至少(zhsho)要有一個結(jié)點，因此深度為k的二叉樹，至少有k個結(jié)點。深度為k且具有2k-1個結(jié)點的二叉樹一定是滿二叉樹，深度為k且具有k個結(jié)點的二叉樹不一定是斜樹。二叉樹的基本性質(zhì) 二叉樹及存儲結(jié)構(gòu)CDEFGHIJKLMNO111213141

32、5數(shù)據(jù)結(jié)構(gòu)共八十五頁性質(zhì)5-3 在一棵二叉樹中，如果葉子(y zi)結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有: n0n21。 證明: 設(shè)n為二叉樹的結(jié)點總數(shù)，n1為二叉樹中度為1的結(jié)點數(shù)，則有： nn0n1n2 在二叉樹中，除了根結(jié)點外，其余結(jié)點都有唯一的一個分枝進入(jnr)，由于這些分枝是由度為1和度為2的結(jié)點射出的，一個度為1的結(jié)點射出一個分枝，一個度為2的結(jié)點射出兩個分枝，所以有： nn12n21因此可以得到：n0n21 。二叉樹的基本性質(zhì) 二叉樹及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁在有n個結(jié)點的滿二叉樹中，有多少個葉子結(jié)點？因為在滿二叉樹中沒有度為1的結(jié)點，只有度為0的葉子結(jié)點和度為2的分支

33、結(jié)點，所以，n n0 + n2n0n2 + 1 即葉子結(jié)點n0（n + 1）/2 二叉樹的基本(jbn)性質(zhì) 性質(zhì)5-3 在一棵二叉樹中，如果葉子(y zi)結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有: n0n21。 二叉樹及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁性質(zhì)5-4 具有n個結(jié)點(ji din)的完全二叉樹的深度為 log2n +1。 證明：假設(shè)具有n個結(jié)點的完全二叉樹的深度(shnd)為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立 2k-1 n 2k 2k-1-12k-12k-1第k-1層第k層最少結(jié)點數(shù)最多結(jié)點數(shù)完全二叉樹的基本性質(zhì) 二叉樹及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁 log2n + 1log2

34、nlog2nlog2n+1k所在區(qū)間證明：假設(shè)具有n個結(jié)點(ji din)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立 2k-1 n 2k完全(wnqun)二叉樹的基本性質(zhì) 性質(zhì)5-4 具有n個結(jié)點的完全二叉樹的深度為 log2n +1。 對不等式取對數(shù)，有： k-1log2nk即： log2nklog2n+1由于k是整數(shù)，故必有k log2n +1。 二叉樹及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁性質(zhì)(xngzh)5-5 對一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1in）的結(jié)點（簡稱為結(jié)點i），有： (1) 如果i1，則結(jié)點i的雙親結(jié)點的序號為 i/2

35、； 如果i1，則結(jié)點i是根結(jié)點，無雙親結(jié)點。 (2) 如果2in，則結(jié)點i的左孩子的序號為2i； 如果2in，則結(jié)點i無左孩子。 (3) 如果2i1n，則結(jié)點i的右孩子的序號為2i1； 如果2i1n，則結(jié)點 i無右孩子。 完全二叉樹的基本(jbn)性質(zhì) 二叉樹及存儲結(jié)據(jù)結(jié)構(gòu)共八十五一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號(bin ho)，則 結(jié)點i的雙親結(jié)點為 i/2； 結(jié)點i的左孩子為2i； 結(jié)點i的右孩子為2i1。 性質(zhì)5表明，在完全(wnqun)二叉樹中，結(jié)點的層序編號反映了結(jié)點之間的邏輯關(guān)系。完全二叉樹的基本性質(zhì) 二叉樹及存儲

36、結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)順序存儲結(jié)構(gòu)(jigu)二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的結(jié)點，并且結(jié)點的存儲位置（下標）應(yīng)能體現(xiàn)結(jié)點之間的邏輯關(guān)系父子關(guān)系。 如何利用數(shù)組下標來反映結(jié)點之間的邏輯關(guān)系?完全二叉樹和滿二叉樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系 。數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu) A B C D E F G H I J數(shù)組下標 1 2 3 4 5 6 7 8 9 10完全(wnqun)二叉樹的順序存儲以編號為下標CDEFGHIJ數(shù)據(jù)結(jié)構(gòu)共八十五頁二叉樹及存儲(cn ch)結(jié)構(gòu)二叉樹的順序存儲ABCDEFG數(shù)組下標 1