大學計算機基礎第4章數據結構

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

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

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

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

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

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

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

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

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

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

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)數據結構共八十五頁線性表的順序存儲結構(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)的順序存儲：數據結構共八十五頁線性表的順序存儲結構(jigu)33

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

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

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

15、 2) 刪除第i個結點 3) 返回操作結果信息(成功與否)plista2a1ai-1ai+1aippq數據結構共八十五頁棧的概念(ginin)及實現棧：限定僅在表尾進行插入(ch r)和刪除操作的線性表。空棧：不含任何數據元素的棧。 （a1, a2, , an）棧頂棧底允許插入和刪除的一端稱為棧頂，另一端稱為棧底。 a1a2a3數據結構共八十五頁棧的概念(ginin)及實現a1a2a3入棧出棧棧底棧頂插入(ch r)：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖數據結構共八十五頁棧的概念(ginin)及實現棧的操作(cozu)特性：后進先出a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓

16、棧刪除：出棧、彈棧棧頂棧的示意圖數據結構共八十五頁棧的概念(ginin)及實現例：有三個元素按a、b、c的次序依次(yc)進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂 情況1：出棧序列：cba數據結構共八十五頁棧的概念(ginin)及實現例：有三個元素按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出）只一種情況數據結構共八十五頁進一步的例題(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)的只有一種數據結構共八十五頁 一個棧的輸入序列(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 u)共八十五頁棧的概念(ginin)及實現棧的順序存儲結構(jigu)及實現 順序棧棧的順序存儲結構如何改造數組實現棧的順序存儲？ 0 1 2 3 4 5 6 7 8a1確定用數組的哪一端表示棧底。附設指針top指示棧頂元素在數組中的位置。 top數據結構共八十五頁棧的概念(ginin)及實現出棧：top減1進棧：top加1?？眨簍op= -1 0 1 2 3 4 5 6 7 8a1topa2topa3top棧滿：top= MAX_SIZE棧的順序存儲結

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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