第一講緒論了解數據結構有關概念的含義，特別是數據的邏輯結構和存儲結構之間的關系；（重點）熟悉類C語言的書寫規范；了解計算算法時間復雜度的方法。（難點）06/08/20231第一講緒論了解數據結構有關概念的含義，特別是數據的邏輯結構1數據結構的定義按某種邏輯關系組織起來的一批數據（或稱帶結構的數據元素的集合）應用計算機語言并按一定的存儲表示方式把它們存儲在計算機的存儲器中，并在其上定義了一個運算的集合。數據結構的定義按某種邏輯關系組織起來的一批數據（或稱帶結構的2基本概念和術語【數據】是對信息的一種符號表示。是可以輸入計算機中， 能被計算機識別處理和輸出的一切符號集合。【數據元素】是數據的基本單位，在計算機中通常作為一個 整體進行考慮和處理。也稱為記錄。【數據項】一個數據元素可由若干個數據項組成。是數據不 可分割的最小單位。【數據對象】是性質相同的數據元素的集合。是數據的一個 子集。06/08/20233【數據結構】相互之間存在一種或多種特定關系的數據 元素的集合基本概念和術語【數據】是對信息的一種符號表示。是可以輸入計算3計算機如何解決問題06/08/20234問題機外表示處理要求邏輯結構基本運算數學模型存儲結構編程實現實現建模求精研究數據結構是為了幫計算機解決問題！計算機如何解決問題29/07/20234問題機外表示邏輯結構4數據結構的研究內容06/08/20235【數據結構的三個方面研究內容】具體來說，數據結構包含三個方面的內容，即數據的邏輯結構，數據的存儲結構和對數據所施加的運算（操作）。

數據的邏輯結構（面向人類）

數據的存儲結構（面向計算機）

數據的運算（操作）：檢索、排序、插入、刪除、修改等

線性結構

非線性結構順序存儲鏈式存儲線性表棧隊列樹形結構圖形結構散列存儲索引存儲串及數組數據結構的研究內容29/07/20235【數據結構的三個方面5四種基本邏輯結構06/08/20236【集合】——數據元素間除了“同屬于一個集合”外，無其他關系。【線性結構】——1對1的關系比如線性表、棧、隊列。【樹形結構】——1對多的關系比如樹。【圖形結構】——多對多的關系比如圖。四種基本邏輯結構29/07/20236【集合】——數據元素6算法與數據結構算法與數據結構關系密切選擇的數據結構是否恰當直接影響算法的效率；而數據結構的優劣由算法的執行來體現。“算法+數據結構=程序”算法!=程序算法是供人閱讀的，程序是讓機器執行的算法用計算機語言實現時就是程序程序不具有算法的有窮性算法與數據結構算法與數據結構關系密切7算法的概念算法是解決某個特定問題的求解步驟的描述。算法在計算機中表現為指令的有限序列，每條指令表示一個或多個操作。計算機對數據的操作可以分為數值性和非數值性兩種類型。在數值性操作中主要進行的是算術運算；而在非數值性操作中主要進行的是檢索、排序、插入、刪除等等。程序不等于算法：計算機程序是算法的具體實現。06/08/20238算法的概念算法是解決某個特定問題的求解步驟的描述。29/078（1）有窮性：一個算法必須在執行有窮步之后結束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時不會產生二義性。（3）可行性：算法中描述的每一步操作都可以通過已有的基本操作執行有限次實現。（4）輸入：一個算法應該有零個或多個輸入。（5）輸出：一個算法應該有一個或多個輸出。這里所說的輸出是指與輸入有某種特定關系的量。算法的性質（1）有窮性：一個算法必須在執行有窮步之后結束。算法的性質9算法設計的要求正確性（四個境界）沒有語法錯誤對于合法的輸入數據能夠產生滿足要求的輸出對于非法的輸入數據能夠得出滿足規格說明的結果對于任何測試數據都有滿足要求的輸出結果可讀性：便于閱讀、理解和交流健壯性：不合法數據也能合理處理時間效率高和存儲量低06/08/202310算法設計的要求正確性（四個境界）29/07/20231010算法效率的度量方法事后統計方法通過設計好的測試程序和數據，利用計算機測量其運行時間。缺陷：需要先編寫程序；和計算機軟硬件相關；和測試數據相關。事前分析估算方法（我們的選擇）依據統計方法對算法進行估算。m=f(n)，m是語句總的執行次數，n是輸入的規模。和問題輸入規模相關，獨立于程序設計語言和計算機軟硬件

06/08/202311算法效率的度量方法事后統計方法29/07/20231111算法時間復雜度06/08/202312在進行算法分析時，語句的總執行次數T(n)是關于問題規模n的函數，進而分析T(n)隨n的變化情況并確定T(n)的數量級。算法的時間復雜度，也就是算法的時間量度，用“大O記法”記作：T(n)=O(f(n))。由此得到的T(n)的數量級叫“大O階”。它表示隨問題規模n的增大，算法執行時間增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱時間復雜度。其中f(n)是問題規模n的某個函數。一般情況下，T(n)增長越慢，算法越優。算法時間復雜度29/07/202312在進行算法分析時，語句12大O階的數學定義

當n→∞時，有f(n)/g(n)=常數≠0，則稱函數f(n)與g(n)同階,或者說，f(n)與g(n)同一個數量級，記作f(n)=O(g(n))稱上式為算法的時間復雜度,或稱該算法的時間復雜度為O(g(n))。其中,n為問題的規模(大小)的量度。若lim(f(n)/g(n))=lim((2n3+3n2+2n+1)/n3)

=2n→∞n→∞則算法的時間復雜度為O(n3)大O階的數學定義若lim(f(n)/g(n))=lim(13算法空間復雜度06/08/202314

算法的空間復雜度通過計算算法所需的存儲空間實現，算法空間復雜度的計算公式記作：S(n)=O(f(n))，其中，n為問題的規模，f(n)為語句關于n所占存儲空間的函數。

我們主要討論時間復雜度問題。算法空間復雜度29/07/202314 算法的空間復雜度通過14例題解析【例1】數據元素之間的關系在計算機中有幾種表示方法？各有什么特點？答：四種表示方法（1）順序存儲方式。數據元素順序存放，每個存儲結點只含一個元素。存儲位置反映數據元素間的邏輯關系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈式存儲方式。每個存儲結點除包含數據元素信息外還包含一組（至少一個）指針。指針反映數據元素間的邏輯關系。這種方式不要求存儲空間連續，便于動態操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。除數據元素存儲在一地址連續的內存空間外，尚需建立一個索引表，索引表中索引指示存儲結點的存儲位置（下標）或存儲區間端點（下標），兼有靜態和動態特性。（4）散列存儲方式。通過散列函數和解決沖突的方法，將關鍵字散列在連續的有限的地址空間內，并將散列函數的值解釋成關鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關鍵字隨機存取，不能順序存取，也不能折半存取。06/08/202315例題解析【例1】數據元素之間的關系在計算機中有幾種表示方法？15例題解析【例2】有下列運行時間函數：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分別寫出相應的大O表示的運算時間答：(1)O(1)(2)O(n2)(3)O(n3)06/08/202316例題解析【例2】有下列運行時間函數：29/07/202316例題解析【例3】已知如下程序段for(i=n;i>0;i--){ {語句1}x=x+1; {語句2}for(j=n;j>=i;j--) {語句3}y=y+1; {語句4}}語句1執行的頻度為_____________；語句2執行的頻度為_____________；語句3執行的頻度為_____________；語句4執行的頻度為_____________。答：（1）n+1（2）n（3）n(n+3)/2（4）n(n+1)/2例題解析【例3】已知如下程序段17第二講線性表線性結構的定義和特點在數據元素的非空有限集中，有且僅有一個開始結點和一個終端結點，并且所有結點只有一個直接前趨和一個直接后繼。簡言之，線性結構反映結點間的邏輯關系是

一對一。線性結構包括線性表、堆棧、隊列、字符串、數組等等，其中，最簡單、最常用的是線性表。線性表的存儲方法順序存儲：邏輯上相鄰物理上一定相鄰鏈式存儲：邏輯上相鄰物理上不一定相鄰第二講線性表線性結構的定義和特點18順序表順序表——線性表的順序存儲表示順序存儲——用一組地址連續的存儲單元依次存儲線性表的元素，可通過數組來實現。（邏輯上相鄰物理上一定相鄰）

LOC(ai

)=LOC(a1)+(i-1)len（a1為首元素，len為單個元素占用空間長度）順序存儲的優點可以隨機存取表中任一元素O(1)；存儲空間使用緊湊順序存儲的缺點在插入元素時平均需要移動n/2個元素，刪除某一元素時，平均需要移動n-1/2個元素。算法的平均時間復雜度為O(n)預先分配空間需按最大空間分配，利用不充分;表容量難以擴充06/08/202319順序表順序表——線性表的順序存儲表示29/07/20231919鏈表鏈式存儲結構特點用一組任意的存儲單元存儲線性表的數據元素利用指針實現了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數據元素ai，除存儲本身信息外，還需存儲其直接后繼的信息

鏈式存儲結構的優點：結點空間可以動態申請和釋放；數據元素的邏輯次序靠結點的指針來指示，插入和刪除時不需要移動數據元素。鏈式存儲結構的缺點：每個結點的指針域需額外占用存儲空間。當數據域所占字節不多時，指針域所占存儲空間的比重顯得很大。鏈表是非隨機存取結構。對任一結點的操作都要從頭指針依鏈查找該結點，這增加了算法的復雜度O（n）不便于在表尾插入元素：需遍歷整個表才能找到位置。06/08/202320鏈表鏈式存儲結構特點29/07/20232020例題解析【例1】說明在線性表的鏈式存儲結構中，頭指針與頭結點之間的根本區別。答：在線性表的鏈式存儲結構中，頭指針指鏈表的指針，若鏈表有頭結點則是鏈表的頭結點的指針，頭指針具有標識作用，故常用頭指針冠以鏈表的名字。頭結點是為了操作的統一、方便而設立的，放在第一元素結點之前，其數據域一般無意義（當然有些情況下也可存放鏈表的長度、用做監視哨等等），有頭結點后，對在第一元素結點前插入結點和刪除第一結點，其操作與對其它結點的操作統一了。而且無論鏈表是否為空，頭指針均不為空。06/08/202321例題解析【例1】說明在線性表的鏈式存儲結構中，頭指針與頭結點21例題解析 【例2】設順序表va中的數據元素遞增有序。試設計一個算法，將x插入到順序表的適當位置上，以保持該表的有序性。答：voidInsert_SqList(SqListva,intx)/*把x插入遞增有序表va中*/{inti;if(va.length>MAXSIZE)return;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;va.length++;}/*Insert_SqList*/06/08/202322#defineMAXSIZE100typedefstruct{ ElemType*elem; intlength;}SqList；例題解析 【例2】設順序表va中的數據元素遞增有序。試設計22例題解析【例3】設單鏈表結點指針域為next，試寫出刪除鏈表中指針p所指結點的直接后繼的C語言語句。答： q=p->next; p->next=q->next; free(q);06/08/202323例題解析【例3】設單鏈表結點指針域為next，試寫出刪除鏈23例題解析【例4】設單鏈表中某指針p所指結點（即p結點）的數據域為data，鏈指針域為next，請寫出在p結點之前插入s結點的操作。答： 設單鏈表的頭結點的頭指針為head,且pre=head；while(pre->next!=p)pre=pre->next;s->next=p;pre->next=s;06/08/202324例題解析【例4】設單鏈表中某指針p所指結點（即p結點24例題解析【例5】試編寫在帶頭結點的單鏈表中刪除（一個）最小值結點的算法。voiddelete（Linklist&L）答：[題目分析]本題要求在單鏈表中刪除最小值結點。單鏈表中刪除結點，為使結點刪除后不出現“斷鏈”，應知道被刪結點的前驅。而“最小值結點”是在遍歷整個鏈表后才能知道。所以算法應首先遍歷鏈表，求得最小值結點及其前驅。遍歷結束后再執行刪除操作。

voiddelete（LinkedList&L）{∥L是帶頭結點的單鏈表p=L->next；∥p為工作指針。指向待處理的結點。假定鏈表非空。pre=L；∥pre指向最小值結點的前驅。q=p；∥q指向最小值結點，初始假定第一元素結點是最小值結點。while（p->next!=null）{if（p->next->data<q->data）{pre=p；q=p->next；}∥查最小值結點p=p->next；∥指針后移。}pre->next=q->next；∥從鏈表上刪除最小值結點free（q）；∥釋放最小值結點空間}∥結束算法delete。06/08/202325例題解析【例5】試編寫在帶頭結點的單鏈表中刪除（一個）最小值25例題解析【例6】一元稀疏多項式以循環單鏈表按降冪排列，結點有三個域，系數域coef，指數域exp和指針域next；現對鏈表求一階導數，鏈表的頭指針為ha，頭結點的exp域為–1。

voidderivative(ha){q=ha;pa=ha->next;while((1)_______){if((2)____){((3)__);free(pa);pa=((4)_);}else{pa->coef((5)___);pa->exp((6)___);q=((7)__);}pa=((8)________);}}06/08/202326(1)pa!=ha∥或pa->exp!=-1(2)pa->exp==0∥若指數為0，即本項為常數項(3)q->next=pa->next∥刪常數項(4)q->next∥取下一元素(5)=pa->coef*pa->exp(6)--∥指數項減1(7)pa∥前驅后移,或q->next(8)pa->next∥取下一元素例題解析【例6】一元稀疏多項式以循環單鏈表按降冪排列，結點有26第三講棧和隊列棧限定僅在表尾進行插入和刪除的線性表，把這個表尾稱為棧頂。特點后進先出(LIFO表)棧的存儲方法棧的順序存儲——順序棧棧的鏈式存儲——鏈棧06/08/202327第三講棧和隊列棧29/07/20232727關于棧要求掌握的內容06/08/202328

棧的基本概念：LIFO

棧的存儲棧的應用（了解）順序棧（熟練掌握）鏈棧（熟練掌握）初始化取棧頂入棧出棧判斷棧空

棧初始化取棧頂入棧出棧判斷棧空關于棧要求掌握的內容29/07/202328棧的基本概念：28隊列定義06/08/202329

隊列的定義隊列：線性表(queue)特點：先進先出(FIFO結構)。隊尾隊頭下圖是隊列的示意圖：

a1

a2

…

an出隊入隊隊頭隊尾當隊列中沒有元素時稱為空隊列。表尾稱為隊尾(rear)表頭稱為隊頭(front)插入元素稱為入隊刪除元素稱為出隊限定在表的一端插入、另一端刪除。隊列定義29/07/202329隊列的定義隊列：29順序隊列的假溢出問題06/08/202330

在順序隊列中，當尾指針已經指向了隊列的最后一個位置即數組上界時，若再有元素入隊，就會發生“溢出”。

“假溢出”——隊列的存儲空間未滿，卻發生了溢出。rearfrontJ1

J2

J3

J4

rearfrontJ3

J4

(1)、平移元素：把元素平移到隊列的首部。效率低。

解決“假溢出”的問題有兩種可行的方法：(2)、將新元素插入到第一個位置上，構成循環隊列，入隊和出隊仍按“先進先出”的原則進行。

操作效率、空間利用率高。rearfrontJ3

J4

frontrearJ3

J4

順序隊列的假溢出問題29/07/20233030循環隊列06/08/202331隊空條件:front=rear(初始化時：front=rear)隊滿條件：front=(rear+1)%N(N=maxsize)隊列長度：L=（N＋rear－front）%NJ2J3

J1

J4J5frontrear

選用空閑單元法：即front和rear之一指向實元素，另一指向空閑元素。

問2：在具有n個單元的循環隊列中，隊滿時共有多少個元素？n-1個5問1：左圖中隊列長度L=？循環隊列29/07/202331隊空條件:front31例題解析【例1】一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現嗎？12345的輸出呢？答： 43512不可能實現，主要是其中的12順序不能實現； 12345的輸出可以實現，只需壓入一個立即彈出一個即可。06/08/202332例題解析【例1】一個棧的輸入序列是12345，若在入棧的過程32例題解析【例2】如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？答： 435612中到了12順序不能實現； 135426可以實現。06/08/202333例題解析【例2】如果一個棧的輸入序列為123456，能否得到33例題解析【例3】一個棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321； 合計有5種可能性。06/08/202334例題解析【例3】一個棧的輸入序列為123，若在入棧的過程中允34例題解析【例4】簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件。答：設順序存儲隊列用一維數組q[m]表示，其中m為隊列中元素個數，隊列中元素在向量中的下標從0到m-1。設隊頭指針為front，隊尾指針是rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。當front等于-1時隊空，rear等于m-1時為隊滿。由于隊列的性質（“刪除”在隊頭而“插入”在隊尾），所以當隊尾指針rear等于m-1時，若front不等于-1，則隊列中仍有空閑單元，所以隊列并不是真滿。這時若再有入隊操作，會造成假“溢出”。其解決辦法有二，一是將隊列元素向前“平移”（占用0至rear-front-1）；二是將隊列看成首尾相連，即循環隊列（0..m-1）。在循環隊列下，仍定義front=rear時為隊空，而判斷隊滿則用兩種辦法，一是用“犧牲一個單元”，即rear+1=front（準確記是（rear+1）%m=front，m是隊列容量）時為隊滿。另一種解法是“設標記”方法，如設標記tag，tag等于0情況下，若刪除時導致front=rear為隊空；tag=1情況下，若因插入導致front=rear則為隊滿。06/08/202335例題解析【例4】簡述順序存儲隊列的假溢出的避免方法及隊列滿和35第四講串和數組【例1】填空題：1.空格串是指_____________，其長度等于_____________。【答案】（1）由空格字符（ASCII值32）所組成的字符串（2）空格個數2．組成串的數據元素只能是_____________。【答案】字符【解析】串是一種特殊的線性表，其特殊性在于串中的元素只能是字符型數據。3．兩個字符串相等的充分必要條件是_____________。【答案】兩串的長度相等且兩串中對應位置上的字符也相等。4．一個字符串中_____________稱為該串的子串。【答案】任意個連續的字符組成的子序列06/08/202336第四講串和數組【例1】填空題：29/07/20233636例題解析【例2】設計一個算法，將字符串s的全部字符復制到字符串t中，不能利用strcpy函數。答：【算法分析】要實現兩個字符串的復制，實質為兩個字符數組之間的復制，在復制時，一個字符一個字符的復制，直到遇到'\0'，'\0'一同復制過去，'\0'之后的字符不復制。【算法源代碼】voidcopy(chars[],chart[]){inti;for(i=0;s[i]!='\0';i++)t[i]=s[i];t[i]=s[i];}06/08/202337例題解析【例2】設計一個算法，將字符串s的全部字符復制到字符37例題解析【例3】設有一個二維數組A[m][n]，假設A[0][0]存放位置在644，A[2][2]存放位置在676，每個元素占一個空間，問A[3][3]存放在什么位置？答：設數組元素A[i][j]存放在起始地址為Loc（i,j）的存儲單元中。∵Loc（2,2）=Loc（0,0）+2*n+2=644+2*n+2=676.∴n=（676-2-644）/2=15∴Loc（3,3）=Loc（0,0）+3*15+3=644+45+3=692.06/08/202338例題解析【例3】設有一個二維數組A[m][n]，假設A[0]38例題解析【例4】設有一個nn的對稱矩陣A，為了節約存儲，可以只存對角線及對角線以上的元素，或者只存對角線或對角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行存放于一個一維數組B中，稱之為對稱矩陣A的壓縮存儲方式。試問：（1）存放對稱矩陣A上三角部分或下三角部分的一維數組B有多少元素？（2）若在一維數組B中從0號位置開始存放，則對稱矩陣中的任一元素aij在只存下三角部分的情形下應存于一維數組的什么下標位置？給出計算公式。答：（1）數組B共有1＋2+3++n=（n+1）*n/2個元素。（2）只存下三角部分時，若ij，則數組元素A[i][j]前面有i-1行（1i-1，第0行第0列不算），第1行有1個元素，第2行有2個元素，，第i-1行有i-1個元素。在第i行中，第j號元素排在第j個元素位置，因此，數組元素A[i][j]在數組B中的存放位置為：1+2++（i-1）+j=（i-1）*i/2+j若i<j，數組元素A[i][j]在數組B中沒有存放，可以找它的對稱元素A[j][i]。在數組B的第（j-1）*j/2+i位置中找到。如果第0行第0列也計入，數組B從0號位置開始存放，則數組元素A[i][j]在數組B中的存放位置可以改為：當ij時，=i*（i+1）/2+j；當i<j時，=j*（j+1）/2+i。06/08/202339例題解析【例4】設有一個nn的對稱矩陣A，為了節約存儲，可39第五講樹06/08/202340二叉樹的定義定義：是n（n≥0）個結點的有限集合，由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。邏輯結構：一對二（1：2）

基本特征:每個結點最多只有兩棵子樹（不存在度大于2的結點）；左子樹和右子樹次序不能顛倒（有序樹）。滿二叉樹完全二叉樹第五講樹29/07/202340二叉樹的定義40二叉樹的性質（能證明嗎）06/08/202341【性質1】在二叉樹的第i

層上至多有2i-1個結點(i≥1)。【性質2】深度為k的二叉樹至多有2k

-1個結點（k≥1）。【性質3】對任何一棵二叉樹T，如果其葉子數為n0，度為2的結點數為n2，則n0=n2+1。（葉子數＝結點的度為2的結點數＋1）【性質4】具有n

個結點的完全二叉樹的深度為

log2n+1或者log2(n+1)。【性質5】n個結點的完全二叉樹，結點按層次編號有：

1)i的雙親是，如果i=1時為根（無雙親）；

2)i的左孩子是2i，如果2i>n，則無左孩子；3)i的右孩子是2i+1，如果2i+1>n則無右孩子。二叉樹的性質（能證明嗎）29/07/202341【性質1】在41例題解析1．深度為H的完全二叉樹至少有_____________個結點；至多有_____________個結點；H和結點總數N之間的關系是_____________。【答案】（1）2H-1 （2）2H-1 （3）H=log2N+12．一棵有n個結點的滿二叉樹有_____________個度為1的結點，有_____________個分支（非終端）結點和_____________個葉子，該滿二叉樹的深度為_____________。【答案】（1）0 （2）(n-1）/2 （3）(n+1）/2 （4）log2n

+13．對于一個具有n個結點的二叉樹，當它為一棵_____________時，具有最小高度，當它為一棵_____________時，具有最大高度。【答案】（1）完全二叉樹 （2）單支樹，樹中任一結點（除最后一個結點是葉子外），只有左子女或只有右子女。4．已知二叉樹有50個葉子結點，則該二叉樹的總結點數至少是_____________。【答案】99【解析】在二叉樹中，N0=N2+1，所以，有50個葉子結點的二叉樹，有49個度為2的結點。若要使該二叉樹的結點數最少，度為1的結點應為0個，即總結點數N=N0+N1+N2=99。06/08/202342例題解析1．深度為H的完全二叉樹至少有__________42二叉樹的存儲（一）06/08/202343二叉樹存儲方法有順序存儲和鏈式存儲二叉樹順序存儲結構完全二叉樹：用一組地址連續的存儲單元依次自上而下、自左至右存儲結點元素，即將編號為i的結點元素存儲在一維數組中下標為

i

的分量中（不用下標為0存儲單元）。此順序存儲結構僅適用于完全二叉樹不是完全二叉樹怎么辦？一律轉為完全二叉樹！方法很簡單，將各層空缺處統統補上“虛結點”，其內容為空。缺點：①浪費空間；②插入、刪除不便二叉樹的存儲（一）29/07/202343二叉樹存儲方法有順43二叉樹的存儲（二）06/08/202344二叉樹鏈式存儲結構

存儲方式

一般從根結點開始存儲，用二叉鏈表來表示。（相應地，訪問樹中結點時也只能從根開始）

二叉樹結點的特點二叉樹是非線性結構，適合用鏈式存儲結構lchilddatarchild結點結構datarchildlchilddata

parentlchildrchild二叉樹結點數據類型定義：typedefstructBiTNode{

TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;二叉樹的存儲（二）29/07/202344二叉樹鏈式存儲結構44二叉樹遍歷06/08/202345若規定先左后右，則只有前三種情況：DLR——

前（根）序遍歷，LDR——

中（根）序遍歷，LRD——

后（根）序遍歷根據遍歷順序確定一棵二叉樹已知二叉樹的前序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的后序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的前序序列和后序序列，不能唯一確定一棵二叉樹。二叉樹遍歷29/07/202345若規定先左后右，則只有前三45例題解析06/08/202346

設二叉樹bt的一種存儲結構如下：00237580101jhfdbacegi000940000012345678910lchilddatarchild

其中bt為樹根結點指針,lchild、rchild分別為結點的左、右孩子指針域,在這里使用結點編號作為指針域值,0表示指針域為空;data為結點的數據域。請完成下列各題：(1)畫出二叉樹的樹形表示；(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結點序列；例題解析29/07/202346 設二叉樹bt的一種存儲結構46例題解析（續）06/08/20234700237580101jhfdbacegi000940000012345678910lchilddatarchild(1)畫出二叉樹的樹形表示；因為第6號結點不是任何結點的孩子結點，該結點必定是根結點，再根據和結點左、右指針域的值很容易得到該二叉樹的樹形表示為

abgfdcehij例題解析（續）29/07/2023470023758010147例題解析（續）06/08/20234800237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結點序列；a.先序序列abcedfhgij例題解析（續）29/07/2023480023758010148例題解析（續）06/08/20234900237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結點序列；a.先序序列abcedfhgijb.中序序列ecbhfdjiga例題解析（續）29/07/2023490023758010149例題解析（續）06/08/20235000237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結點序列；a.先序序列abcedfhgijb.中序序列ecbhfdjigab.后序序列echfjigdba例題解析（續）29/07/2023500023758010150樹與森林【例題】從概念上講，樹，森林和二叉樹是三種不同的數據結構，將樹，森林轉化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區別。答：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹惟一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區別有3：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分支的情況下，也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個別書上允許為空）。06/08/202351樹與森林【例題】從概念上講，樹，森林和二叉樹是三種不同的數據51例題解析【例題】已知一棵二叉樹的中序序列和后序序列分別為GLDHBEIACJFK和LGHDIEBJKFCA（1）給出這棵二叉樹；（2）轉換為對應的森林。答：06/08/202352ACBHJDFGKLEIEABLDGHIJFCK例題解析【例題】已知一棵二叉樹的中序序列和后序序列分別為GL52例題解析【例題】假設一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為ABECFGDHI,中序序列為BCDAFEHIG。請畫出該二叉樹，并將其轉換為對應的森林。答：按層次遍歷，第一個結點（若樹不空）為根，該結點在中序序列中把序列分成左右兩部分：左子樹和右子樹。若左子樹不空，層次序列中第二個結點為左子樹的根；若右子樹為空，則層次序列中第三個結點為右子樹的根。對右子樹也作類似的分析。層次序列的特點是，從左到右每個結點或是當前情況下子樹的根或是葉子。06/08/202353IADEBFCGHECABDIGHF例題解析【例題】假設一棵二叉樹的層次次序（按層次遞增順序排列53二叉樹的應用：Huffman樹06/08/202354Huffman樹的應用帶權路徑計算WPL帶權路徑長度WPL最小的二叉樹稱作赫夫曼樹具有相同帶權結點的哈夫曼樹不惟一滿二叉樹不一定是哈夫曼樹哈夫曼樹的結點的度數為0或2，沒有度為1的結點。包含n個葉子結點的哈夫曼樹中共有2n–1個結點。二叉樹的應用：Huffman樹29/07/202354Huf54Huffman樹的構造過程給定權值集w={2,3,4,7,8,9},試構造關于w的的一顆哈夫曼樹，并求其帶權路徑長度WPL。06/08/2023552347894789235789235499235497815Huffman樹的構造過程給定權值集w={2,3,4,7,855Huffman樹的構造過程06/08/202356給定權值集w={2,3,4,7,8,9},試構造關于w的的一顆哈夫曼樹，并求其帶權路徑長度WPL。78159235491878159235491833WPL=(2+3)×4+4×3+9×2+(7+8)×2=80Huffman樹的構造過程29/07/202356給定權值集56【例題】T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權字符集，試構造關于該字符集的一顆哈夫曼樹，求其加權路