第四章 數據結構

1、13第第1章章 緒論緒論第第2章章 線性表線性表第第3章章 棧和隊列棧和隊列 第第4章章 串串第第5章章 數組和廣義表數組和廣義表第第6 6章章 樹和二叉樹樹和二叉樹 第第7章章 圖圖第第8章章 查找查找第第9章章 排序排序目目 錄錄45（a1, a2, ai-1，ai, ai1 ，, an）2.1 線性表的邏輯結構線性表的邏輯結構 用數據元素的有限序列表示用數據元素的有限序列表示n=0時稱為時稱為數據元素數據元素線性起點線性起點ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標，下標，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素總為元素總個數，即表個數，即表

2、長。長?？毡砜毡砭€性終點線性終點6 （ A, B, C, D, , Z）學號學號姓名姓名性別性別年齡年齡班級班級012003010622陳建武陳建武男男 192003級電信級電信0301班班012003010704趙玉鳳趙玉鳳女女 182003級電信級電信0302班班012003010813王王 澤澤男男 192003級電信級電信0303班班012003010906薛薛 荃荃男男 192003級電信級電信0304班班012003011018王 春男 19 192003級電信級電信0305班班： ：例例2 分析學生情況登記表是什么結構。分析學生情況登記表是什么結構。分析：分析：數據元素都是同類型

3、（數據元素都是同類型（記錄記錄），元素間關系是線性的。），元素間關系是線性的。分析：分析： 數據元素都是同類型（數據元素都是同類型（字母字母），）， 元素間關系是線性的。元素間關系是線性的。例例1 分析分析26 個英文字母組成的英文表是什么結構。個英文字母組成的英文表是什么結構。返回本章目錄返回本章目錄72.2 線性表的順序表示和運算線性表的順序表示和運算2.2.1 順序表的表示順序表的表示2.2.2 順序表的運算順序表的運算2.2.3 順序表的運算效率分析順序表的運算效率分析返回本章目錄返回本章目錄82.2.1 順序表的表示順序表的表示用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次的存儲單元依次

4、存儲線性表的元素。存儲線性表的元素。把邏輯上相鄰的數據元素存儲在物把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元中的存儲結構。理上相鄰的存儲單元中的存儲結構。線性表的順序表示又稱為線性表的順序表示又稱為順序存儲結構順序存儲結構或順序映像。或順序映像。順序存儲定義：順序存儲定義：順序存儲方法：順序存儲方法：特點：特點：邏輯上相鄰的元素，物理上也相鄰邏輯上相鄰的元素，物理上也相鄰可以利用可以利用數組數組VnVn來實現來實現注意：在注意：在C C語言中數組的下標是從語言中數組的下標是從0 0開始，即：開始，即： VnVn的有效范圍是從的有效范圍是從 V0V0Vn-1Vn-191. 邏輯上相鄰的數據

5、元素，其物理上也相鄰；邏輯上相鄰的數據元素，其物理上也相鄰；2. 若已知表中首元素在存儲器中的位置，則其他元若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出素存放位置亦可求出（利用數組利用數組VnVn的的下標下標）。）。設首元素設首元素a1的存放地址為的存放地址為LOC(a1)（稱為稱為首地址首地址），），設每個元素占用存儲空間（地址長度）為設每個元素占用存儲空間（地址長度）為L字節(jié)，字節(jié)，則表中任一數據元素的則表中任一數據元素的存放地址存放地址為：為： LOC ( ai+1 ) = LOC( ai ) + L 對上述公式的解釋如圖所示對上述公式的解釋如圖所示線性表順序存儲特點：線

6、性表順序存儲特點：10a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內容內容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L L線性表的順序存儲結構示意圖線性表的順序存儲結構示意圖11設有一維數組設有一維數組，下標的范圍是，下標的范圍是到到，每個數，每個數組元素用相鄰的組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲器按字節(jié)編址，存儲。存儲器按字節(jié)編址，設存儲數組元素設存儲數組元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是，則則 的第一個字

7、節(jié)的地址是多少？的第一個字節(jié)的地址是多少？113但此題要注意下標起點略有不同：但此題要注意下標起點略有不同：LOC( M3 ) = 98 + 5 (4-1) =113解：解：已知地址計算通式為：已知地址計算通式為：LOC(ai) = LOC(a1) + L *（i-1）例例1 112 char V30;void build() /*字母線性表的生成，即字母線性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心語句：核心語句：1)1)用數組用數組V來存放來存放26個英文字母組成的線性表（個英文字母組成的線性表（a，b，c

8、，z），寫出在順序結構上），寫出在順序結構上生成生成和和顯示顯示該表的該表的C語言語言程序。程序。2.2.2 2.2.2 順序表的運算（或操作）順序表的運算（或操作）13void main(void) /*主函數主函數，字母線性表的，字母線性表的生成和輸出生成和輸出*/ n=26; /* n n是表長，是數據元素的個數，而不是是表長，是數據元素的個數，而不是V V的的 實際下標實際下標*/build( );display( );void display( ) /*字母線性表的顯示，即字母線性表的顯示，即讀表操作讀表操作*/ int i;for( i=0; i=i; j )aj+1=a j ;

9、a i =x; n+;/ / 元素后移一個位置元素后移一個位置/ / 插入插入x x / / 表長加表長加1 1 核核心心語語句：句：3)3)插入插入16實現步驟：實現步驟：將第將第i+1 至第至第n 位的元素向前移動一個位置；位的元素向前移動一個位置；表長減表長減1。注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法?應當有應當有1in 或或 i=1, n刪除線性表的第刪除線性表的第i i個位置上的元素個位置上的元素for ( j=i+1; j=n; j+ )aj-1=aj; n-;/ / 元素前移一個位置元素前移一個位置/ / 表長減表長減1 1 核心語句：核心語

10、句：4)4)刪除刪除順序表插入和刪除的完整程序請同學們自編。順序表插入和刪除的完整程序請同學們自編。172.2.3 順序表的運算效率分析順序表的運算效率分析在插入或刪除運算中在插入或刪除運算中,算法時間主要耗費在算法時間主要耗費在移動元素移動元素的操作上，因此計算時間復雜度的大小取決于移動元素的操作上，因此計算時間復雜度的大小取決于移動元素的個數的個數,而移動元素的個數取決于插入或刪除元素的位置而移動元素的個數取決于插入或刪除元素的位置.思考：思考：若插入在尾結點之后，則根本無需移動（特別快）；若插入在尾結點之后，則根本無需移動（特別快）；若插入在首結點之前，則表中元素全部要后移（特別慢）；若

11、插入在首結點之前，則表中元素全部要后移（特別慢）；討論討論1：若在長度為若在長度為 n 的線性表的第的線性表的第 i 位前位前 插入插入一個元素，一個元素，則向后移動元素的次數則向后移動元素的次數f(n)為為:f(n) = n i + 1時間效率分析時間效率分析:注意注意順序表在存儲結構中是均勻有序的順序表在存儲結構中是均勻有序的, ,所以只要知道順所以只要知道順序表的地址和數據元素的長度和序號序表的地址和數據元素的長度和序號, ,就能知道每個就能知道每個數據元素的實際地址數據元素的實際地址. .因此因此, ,對表內數據元素進行訪對表內數據元素進行訪問、修改運算的速度快問、修改運算的速度快.

12、.所以順序表多用于查找頻繁、所以順序表多用于查找頻繁、很少增刪的場合很少增刪的場合, ,例如工程手冊中的數據表例如工程手冊中的數據表. .18鏈式存儲結構鏈式存儲結構本節(jié)小結本節(jié)小結線性表線性表順序存儲結構特點順序存儲結構特點：邏輯關系上相鄰的兩個元素：邏輯關系上相鄰的兩個元素在物理存儲位置上也相鄰；在物理存儲位置上也相鄰；優(yōu)點：優(yōu)點：可以隨機存取表中任一元素，查找方便快捷；可以隨機存取表中任一元素，查找方便快捷；缺點：缺點：在插入或刪除某一元素時，需要移動大量元素。在插入或刪除某一元素時，需要移動大量元素。解決問題的思路：解決問題的思路：改用另一種線性存儲方式：改用另一種線性存儲方式：返回本

13、章目錄返回本章目錄192.3 線性表的鏈式表示和運算線性表的鏈式表示和運算2.3.1 鏈表的表示鏈表的表示2.3.2 鏈表的運算鏈表的運算2.3.3 鏈表的運算效率分析鏈表的運算效率分析返回本章目錄返回本章目錄20鏈式存儲結構特點：鏈式存儲結構特點：其結點在存儲器中的位置是其結點在存儲器中的位置是隨意隨意的，的，即邏輯上相鄰的數據元素在物理上不一定相鄰。如何實現？通過來實現！讓每個存儲結點都包含兩部分：讓每個存儲結點都包含兩部分：數據域數據域和和指針域指針域指針指針指針指針指針指針或或樣式樣式:數據域：數據域：存儲存儲元素數值數據元素數值數據指針域：指針域：存儲直接后繼或存儲直接后繼或者直接前

14、驅的存儲位置者直接前驅的存儲位置2.3.1 鏈表的表示鏈表的表示21例：請畫出例：請畫出26 26 個英文字母表的鏈式存儲結構。個英文字母表的鏈式存儲結構。該字母表在內存中鏈式存放的樣式舉例如下：該字母表在內存中鏈式存放的樣式舉例如下： 解：解：該字母表的邏輯結構為：該字母表的邏輯結構為：（ a, b, ,y, za, b, ,y, z）鏈表存放示意圖如下：鏈表存放示意圖如下： a1heada2/an 討論討論1 ：每個存儲結點都包含兩部分：數據域和：每個存儲結點都包含兩部分：數據域和 。討論討論2：在單鏈表中，除了在單鏈表中，除了首元結點首元結點外，任一結點的存儲位置外，任一結點的存儲位置

15、由由 指示。指示。 其直接前驅結點的鏈域的值其直接前驅結點的鏈域的值指針域指針域(鏈域鏈域)221）結點：）結點：數據元素的存儲映像。由數據域和指針域兩部分組成；數據元素的存儲映像。由數據域和指針域兩部分組成；2）鏈表：）鏈表： n n 個結點由個結點由指針鏈指針鏈組成一個鏈表。它是線性表的鏈式組成一個鏈表。它是線性表的鏈式存儲映像存儲映像，稱為線性表的鏈式存儲結構稱為線性表的鏈式存儲結構。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結點只有一個指針域的鏈表，稱為結點只有一個指針域的鏈表，稱為單鏈表單鏈表或或線性鏈表線性鏈表；有兩個指針域的鏈表，稱為有兩個指針域的

16、鏈表，稱為雙鏈表雙鏈表；有多個指針域的鏈表，稱為有多個指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2an循環(huán)鏈表循環(huán)鏈表示圖：示圖：(2) 與鏈式存儲有關的術語：與鏈式存儲有關的術語：234）頭指針、頭結點和首元結點的區(qū)別）頭指針、頭結點和首元結點的區(qū)別頭指針頭指針頭結點頭結點首元結點首元結點a1heada2infoan頭指針頭指針是指向鏈表中第一個結點（或為頭結點、或為首元是指向鏈表中第一個結點（或為頭結點、或為首元結點）的指針；結點）的指針；頭結點頭結點是在鏈表的首元結點之前是在鏈表的首元結點之前附設附設的一個結點；數據域的一個結點；

17、數據域內只放空表標志和表長等信息，它不計入表長度。內只放空表標志和表長等信息，它不計入表長度。首元結點首元結點是指鏈表中存儲線性表第一個數據元素是指鏈表中存儲線性表第一個數據元素a a1 1的結點。的結點。 示意圖如下：示意圖如下：24 對于指向結構類型的指針變量，可說明為：對于指向結構類型的指針變量，可說明為： *p, *q; /或用或用 struct *p , *q; /注：上面已經定義了注：上面已經定義了node為用戶自定義的為用戶自定義的lilylily類型。類型。 類型定義和變量說明可以合寫為：類型定義和變量說明可以合寫為： lily /lilylily是自定義結構類型名稱是自定義結

18、構類型名稱 char data; /定義數據域的變量名及其類型定義數據域的變量名及其類型 lily *next; /定義指針域的變量名及其類型定義指針域的變量名及其類型node，*pointer; /nodenode是是lilylily結構類型的類型替代結構類型的類型替代, , * *pointerpointer是指針型的是指針型的lilylily結構類型的替代，也是數據類型結構類型的替代，也是數據類型* */ /附：附： 補充結構數據類型的補充結構數據類型的C表示法表示法如何具體編程來建立如何具體編程來建立和訪問鏈表？和訪問鏈表？鏈表的實現鏈表的實現252.3.2 鏈表的運算鏈表的運算（1

19、1） 單鏈表的建立和輸出單鏈表的建立和輸出（2 2） 單鏈表的修改單鏈表的修改（3 3） 單鏈表的插入單鏈表的插入（4 4） 單鏈表的刪除單鏈表的刪除26（1） 單鏈表的建立和輸出單鏈表的建立和輸出例：用例：用單鏈表單鏈表結構來存放結構來存放26個英文字母組成的線個英文字母組成的線性表（性表（a，b，c，z）,請寫出請寫出C語言程序。語言程序。實現思路：實現思路：先開辟頭指針，然后陸續(xù)為每個結點開辟存儲先開辟頭指針，然后陸續(xù)為每個結點開辟存儲空間并及時賦值，后繼結點的地址要空間并及時賦值，后繼結點的地址要提前提前送給前面的指針。送給前面的指針。先挖先挖“坑坑”, ,后種后種“蘿蘿卜卜”！27t

20、ypedef struct nodechar data; struct node *next;node; node *p,*q,*head; /一般需要一般需要3 3個指針變量個指針變量int n ; / / 數據元素的個數數據元素的個數int m=sizeof(node); / /* *結構類型定義好之后，每個變量結構類型定義好之后，每個變量的長度就固定了，的長度就固定了，m m求一次即可求一次即可* */ /將全局變量及函數提前說明：將全局變量及函數提前說明：28新手特別容易忘記！新手特別容易忘記！ int i;head=(node*)malloc(m); /m=sizeof(node)

21、前面已求出前面已求出p=head;for( i=1; idata=i+a-1; / 第一個結點值為字符第一個結點值為字符ap-next=(node*)malloc(m); /為后繼結點為后繼結點“挖坑挖坑”！p=p-next； /讓指針變量讓指針變量P指向后一個結點指向后一個結點p-data=i+a-1; /最后一個元素要單獨處理最后一個元素要單獨處理p-next=NULL ; / /單鏈表尾結點的指針域要置空！單鏈表尾結點的指針域要置空！void build( ) /字母鏈表的生成字母鏈表的生成。要一個個慢慢鏈入要一個個慢慢鏈入29p=head;while (p) /當指針不空時循環(huán)當指針不

22、空時循環(huán) printf(%c,p-data); p=p-next; /讓指針不斷讓指針不斷“順藤摸瓜順藤摸瓜” 討論：要統(tǒng)計鏈表中數據元素的個數，該如何改寫？討論：要統(tǒng)計鏈表中數據元素的個數，該如何改寫？ sum+;sum+;sum=0;sum=0;void display() /*字母鏈表的輸出字母鏈表的輸出*/30（2） 單鏈表的修改單鏈表的修改(或讀?。┗蜃x取）思路：思路：要修改第要修改第i個數據元素，必須從頭指針起一直找到該結個數據元素，必須從頭指針起一直找到該結點的指針點的指針p，然后才能執(zhí)行，然后才能執(zhí)行p-data=new_value 。修改修改第第i i個數據元素的操作函數可寫

23、為：個數據元素的操作函數可寫為：GetElem_L(LinkList L, int i, ElemType &e)p=L-next; int j=1; /帶頭結點的鏈表帶頭結點的鏈表while(p&jnext; +j; /p非空且非空且ji ) return ERROR; /p為空或為空或ji p-data =e; /若是讀取則為：若是讀取則為：e=p-data; return OK;/ GetElem_L缺點：缺點：想尋找單鏈表中第想尋找單鏈表中第i i個元素，只能從頭指針開始逐一個元素，只能從頭指針開始逐一查詢（查詢（順藤摸瓜順藤摸瓜），無法隨機存取），無法隨機存取 。31

24、在鏈表中插入一個元素在鏈表中插入一個元素X X 的示意圖如下：的示意圖如下：X Xsabp鏈表插入的核心語句：鏈表插入的核心語句：p-nexts-nextX X 結點的生成方式：結點的生成方式：s=(node*)malloc(m);s-data=X X ;s-next= ?bapX X （3） 單鏈表的插入單鏈表的插入32在鏈表中刪除某元素在鏈表中刪除某元素b b的示意圖如下：的示意圖如下：c a bp刪除動作的核心語句刪除動作的核心語句（要借助輔助指針變量（要借助輔助指針變量q q）：）：q = p-next; /首先保存首先保存b b的指針，靠它才能找的指針，靠它才能找c c；p-next

25、=q-next; /將將a a、c c兩結點相連，淘汰兩結點相連，淘汰b b結點；結點；free(q) ； /徹底釋放徹底釋放b b結點空間結點空間p-next(p-next) - nextq（4） 單鏈表的刪除單鏈表的刪除332.3.3 鏈表的運算效率分析鏈表的運算效率分析（1） 查找查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度查找的時間復雜度遠遠大于順序表遠遠大于順序表。時間效率分析時間效率分析（2） 插入和刪除插入和刪除 因線性鏈表不需要移動元素，只要修改指針，一般情況下時因線性鏈表不需要移動元素，只要修改指針

26、，一般情況下時間復雜度間復雜度 遠遠小于順序表遠遠小于順序表。34結 束35第第4 4章章 樹和二叉樹樹和二叉樹（Tree & Binary Tree）4.1 樹的基本概念樹的基本概念4.2 二叉樹二叉樹4.3 遍歷二叉樹遍歷二叉樹特點：特點：非線性結構，一個直接前驅，但可能有多個非線性結構，一個直接前驅，但可能有多個直接后繼。直接后繼。（一對多或（一對多或1:n1:n）364.14.1 樹的基本概念4.1.1 樹的定義樹的定義4.1.2 若干術語若干術語4.1.3 邏輯結構邏輯結構4.1.4 存儲結構存儲結構4.1.5 樹的運算樹的運算37注注1：過去許多書籍中都定義樹為過去許多書籍

27、中都定義樹為n1，曾經有，曾經有“空樹不是空樹不是樹樹”的說法，但現在樹的定義已修改。的說法，但現在樹的定義已修改。注注2：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。由一個或多個由一個或多個( (n0n0) )結點組成的有限集合結點組成的有限集合T T，有且僅有，有且僅有一一個結點稱為根個結點稱為根（rootroot），），當當n1n1時，其余的結點分為時，其余的結點分為m m(m0)(m0)個個互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每個集合本身又是棵樹，。每個集合本身又是棵樹，被稱作這個根的被稱作這個根的子樹子樹 。38結點的直接前驅

28、結點的直接前驅結點的直接后繼結點的直接后繼同一雙親下的同層結點（孩子之間互稱兄弟）同一雙親下的同層結點（孩子之間互稱兄弟）即雙親位于同一層的結點（但并非同一雙親）即雙親位于同一層的結點（但并非同一雙親）即從根到該結點所經分支的所有結點即從根到該結點所經分支的所有結點即該結點下層子樹中的任一結點即該結點下層子樹中的任一結點ABCGEIDHFJFLK 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結點即根結點(沒有前驅沒有前驅)即終端結點即終端結點(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如刪除例如刪除A后的子樹個數后的子樹個數)雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖

29、先祖先子孫子孫結點各子樹從左至右有序，不能互換（左為第一）結點各子樹從左至右有序，不能互換（左為第一）結點各子樹可互換位置。結點各子樹可互換位置。39即樹的數據元素即樹的數據元素結點的孩子數量結點的孩子數量結點結點結點的度結點的度結點的層次結點的層次終端結點終端結點分支結點分支結點樹的度樹的度樹的深度樹的深度(或高度或高度)ABCGEIDHFJFLK從根到該結點的層數（根結點算第一層）從根到該結點的層數（根結點算第一層）即度為即度為0的結點，即葉子的結點，即葉子即度不為即度不為0的結點（也稱為內部結點）的結點（也稱為內部結點）所有結點度中的最大值（所有結點度中的最大值（Max各結點的度各結點的

30、度）指所有結點中最大的層數（指所有結點中最大的層數（Max各結點的層次各結點的層次）問：問：右上圖中的結點數右上圖中的結點數 ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4（有幾個直接后繼就是幾度，亦稱（有幾個直接后繼就是幾度，亦稱“次數次數”）40一對多（一對多（1:n1:n），），有多個直接后繼（如家譜有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結點，樹、目錄樹等等），但只有一個根結點，且且子樹之間互不相交。子樹之間互不相交。 討論討論1：樹是非線性結構，該怎樣存儲？樹是非線性結構，該怎樣存儲？特點：特點：仍然有順序存儲、鏈式存儲等方式。仍然有順序存儲、鏈式存儲等方式。

31、 41討論討論3：樹的樹的鏈式存儲鏈式存儲方案應該怎樣制定？方案應該怎樣制定？復原困難復原困難可用多重鏈表：可用多重鏈表：一個前趨指針，一個前趨指針，n n個后繼指針。個后繼指針。 細節(jié)問題：細節(jié)問題： 樹中結點的結構類型樣式該如何設計？樹中結點的結構類型樣式該如何設計？ 即應該設計成即應該設計成“等長等長”還是還是“不等長不等長”？ 缺點：缺點： 等長結構太浪費（每個結點的度不一定相同）；等長結構太浪費（每個結點的度不一定相同）； 不等長結構太復雜（要定義好多種結構類型）。不等長結構太復雜（要定義好多種結構類型）。先研究最簡單、最有規(guī)律的樹，然先研究最簡單、最有規(guī)律的樹，然后設法把一般的樹轉

32、化為簡單樹。后設法把一般的樹轉化為簡單樹?？梢?guī)定為：可規(guī)定為： 從上至下、從左至右將樹的結點依次存入內存。從上至下、從左至右將樹的結點依次存入內存。重大缺陷：重大缺陷：解決思路：解決思路：不能唯一復原就沒有實用價值！不能唯一復原就沒有實用價值！討論討論2：樹的樹的順序存儲順序存儲方案應該怎樣制定？方案應該怎樣制定？42多叉樹轉為多叉樹轉為了二叉樹了二叉樹轉換的步驟: 1. 保留每個結點與最左邊孩子的邊，去掉其余的邊。 2. 連接每個結點與其原相鄰兄弟結點的邊。 3. 以樹根結點為軸心，將整棵樹順時針旋轉45度，即 可得到轉換后的二叉樹。43要明確：要明確：1. 普通樹（即多叉樹）若不轉化為二叉

33、樹，則運算很難實現。普通樹（即多叉樹）若不轉化為二叉樹，則運算很難實現。2. 二叉樹的運算仍然是插入、刪除、修改、查找、排序等，二叉樹的運算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在但這些操作必須建立在對樹結點能夠對樹結點能夠“遍歷遍歷”的基礎上！的基礎上！444.2 二叉樹二叉樹為何要重點研究每結點最多只有兩個為何要重點研究每結點最多只有兩個 “ “叉叉” ” 的樹？的樹？二叉樹的結構最簡單，規(guī)律性最強；二叉樹的結構最簡單，規(guī)律性最強；可以證明，所有樹都能轉為唯一對應的二叉樹，可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。不失一般性。4.2.1 二叉樹的定義二叉樹的定

34、義4.2.2 二叉樹的類型二叉樹的類型4.2.3 二叉樹的存儲結構二叉樹的存儲結構45定義：定義：是是n（n0）個結點的有限集合，由一個根結點以及兩棵）個結點的有限集合，由一個根結點以及兩棵互不相交的、分別稱為互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。邏輯結構：邏輯結構： 一對二（一對二（1:2） 基本特征基本特征: 每個結點最多只有兩棵子樹（不存在度大于每個結點最多只有兩棵子樹（不存在度大于2 2的結點）；的結點）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。 基本形態(tài)：基本形態(tài)：46順序二叉樹：順序二叉樹：深度為深度為k 的的、有有n個結點個結

35、點的二叉樹，當且僅當其每一個結點都與的二叉樹，當且僅當其每一個結點都與深度為深度為k 的滿二叉樹中編號從的滿二叉樹中編號從1至至n的結的結點一一對應。點一一對應。AOBCGEKDJFIHNML深度為深度為4 4的滿二叉樹的滿二叉樹順序二叉樹順序二叉樹ABCGEIDHFJ為何要研究為何要研究這順序二叉這順序二叉樹形式？樹形式？滿二叉樹：滿二叉樹：一棵深度為一棵深度為k 且有且有2k -1個結點的二叉樹。個結點的二叉樹。 （特點：每層都（特點：每層都“充滿充滿”了結點）了結點）完全二叉樹：完全二叉樹：結點的度數或者為結點的度數或者為0、或、或者為者為2的二叉樹的二叉樹 完全二叉樹完全二叉樹ABCE

36、IDH474.2.3 4.2.3 二叉樹的存儲結構二叉樹的存儲結構一、順序存儲結構一、順序存儲結構按二叉樹的結點按二叉樹的結點“自上而自上而下、從左至右下、從左至右”編號，用編號，用一組連續(xù)的存儲單元存儲。一組連續(xù)的存儲單元存儲。123456789問：順序存儲后能否復原成唯一對應的二叉樹形狀？問：順序存儲后能否復原成唯一對應的二叉樹形狀？答：答：若是順序若是順序/ /滿二叉樹則可以做到唯一復原。滿二叉樹則可以做到唯一復原。 而且有規(guī)律：下標值為而且有規(guī)律：下標值為i i的雙親，其左孩子的下標值必為的雙親，其左孩子的下標值必為2i2i，其右孩子的下標值必為，其右孩子的下標值必為2i2i1 1 例如，對應例如，對應22的兩個孩子必為的兩個孩子必為44和和5,5,即即B B的左孩子必的左孩子必是是D,D,右孩子必為右孩子必為E E。48討論：討論：不