數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)必背

1、第一章：緒論1.1：數(shù)據(jù)結(jié)構(gòu)課程的任務(wù)是：討論數(shù)據(jù)的各種邏輯結(jié)構(gòu)、在計算機(jī)中的存儲結(jié)構(gòu)以及各種操作的算法設(shè)計。1.2 ：數(shù)據(jù)：是客觀描述事物的數(shù)字、字符以及所有的能輸入到計算機(jī)中并能被計算機(jī)接收的各種集合的統(tǒng)稱。數(shù)據(jù)元素：表示一個事物的一組數(shù)據(jù)稱作是一個數(shù)據(jù)元素，是數(shù)據(jù)的基本單位。 數(shù)據(jù)項：是數(shù)據(jù)元素中有獨(dú)立含義的、不可分割的最小標(biāo)識單位。數(shù)據(jù)結(jié)構(gòu)概念包含三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)的數(shù)據(jù)的操作。1.3 數(shù)據(jù)的 邏輯結(jié)構(gòu) 指數(shù)據(jù)元素之間的邏輯關(guān)系，用一個數(shù)據(jù)元素的集合定義在此集合的若干關(guān)系來表示，數(shù)據(jù)結(jié)構(gòu)可以分為三種： 線性結(jié)構(gòu) 、樹結(jié)構(gòu)和圖。上1.4：數(shù)據(jù)元素及其關(guān)系在計算機(jī)中的

2、存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)基本形式有兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。2.1 ：算法：一個算法是一個有窮規(guī)則的集合，其規(guī)則確定一個解決某一特定類型問題的操作序列。算法規(guī)則需滿足以下五個特性：輸入算法有零個或多個輸入數(shù)據(jù)。輸出算法有一個或多個輸出數(shù)據(jù)，與輸入數(shù)據(jù)有某種特定關(guān)系。有窮性算法必須在執(zhí)行又窮步之后結(jié)束。確定性算法的每個步驟必須含義明確，無二義性?？尚行?算法的每步操作必須是基本的，它們的原則上都能夠精確地進(jìn)行，用筆和 紙做有窮次就可以完成。有窮性和可行性是算法最重要的兩個特征。2.2：算法與數(shù)據(jù)結(jié)構(gòu)：算法建立數(shù)據(jù)結(jié)構(gòu)之上，對數(shù)據(jù)結(jié)構(gòu)的操作需用算法來描述。

3、算法設(shè)計依賴數(shù)據(jù)的邏輯結(jié)構(gòu)，算法實(shí)現(xiàn)依賴數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)。2.3：算法的設(shè)計應(yīng)滿足五個目標(biāo)：正確性：算法應(yīng)確切的滿足應(yīng)用問題的需求，這是算法設(shè)計的基本目標(biāo)。健壯性：即使輸入數(shù)據(jù)不合適，算法也能做出適當(dāng)?shù)奶幚?，不會?dǎo)致不可控結(jié)高時間效率：算法的執(zhí)行時間越短，時間效率越高。果。高空間效率：算法執(zhí)行時占用的存儲空間越少，空間效率越高。可讀性：算法的可讀性有利于人們對算法的理解。2.4 : 度量算法的時間效率，時間復(fù)雜度， ( 課本 39 頁) 。2.5: 遞歸定義：即用一個概念本身直接或間接地定義它自己。遞歸定義有兩個條件：至少有一條初始定義是非遞歸的，如1！ =1.由已知函數(shù)值逐步遞推計算出未知

4、函數(shù)值，如用(n-1 )! 定義 n! 。第二章：線性表1.1 線性表：線性表是由n(n>=0) 個類型相同的數(shù)據(jù)元素a0,a1,a2,an 組成的有限序列，記作：Li nearList = (a0,a1,a2,-1)a n其中，元素ai 可以是整數(shù)、浮點(diǎn)數(shù)、字符、也可以是對象。n 是線性表的元素個數(shù)，成為線性表長度。若n=0 ，則 LinearList 為空表。若n>0 ，則 a0 沒有前驅(qū)元素，an-1 沒有后繼元素， ai ( 0<i<n-1 ) 有且僅有一個直接前驅(qū)元素ai-1 和一個直接后繼元素ai+1 。1.2 線性表的順序存儲是用一組連續(xù)的內(nèi)存單元依次存放

5、線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存儲次序與它們在線性表中的邏輯次序相同。線性表的數(shù)據(jù)元素數(shù)據(jù)同一種數(shù)據(jù)類型，設(shè)每個元素占用c 字節(jié)， a0 的存儲地址為Loc ( a0 ) ，貝 V ai 的存儲地址Loc ( ai) 為： Loc ( ai)= Loc ( a0)+ i*c數(shù)組是順序存儲的隨機(jī)存儲結(jié)構(gòu)，它占用一組連續(xù)的存儲單元，通過下標(biāo)識別元素，元素地址是下標(biāo)的線性函數(shù)。1.3 : 順序表的插入和刪除操作要移動數(shù)據(jù)元素。平均移動次數(shù)是屬數(shù)據(jù)表長度的一半。( 課本第50 頁)1.4 : 線性表的鏈?zhǔn)酱鎯κ怯萌舾傻刂贩稚⒌拇鎯卧鎯?shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，必須采

6、用附加信息表示數(shù)據(jù)元素之間的順序關(guān)系。它有兩個域組成：數(shù)據(jù)域和地址域。通常成為節(jié)點(diǎn)。( 課本第55 頁及 56 頁)1.5 單鏈表 ( 課本 56 頁)歡迎下載2單鏈表的遍歷： Node<E> p = head; while(p!=null)訪問p 節(jié)點(diǎn)； p = p.next;歡迎下載3單鏈表的插入和刪除操作非常簡便，只要改變節(jié)點(diǎn)間的鏈接關(guān)系，不需移動數(shù)據(jù)元素。單鏈表的插入操作：1): 空表插入 /頭插入2)中間插入 /尾插入if(head = n ull)Node<E> q = new Node<E>(x); head = new Node<E&g

7、t;(x);q.n ext = p.n ext;elsep.n ext = q;Node<E> q=new Node<E>(x);中間插入或尾插入都不會改變單表q.n ext = head;的頭指針headhead = q;單鏈表的刪除操作:頭刪除：head = head .n ext;中間/尾刪除： if(p.next!=null) p.next = p.next.next;循環(huán)單鏈表：如果單鏈表最后一個節(jié)點(diǎn)的next 鏈保存單鏈表的頭指針head 值，則該單鏈表成為環(huán)形結(jié)構(gòu)，稱為循環(huán)單鏈表。( 課本67)若 rear 是單鏈表的尾指針，則執(zhí)行( rear.next=

8、head;) 語句，使單鏈表成為一條循環(huán)單鏈表。當(dāng) head.next=head時，循環(huán)單鏈表為空。1.6 : 雙鏈表結(jié)構(gòu)：雙鏈表的每個結(jié)點(diǎn)有兩個鏈域，分別指向它的前驅(qū)和后繼結(jié)點(diǎn)，當(dāng) head.next=null時，雙鏈表為空設(shè) p 指向雙鏈表中非兩端的某個結(jié)點(diǎn)，則成立下列關(guān)系:p=p .n ext.prev=p.prev .next雙鏈表的插入和刪除：1) 插入2) 刪除q=new DLinkNode( x) ；p.prev .n ext = p.next;q.prev=p.prev; q.n ext =p;if(p.n ext=nu ll)p.prev .n ext = q;p.prev=

9、q;循環(huán)雙鏈表：當(dāng)且(p.n prev=headext). 時，循環(huán)雙鏈表為空。head.next=headhead.第三章：棧和隊列1.1 棧：棧是一種特殊的線性表，其中插入和刪除操作只允許在線性表的一端進(jìn)行。允許操作的一端稱為棧頂，不允許操作的一端稱為棧底。棧有順序棧和鏈?zhǔn)綏?。歡迎下載4棧中插入元素的操作稱為入棧，刪除元素的操作稱為出棧。沒有元素的中稱為空棧。棧的進(jìn)出棧順序：后進(jìn)先出，先進(jìn)后出。（及75 頁的思考題）。1.2 : 隊列：隊列是一種特殊的線性表，其中插入和刪除操作分別在線性表的兩端進(jìn)行。向隊列中插入元素的過程稱為入隊，刪除元素的過程稱為出對，允許入隊的一端稱為隊尾，允許出隊的

10、一端稱為對頭。沒有元素的隊列稱為空隊列。隊列是先進(jìn)先出。第四章：串1.1 : 串是一種特殊的線性表，其特殊性在于線性表中的每個元素是一個字符。一個串記為： s=“ s0s1s2 -1” n 其中 n>=O,s 是串名，一對雙引號括起來的字符序列s0s1s2sn 是串值， si（ i=0 ,1 ,2 ,-n-1 ）為特定字符集合中的一個字符。一個串中包含的字符個數(shù)稱為串的長度。長度為 0 的串稱為空串，記作“；而由一個或多個空格字符構(gòu)成的字符串稱為空格串。子串：由串s 中任意連續(xù)字符組成的一個子序列sub 稱為 s 的子串， s 稱為 sub 的主串。子串的序號是指該子串的第一個字符在主串

11、中的序號。串比較：兩個串可比較是否相等，也可比較大小。兩個串（子串）相等的充要條件是兩個串（子串）的長度相同，并且各對應(yīng)位置上的字符也相同。兩個串的大小由對應(yīng)位置的第一個不同字符的大小決定，字符比較次序是從頭開始依次向后。當(dāng)兩個串長度不等而對應(yīng)位置的字符都相同時，較長的串定義為較大”。第五章：數(shù)組和廣義表1.1 : 數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。一維數(shù)組的邏輯結(jié)構(gòu)是線性表，多維數(shù)組是線性表的擴(kuò)展。1.2 : 一維數(shù)組：一維數(shù)組采用順序存儲結(jié)構(gòu)。一個一維數(shù)組占用一組連續(xù)的存儲單丿元。設(shè)數(shù)組第一個元素a0 的存儲地址為Loc ( a0 ) ，每個元素占用c 字節(jié)，則數(shù)組其他元素

12、ai 的存儲地址 Loc ( ai) 為： Loc ( ai ) = Loc ( a0) +i*c數(shù)組通過下標(biāo)識別元素，元素地址是下標(biāo)的線性函數(shù)。一個下標(biāo)能夠唯一確定一個元素，所劃給的時間是0(1) 。因此數(shù)組是隨機(jī)存取結(jié)構(gòu)，這是數(shù)組最大的優(yōu)點(diǎn)。1.3 : 多維數(shù)組的遍歷：有兩種次序：行主序和列主序。歡迎下載5行主序：以行為主序，按行遞增訪問數(shù)組元素，訪問完第i 行的所有元素之后再訪問第i+1 行的元素，同一行上按列遞增訪問數(shù)組元素。aOO,aO1,aO-1), a10,a11,a1(na(i-1)0,a(m- 1)1,a(r-1)(n-1)2) 列主序：以列為主序，按列遞增訪問數(shù)組元素，訪問

13、完第j 列的所有元素之后再訪問第 j+1 列的元素，同一列上按列遞增訪問數(shù)組元素。多維數(shù)組的存儲結(jié)構(gòu)：多維數(shù)組也是由多個一維數(shù)組組合而成，組合方式有一下兩種。靜態(tài)多維數(shù)組的順序存儲結(jié)構(gòu)：可按行主序和列主序進(jìn)行順序存儲。按行主序存儲時，元素aij 的地址為： Loc ( aij ) = Loc ( a00 )+ ( i*n+j )*c按列主序存儲時，Loc ( aij )= Loc ( a00 )+ ( j*m+i )*c動態(tài)多維數(shù)組的存儲結(jié)構(gòu)。二維數(shù)組元素地址就是兩個下標(biāo)的線性函數(shù)。無論采用哪種存儲結(jié)構(gòu)，多維數(shù)組都是基于一維數(shù)組的，因此也只能進(jìn)行賦值、取值兩種存取操作，不能進(jìn)行插入，刪除操作。

14、樹是數(shù)據(jù)元素 ( 結(jié)點(diǎn) ) 之間具有層次關(guān)系的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，除根以外的結(jié)點(diǎn)只有一個直接前驅(qū)結(jié)點(diǎn)，可以有零至多個直接后繼結(jié)點(diǎn)。根沒有前驅(qū)結(jié)點(diǎn)。樹是由 n ( n>=0 ) 個結(jié)點(diǎn)組成的有限集合( 樹 中元素通常稱為結(jié)點(diǎn)) 。 N=0 的樹稱為空樹； n>0大的樹 T; 有一個特殊的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，它只有后繼結(jié)點(diǎn)，沒有前驅(qū)結(jié)點(diǎn)。 除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)分為m ( m>=0 ) 個互不相交的集合T0,T1,T3.,Tm 1 ，其中每個集合 Ti ( 0<=i<m ) 本身又是一棵樹，稱為根的子樹。樹是遞歸定義的。結(jié)點(diǎn)是樹大的基本單位，若干個結(jié)點(diǎn)組成一棵子樹，若

15、干棵互不相交的子樹組成一棵樹。樹的每個結(jié)點(diǎn)都是該樹中某一棵子樹的根。因此，樹是由結(jié)點(diǎn)組成的、結(jié)點(diǎn)之間具有層次關(guān)系大的非線性結(jié)構(gòu)。結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)稱為其父母結(jié)點(diǎn)，反之，結(jié)點(diǎn)大的后繼結(jié)點(diǎn)稱為其孩子結(jié)點(diǎn)。一棵樹中，只有根結(jié)點(diǎn)沒有父母結(jié)點(diǎn)，其他結(jié)點(diǎn)有且僅有一個父母結(jié)點(diǎn)。擁有同一個父母結(jié)點(diǎn)的多個結(jié)點(diǎn)之間稱為兄弟結(jié)點(diǎn)。結(jié)點(diǎn)的祖先是指從根結(jié)點(diǎn)到其父母結(jié)點(diǎn)所經(jīng)過大的所有結(jié)點(diǎn)。結(jié)點(diǎn)的后代是指該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，以及孩子的孩歡迎下載6子等。結(jié)點(diǎn)的度是結(jié)點(diǎn)所擁有子樹的棵數(shù)。度為0 的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，又叫終端結(jié)點(diǎn)；樹中除葉子結(jié)點(diǎn)之外的其他結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，又叫非葉子結(jié)點(diǎn)或非終端結(jié)點(diǎn)。樹的度是指樹中各結(jié)點(diǎn)度的最大值。

16、結(jié)點(diǎn)的層次屬性反應(yīng)結(jié)點(diǎn)處于樹中的層次位置。約定根結(jié)點(diǎn)的層次為1, 其他結(jié)點(diǎn)的層次是其父母結(jié)點(diǎn)的層次加1。顯然，兄弟結(jié)點(diǎn)的層次相同。樹的高度或深度是樹中結(jié)點(diǎn)的最大層次樹。設(shè)樹中 x 結(jié)點(diǎn)是 y 結(jié)點(diǎn)的父母結(jié)點(diǎn)，有序?qū)? x， y) 稱為連接這兩個結(jié)點(diǎn)的分支，也稱為邊。設(shè) ( X0,X1,.-Xk 是由樹中結(jié)點(diǎn)組成的一個序列，且(Xi,Xi+1 ) (0<=ivk-1 ) 都是樹中的邊，則該序列稱為從X0 到 Xk-1 的一條路徑。路徑長度為路徑上的邊數(shù)。在樹的定義中，結(jié)點(diǎn)的子樹T0 ,T1.,Tm1 之間沒有次序，可以交換位置，稱為無序樹，簡稱樹。如果結(jié)點(diǎn)的子樹T0,T1，Tm 從左到右是

17、有次序的，不能交換位置，則稱該樹為有序樹。森林是 m ( m>=0 ) 棵互不相干的樹的集合。給森林加上一個根結(jié)點(diǎn)就變成一棵樹，將樹的根節(jié)點(diǎn)刪除就變成森林。二叉樹的性質(zhì)1: 若根結(jié)點(diǎn)的層次為1, 則二叉樹第i 層最多有2 的 i-1 次方 ( i>=1 )個結(jié)點(diǎn)。二叉樹的性質(zhì)2: 在高度為k 的二叉樹中，最多有2 的 k 次方減一個結(jié)點(diǎn)。二叉樹的性質(zhì)3: 設(shè)一棵二叉樹的葉子結(jié)點(diǎn)數(shù)為n0,2 度結(jié)點(diǎn)數(shù)為n2 , 則 n0=n2+1 。一棵高度為k 的滿二叉樹是具有2 的 k 次方減一個結(jié)點(diǎn)的二叉樹。滿二叉樹中每一層的結(jié)點(diǎn)數(shù)目都達(dá)到最大值。對滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號，約定根節(jié)點(diǎn)的序號

18、為0，從根節(jié)點(diǎn)開始，自上而下，每層自左至右編號。一棵具有n 個結(jié)點(diǎn)高度為k 的二叉樹，如果他的每個節(jié)點(diǎn)都與高度為k 的滿二叉樹中序號為 0? n-1的結(jié)點(diǎn) - - 對應(yīng)，則這棵二叉樹為為完全二叉樹。滿二叉樹是完全二叉樹，而完全二叉樹不一定是滿二叉樹。完全二叉樹的第1? k-1 層是滿二叉樹第k 層不滿，并且該層所有結(jié)點(diǎn)必須集中在該層左邊的若干位置上。歡迎下載7二叉樹的性質(zhì)4:一棵具有 n 個結(jié)點(diǎn)的完全二叉樹，其高度k=log2n 的絕對值 +1二叉樹的性質(zhì)5:棵具有 n 個結(jié)點(diǎn)的完全二叉樹，對序號為i 的結(jié)點(diǎn)，有 若 i=0 ，則 i 為根節(jié)點(diǎn)，無父母結(jié)點(diǎn)；若i>0 ，則 i 的父母結(jié)點(diǎn)

19、的序號為( i-1 ) /2。 若 2i+1<n ，貝 V i 的左孩子結(jié)點(diǎn)序號為2i+1 ；否則 i 無左孩子。 若 2i+2<n ，貝 V i 的右孩子結(jié)點(diǎn)的序號為2i+2 ，否則 i 無右孩子。二叉樹的遍歷二叉樹的遍歷是按照一定規(guī)則和次序訪問二叉樹中的所有結(jié)點(diǎn)，并且每個結(jié)點(diǎn)僅被訪問一次。二叉樹的三種次序遍歷1: 先根次序；訪問根節(jié)點(diǎn)，遍歷左子樹，遍歷右子樹。2 : 中根次序；遍歷左子樹，訪問右子樹，遍歷右子樹。3 : 后根次序；遍歷左子樹，遍歷右子樹，訪問根節(jié)點(diǎn)。先根次序遍歷時，最先訪問根節(jié)點(diǎn)；后根次序遍歷時，最后訪問根節(jié)點(diǎn)；中根次序遍歷時，左子樹上的結(jié)點(diǎn)在根節(jié)點(diǎn)之前訪問，右

20、子樹上的結(jié)點(diǎn)在根節(jié)點(diǎn)之后訪問。二叉樹的插入和刪除操作P147二叉樹的層次遍歷P149習(xí)題P1676 10,619第七章圖是由定點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)關(guān)邊系。頂點(diǎn)之間的關(guān)系成為邊。一個圖G 記為 G= （ V,E ） ,V 是頂點(diǎn) A 的有限集合， E 是邊的有限集合。即V= A|A 屬于某個數(shù)據(jù)元素集合E= （ A,B ） |A,B 表示從頂點(diǎn) A到屬于 V或 E= <A,B>|A,B B 的一條單向通路，即 Path屬于V 且 Path （ A,B ）其中Path （ A,B ）（ A,B ）是有方向的。無向圖中的邊事沒有方向，每條邊用兩個頂點(diǎn)的無序?qū)Ρ硎尽Ｓ邢驁D

21、中的邊是有方向，每條邊用兩個頂點(diǎn)的有序?qū)Ρ硎?。歡迎下載8完全圖指圖的邊數(shù)達(dá)到最大值。n 個頂點(diǎn)的完全圖記為Kn 。無向完全圖Kn 的邊數(shù)為n* （ n-1 ）/2, 有向完全圖Kn 的邊數(shù)為n* （ n-1 ）。子圖：設(shè)圖G= （ V,E ） ,G'=（V,' 若，日 ' 包含于 V 且 E 包含于 E,則稱圖 G 是 G 的子圖。若 G'是 G 的真子圖。連通圖：在無向圖G 中，若從頂點(diǎn)VI 到 Vj 有路徑，則稱Vi 和 Vj 是聯(lián)通的。若圖G 中 任意一對頂點(diǎn)Vi 和 Vj （ Vi 不等于 Vj ）都是聯(lián)通的，則稱G 為連通圖。非連通圖的極大聯(lián)通子圖稱為

22、該圖的聯(lián)通分量。強(qiáng)連通圖：在有向圖中，若在每一對頂點(diǎn)Vi 和 Vj （ Vi 不等于 Vj ）之間都存在一條從Vi到 Vj 的路徑，也存在一條從Vi 到 Vj 的路徑，也存在一條從Vi 到 Vj 的路徑，則稱該圖的強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖稱為該圖的強(qiáng)連通圖分量。圖的遍歷遍歷圖是指從圖G 中任意一個頂點(diǎn)V 出發(fā)，沿著圖中的邊前行，到達(dá)并訪問圖中的所有頂點(diǎn)，且每個頂點(diǎn)僅被訪問一次。遍歷圖要考慮一下三個問題： 指定遍歷的第一個訪問頂點(diǎn) 由于一個頂點(diǎn)可能與多個頂點(diǎn)相鄰，因此要在多個鄰接頂點(diǎn)之間約定一種訪問次序。 由于圖中可能存在回路，在訪問某個頂點(diǎn)之后，可能沿著某條路徑又回到該頂點(diǎn)。深度優(yōu)

23、先搜索圖的深度優(yōu)先搜索策略是，訪問某個頂點(diǎn)v，接著尋找v 的另一個未被訪問的鄰接頂點(diǎn)w 訪問，如此反復(fù)執(zhí)行，走過一條較長路徑到達(dá)最遠(yuǎn)頂點(diǎn)；若頂點(diǎn)v 沒有未被訪問的其他鄰接頂點(diǎn)，則回到前一個被訪問頂點(diǎn)，再尋找其他訪問路徑。圖的深度優(yōu)先搜索遍歷算法P188聯(lián)通的無回路的無向圖，簡稱樹。樹中的懸掛點(diǎn)又成為樹葉，其他頂點(diǎn)稱為分支點(diǎn)。各連通分量均為樹的圖稱為森林，樹是森林。由于樹中無回路，因此樹中必定無自身環(huán)也無重邊（否則他有回路）若去掉樹中的任意一條邊，則變成森林，成為非聯(lián)通圖；若給樹加上一條邊，形成圖中的一條回路， 則不是樹。 P191生成樹和生成森林：歡迎下載9一個連通無向圖的生成樹是該圖的一個極小聯(lián)通生成子圖，它包含原圖中所有頂點(diǎn)（n 個）以及足以構(gòu)成一棵樹的n-1 條邊。一個非聯(lián)通的無向圖，其各連通圖分量的生成圖組成該圖的生成森林。圖的生成圖或生成森林不是唯一的，從不同頂點(diǎn)開始、采用不同遍歷可以得到不同的生成樹或森林。在生成樹中，任何樹中，任何兩個頂點(diǎn)之間只有唯一的一條路徑。第八章折半查找算法描述P206,P207二叉排序樹及其查找：二叉排序樹或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： 每個結(jié)點(diǎn)都有一個作為查找依據(jù)的關(guān)鍵字，所有結(jié)點(diǎn)的關(guān)鍵字互不相同。 若一個結(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于這個節(jié)點(diǎn)的關(guān)鍵字； 每個結(jié)點(diǎn)的左右子樹也分別為二叉排序樹。在一棵二叉