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

1、第一章 數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法1、算法是指解題方案的準確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。I=1 ，變量I賦值為1S=0 ，變量S賦值為0DO WHILE I<=100 ，循環(huán)結(jié)構(gòu)，當(dāng)I小于100時循環(huán)S=S+I ，對I的值累加求和I=I+1 ，變量I的值沒循環(huán)一次增加1LOOP ，循環(huán)結(jié)構(gòu)，遇到loop返回DO處重新循環(huán) MSGBOX S ，輸出求和變量S的值算法規(guī)定了解決某類問題所需的操作語句以及執(zhí)行順序，使其能通過有限的指令語句，在一定時間內(nèi)解決問題。算法是一個操作序列、有限長度，目的是解決某類問題。*：算法不等于程序，也不等于計算方法。程序的編制不可

2、能優(yōu)于算法的設(shè)計。2、算法的基本特征（1）可行性。針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。（3）有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內(nèi)完成。（4）擁有足夠的情報。指的是有足夠的輸入和輸出。*：綜上所述，所謂算法，是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。3、算法的基本要素一個算法通常由兩種基本要素組成：一是對數(shù)據(jù)對象的運算和操作；二是算法

3、的控制結(jié)構(gòu)。(1）算法中對數(shù)據(jù)的運算和操作每個算法實際上市按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組成的一組指令序列。因此，計算機算法就是計算機能處理的操作所組成的指令序列。在一般的計算機系統(tǒng)中，基本的運算和操作有以下四類：算術(shù)運算：主要包括加、減、乘、除等運算；邏輯運算：主要包括與(AND)、或(OR)、非(NOT)等運算；關(guān)系運算：主要包括大于、小于、等于、不等于等運算數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。(2)算法的控制結(jié)構(gòu)順序、選擇和循環(huán)。4、算法的基本方法（計算機解題的過程實際上是在實施某種算法）（1）列舉法（列舉所有解決方案） 根據(jù)提出的問題，列舉所有可能的情況，并用

4、問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的。?）歸納法（特殊->一般）適合于列舉量為無限的情況 通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。（3）遞推法 （已知->未知） 從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。（4）遞歸法（逐層分解） 將一個復(fù)雜的問題歸結(jié)為若干個較簡單的問題，然后將這些較簡單的每一個問題再歸結(jié)為更簡單的問題（5）減半遞推法 “減半”是指將問題的規(guī)模減半，而問題的性質(zhì)不變，所謂“遞推”是指重復(fù)“減半”的過程。（6）回溯法 復(fù)雜應(yīng)用，找出解決問題的線索，然后沿著這個線索逐步多次“探”、“試”。5、算法復(fù)雜度主要包括時間復(fù)雜度和空

5、間復(fù)雜度。 算法的復(fù)雜度是衡量算法好壞的量度。（1）算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所需基本運算的執(zhí)行次數(shù)來度量。影響計算機工作量的主要因素：第一：基本運算次數(shù)； 第二：問題規(guī)模。下面的方法不能用來度量算法的時間復(fù)雜度：第一：算法程序的長度或算法程序中的語句（指令）條數(shù)；第二：算法程序所執(zhí)行的語句條數(shù)；第三：算法程序執(zhí)行的具體時間（2）算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。 一個算法所用的內(nèi)存空間包括： 1）算法程序所占用的存儲空間；2）輸入的初始數(shù)據(jù)所占的存儲空間；3）算法執(zhí)行過程中的額外空間。6、考題練習(xí)：1）下列敘述正確的是（） （A）算法就

6、是程序（B）算法強調(diào)的是利用技巧提高程序執(zhí)行效率（C）設(shè)計算法時只需考慮結(jié)果的可靠性（D）以上三種說法都不對2）下面敘述正確的是（） （A）算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)（B）算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)（C）算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止（D）以上三種描述都不對3）下列敘述中正確的是（） （A）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大（B）一個算法空間復(fù)雜度大，則其時間復(fù)雜度必定?。–）一個算法的時間復(fù)雜度大，則其時間復(fù)雜度必定?。―）以上三種說法都不對4）算法的空間復(fù)雜度是指（ ）（A）算法程序中變量的個數(shù)（B）算法程序中的指令條數(shù)（C）

7、算法程序中各控制變量所占的額外空間（D）算法執(zhí)行過程中所需要的存儲空間1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念1、基本概念：1）數(shù)據(jù)：在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。2）數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。3）數(shù)據(jù)結(jié)構(gòu)：是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 線性表 棧 線性結(jié)構(gòu) 隊列 數(shù)據(jù)的邏輯結(jié)構(gòu) 樹形結(jié)構(gòu) 非線性結(jié)構(gòu) 圖形結(jié)構(gòu) 順序存儲 數(shù)據(jù)的存儲結(jié)構(gòu) 鏈式存儲 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改2、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系，從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。3、存儲（物理）結(jié)構(gòu)：是指數(shù)據(jù)元素及

8、其關(guān)系在計算機內(nèi)存中的表示，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。注意：對于同一個邏輯結(jié)構(gòu)來說，采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在數(shù)據(jù)處理時，選擇合適的存儲結(jié)構(gòu)很重要。各數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系與它們的邏輯關(guān)系不一定相同。由于數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計算機存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后間關(guān)系）在數(shù)據(jù)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的本身，而且還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。4、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系：（1）一種邏輯結(jié)構(gòu)可以用不同的物理結(jié)構(gòu)來實現(xiàn)（2）邏輯結(jié)構(gòu)決定了算法的設(shè)計（3）

9、物理結(jié)構(gòu)決定了算法的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的圖形表示：表示數(shù)據(jù)結(jié)構(gòu)的常用方法：二元關(guān)系表和圖形表示。例：一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成：用圖形表示為：春夏秋冬1） 數(shù)據(jù)元素：用中間標有元素值的方框來表示，稱為數(shù)據(jù)結(jié)點，簡稱為結(jié)點。2） 元素之間的前后關(guān)系：用一條有向線段從前件結(jié)點指向后件結(jié)點（有時可以省略箭頭）例如：家庭成員數(shù)據(jù)結(jié)構(gòu)可以表示稱為：父親女兒兒子在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點，沒有后件的結(jié)點稱為終端結(jié)點（也稱為葉子結(jié)點）其它的稱為內(nèi)部結(jié)點。5、線性結(jié)構(gòu)與非線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的分類：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后關(guān)系的復(fù)雜度，一般將數(shù)據(jù)結(jié)構(gòu)分成兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。注意：線性結(jié)

10、構(gòu)與非線性結(jié)構(gòu)是在數(shù)據(jù)的邏輯結(jié)構(gòu)概念下的一種劃分方法，與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)。前面說過，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，但只要數(shù)據(jù)的邏輯結(jié)構(gòu)是屬于線性結(jié)構(gòu)，則該邏輯結(jié)構(gòu)的任意一種存儲結(jié)構(gòu)也都屬于線性結(jié)構(gòu)。6、線性結(jié)構(gòu)的定義：如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：（1） 有且只有一個根結(jié)點（每有前件的結(jié)點稱為根結(jié)點）（2） 每個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，線性結(jié)構(gòu)又稱為線性表。（3） 線性結(jié)構(gòu)的操作。 在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。1.3 線性表及其順序存儲結(jié)構(gòu)1、線性表就是線性結(jié)構(gòu)。線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元

11、素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表是由n(n0)個數(shù)據(jù)元素組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件2、線性表的順序存儲結(jié)構(gòu)也稱為順序表。3、線性表的順序存儲結(jié)構(gòu)具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的，其前后兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。4、線性表的長度：是指線性表中數(shù)據(jù)元素的個數(shù)，當(dāng)N=0時，稱為空表。5、通常定義一個一維數(shù)組來表示線性表的順序存儲空間，用一維數(shù)組來存放線性表時，該一

12、維數(shù)組的長度不要定義為太短，也不要定義為太長。6、順序表（線性表的順序結(jié)構(gòu)）的插入運算：在一般情況下，要在第i（1in）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。7、順序表的刪除運算：在一般情況下，要刪除第i（1in）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。*：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）

13、/2個元素。插入、刪除運算不方便。例題：選擇正確表示線性表(A1,A2,A3,A4)的順序結(jié)構(gòu)是（ ）A1A4A2A3A1A2A3A4A1A2A3A4綜上所述：線性表的順序存儲結(jié)構(gòu)對于經(jīng)常需要變動的大線性表就不合適了，因為插入和刪除的效率比較低。線性表的順序存儲的缺點第一、在插入和刪除時需要移動元素（除棧和隊列之外）第二、上溢（或下溢） 1.4 棧1、棧的定義：展示一種特殊的線性表，即限定在一端進行插入與刪除的線性表。2、棧頂、棧底的定義：在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。3、棧的操作原則：是按照

14、“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。4、棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。5、棧具有記憶功能。6、注意：1）在順序存儲結(jié)構(gòu)下，棧的插入與刪除運算都不需要移動表中其他數(shù)據(jù)元素；2）在棧中，棧頂指針動態(tài)反映了棧中元素的變化情況。7、在順序結(jié)構(gòu)下的讀棧頂元素是指將棧頂元素賦值給一個指定的變量。（讀不是刪除，刪除一定要先讀。在只讀的情況下，原來是多少，讀后還是多少）8、讀棧頂元素過程中應(yīng)注意的問題：1）讀棧頂元素不刪除棧頂元素，只是將它的值賦給一個變量。因此在這個運算中棧頂指針不會改變；2）當(dāng)棧頂指針

15、為0時，說明棧為空，讀不到棧頂元素。1.5隊列及其運算1、隊列的定義：隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。2、允許插入的一端叫隊尾。尾指針（Rear）指向隊尾元素。允許刪除的一端叫對頭。頭指針（front）指向排頭元素的前一個位置（隊頭）。3、數(shù)據(jù)操作方法：隊列是“先進先出”或“后進后出”的線性表。4、隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。5、在順序存儲結(jié)構(gòu)下，隊列的插入與刪除運算都不需要移動表中其他數(shù)據(jù)元素。6、循環(huán)隊列及其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，

16、供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。7、確定循環(huán)隊列中元素個數(shù)的方法如下：設(shè)循環(huán)隊列的容量為M，如果rear>front，則循環(huán)隊列中的元素個數(shù)為rear-front；如果rear<front，則循環(huán)隊列中的元素個數(shù)為M+(rear-front)；8、循環(huán)隊列的運算有兩個：1）入隊運算：是在循環(huán)隊列的隊尾加入一個新元素，也就是rear+1；2）退隊運算：是在先能換隊列的排頭位置退出一個元素并賦給指定的

17、變量，也就是front+1。1.6 線性鏈表對于大的線性表或者變動頻繁的線性表不宜用順序存儲，應(yīng)該用鏈式存儲。1、鏈式存儲方式的特點：（1）在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以是不連續(xù)的。（2）各結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致。2、線性鏈表：線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實現(xiàn)的。3、線性表順序存儲的缺點：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素；（2）線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴充；（3）線性表的順序存

18、儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。注意：線性鏈表是線性表的鏈式存儲結(jié)構(gòu)；帶鏈的棧是棧的鏈式存儲結(jié)構(gòu)；帶鏈的隊列是隊列的鏈式存儲結(jié)構(gòu)。4、線性鏈表的存儲結(jié)點的定義：為了適應(yīng)線性鏈表的鏈式存儲結(jié)構(gòu)，計算機存儲空間被劃分為一個一個小塊，每個小塊占若干個字節(jié)，通常稱這些小塊為存儲結(jié)點。存儲結(jié)點=數(shù)據(jù)域+指針域頭指針：在線性鏈表中，頭指針（head）很關(guān)鍵，不的丟失。最后一個結(jié)點的指針域：線性鏈表的最后一個結(jié)點的指針域為空（用NULL或0來表示）5、在鏈式存儲方式中，每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點的前一個或后一個結(jié)點（即前件

19、或后件），如下圖所示：線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單鏈表中，每一個結(jié)點只有一個指針域，由這個指針只能找到其后件結(jié)點，而不能找到其前件結(jié)點。因此，在某些應(yīng)用中，對于線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針，指向其前件結(jié)點；另一個稱為右指針，指向其后件結(jié)點，這種鏈表稱為雙向鏈表，如下圖所示：3、線性鏈表的基本運算（1）在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素。*：在線性鏈表中插入元素時，不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可，也不會出現(xiàn)“上溢當(dāng)為一個線性表分配順序存儲結(jié)構(gòu)后，如果出現(xiàn)線性表的存儲空間已滿，但還需要插入新的元素時，就會發(fā)生“上溢”現(xiàn)象。”

20、現(xiàn)象。（2）在線性鏈表中刪除包含指定元素的結(jié)點。*：在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可。（3）將兩個線性鏈表按要求合并成一個線性鏈表。（4）將一個線性鏈表按要求進行分解。（5）逆轉(zhuǎn)線性鏈表。（6）復(fù)制線性鏈表。（7）線性鏈表的排序。（8）線性鏈表的查找。*：線性鏈表不能隨機存取在鏈表中，即使知道被訪問結(jié)點的序號i，也不能像順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止。因此，鏈表不是隨機存儲結(jié)構(gòu)。4、循環(huán)鏈表及其基本運算在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程

21、中對于空表和對第一個結(jié)點的處理必須單獨考慮，使空表與非空表的運算不統(tǒng)一。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環(huán)鏈表。與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點，而循環(huán)鏈表的頭指針指向表頭結(jié)點；2）循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。下圖a是一個非空的循環(huán)鏈表，圖b是一個空的循環(huán)鏈表：循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有

22、的結(jié)點，而線性單鏈表做不到這一點；二是由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。*：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點，其插入和刪除運算與單鏈表相同。但它可以從任一結(jié)點出發(fā)來訪問表中其他所有結(jié)點，并實現(xiàn)空表與非空表的運算的統(tǒng)一。1.6 樹與二叉樹1、樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點

23、。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。結(jié)點的定義：數(shù)據(jù)元素+若干指向子樹的分支。結(jié)點的度得定義：子樹的個數(shù)，即擁有的后件個數(shù)稱為該結(jié)點的度。樹的度得定義：樹中所有結(jié)點的度的最大值。葉子結(jié)點的定義：度為零的結(jié)點，即沒有后件的結(jié)點。分支結(jié)點的定義：度大于非零的結(jié)點。結(jié)點的層次（深度）的定義：假設(shè)根結(jié)點的層次為1，第I層得結(jié)點的子樹根結(jié)點的層次為I+1。樹的深度的定義：樹中葉子結(jié)點所在的最大層次。2、二叉樹及其基本性質(zhì)（1）什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個特點：1）非空二叉樹只有一個根結(jié)點；2）每一個

24、結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。*：根據(jù)二叉樹的概念可知，二叉樹的度可以為零（葉結(jié)點）、1（只有一棵子樹）或2（有2棵子樹）。（2）二叉樹的基本性質(zhì)性質(zhì)1 在二叉樹的第k層上，最多有 個結(jié)點。性質(zhì)2 深度為m的二叉樹最多有個 個結(jié)點。性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點（即葉子結(jié)點）總比度為2的結(jié)點多一個。性質(zhì)4 具有n個結(jié)點的二叉樹，其深度至少為 ，其中 表示取 的整數(shù)部分。3、滿二叉樹與完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。*：根據(jù)完全二叉樹的

25、定義可得出：度為1的結(jié)點的個數(shù)為0或1。下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：完全二叉樹還具有如下兩個特性：性質(zhì)5 具有n個結(jié)點的完全二叉樹深度為 。性質(zhì)6 設(shè)完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，n給結(jié)點進行編號，則對于編號為k（k=1，2，n）的結(jié)點有以下結(jié)論：若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點的編號為INT(k/2)。若2kn，則編號為k的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。若2k+1n，則編號為k的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。4、二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈式存儲結(jié)構(gòu)。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩部分組成：數(shù)據(jù)域和指針域。但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結(jié)點），因此，用于存儲二叉樹的存儲結(jié)點的