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

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

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

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

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

5、。（1）算法也回壁圜是指執(zhí)行算法所需要的計算工作量,可以用執(zhí)行算法的過程中所需基木運算的執(zhí)行次數(shù)來度量。影響計算機工作量的主要因素：第一：基本運算次數(shù)；第二：問題規(guī)模。下面的方法不能用來度量算法的時間復雜度：第一：算法程序的長度或算法程序中的語句（指令）條數(shù)；第二：算法程序所執(zhí)行的語句條數(shù)；第三：算法程序執(zhí)行的具體時間（2）算涓空間復雜度|是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所用的內(nèi)存空間包括：1）算法程序所占用的存儲空間；2）輸入的初始數(shù)據(jù)所占的存儲空間；3）算法執(zhí)行過程中的額外空間。6、考題練習：1）下列敘述正確的是（）（A）算法就是程序（B）算法強調(diào)的是利用技巧提高程序執(zhí)行效率（C

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

7、要的存儲空間1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1、基本概念：1）數(shù)據(jù)：在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。2）數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。3）數(shù)據(jù)結(jié)構(gòu)：是指相互有關聯(lián)的數(shù)據(jù)元素的集合。線性表棧線性結(jié)構(gòu)線性結(jié)構(gòu)I隊列，數(shù)據(jù)的邏輯結(jié)構(gòu)Jr樹形結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)Yr順序存儲數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改!、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關系，從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關，是獨立于計算機的。I3、存儲（物理）結(jié)構(gòu)：是指數(shù)據(jù)元素及其關系在計算機內(nèi)存中的表示，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的

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

9、法：二元關系表和圖形表示。例：一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成：用圖形表示為：宓為數(shù)據(jù)簡稱為結(jié)點。力框來表1）數(shù)據(jù)元素：用M病有元疆M框來粉為數(shù)據(jù)童燈簡稱為結(jié)點。2）元素之間的前后關系：用一條有向線段從前件結(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ù)元素之間的前后關系的復雜度，一般將數(shù)據(jù)結(jié)構(gòu)分成兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。注意：線性結(jié)構(gòu)與非線性結(jié)構(gòu)是在數(shù)據(jù)的邏輯結(jié)構(gòu)概念下的一種劃分方法，與數(shù)據(jù)的存儲結(jié)構(gòu)無關

10、。前面說過，一種數(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é)點后還應是線性結(jié)構(gòu)。1.3線性表及其順序存儲結(jié)構(gòu)1、線性表就是線性結(jié)構(gòu)。線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表是由n（nNO

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

12、的插入運算：在一般情況下，要在第i（IWiWn）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共nT+l個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。7、順序表的刪除運算：在一般情況下，要刪除第i（iWiWn）個元素時"，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。*：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-l）/2個元素。插入、刪除運算不方便。例題：選擇正確表示線性表

13、（A1,A2,A3,A4）的順序結(jié)構(gòu)是（）綜上所述：線性表的順序存儲結(jié)構(gòu)對于經(jīng)常需要變動的大線性表就不合適了，因為插入和刪除的效率比較低。線性表的順序存儲的缺點A1A4A2A3AlA2A3A4A1A2A3A4第一、在插入和刪除時需要移動元素（除棧和隊列之外）第二、上溢（或下溢）L4棧1、棧的定義：展示一種特殊的線性表，即限定在一端進行插入與刪除的線性表。2、棧頂、棧底的定義：在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。3、棧的操作原則：是按照“先進后出”或“后進先出"的原則組織數(shù)據(jù)的。4、棧的基本

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

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

16、列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。7、確定循環(huán)隊列中元素個數(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）退隊運算：是在先能換隊列的排頭位置退出一個元素并賦給指定的變量，也就是front+lo1.6線性鏈表對于大的線性

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

18、的鏈式存儲結(jié)構(gòu)；帶鏈的棧是棧的鏈式存儲結(jié)構(gòu)；帶鏈的隊列是隊列的鏈式存儲結(jié)構(gòu)。4、線性鏈表的存儲結(jié)點的定義：為了適應線性鏈表的鏈式存儲結(jié)構(gòu)，計算機存儲空間被劃分為一個一個小塊，每個小塊占若干個字節(jié)，通常稱這些小塊為存儲結(jié)點。存儲結(jié)點二數(shù)據(jù)域+指針域頭指針：在線性鏈表中，頭指針（head）很關鍵，不的丟失。最后一個結(jié)點的指針域：線性鏈表的最后一個結(jié)點的指針域為空（用NULL或0來表示）5、在鏈式存儲方式中，每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值,稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件），如下圖所示：線性鏈表分為單鏈表、雙向鏈表和循環(huán)

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

20、含指定元素的結(jié)點。*：在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關結(jié)點指針即可。（3）將兩個線性鏈表按要求合并成一個線性鏈表。（4）將一個線性鏈表按要求進行分解。（5）逆轉(zhuǎn)線性鏈表。（6）復制線性鏈表。（7）線性鏈表的排序。（8）線性鏈表的查找。批注fwx21：在鏈表中，即使知道被訪問結(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ù)需要來設置，指針域指向線性表的第一個元素的結(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ā)訪問到表中其他所有的結(jié)點，而

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

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

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

25、可得出：度為1的結(jié)點的個數(shù)為0或1。下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：完全二叉樹還具有如下兩個特性：性質(zhì)5具有n個結(jié)點的完全二叉樹深度為flog2/t4-L性質(zhì)6設完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1,2,，n給結(jié)點進行編號，則對于編號為k（k=l,2,，n）的結(jié)點有以下結(jié)論： 若kF,則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>l,則該結(jié)點的父結(jié)點的編號為INT（k/2）o若2kWn,則編號為k的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。 若2k+lWn,則編號為k的右子結(jié)點編號為2k+l；否則該結(jié)點無右子結(jié)點。4、二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈式存儲結(jié)構(gòu)。批注wx3:這樣，不僅節(jié)省了存儲空間，又能方便地確定每一個結(jié)點的父結(jié)點與左右子結(jié)點的位置，但順序存儲結(jié)構(gòu)對于一般的二叉樹不適用。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩