自考02331數(shù)據(jù)結構重點總結

1、自考02331數(shù)據(jù)結構重點總結第一章概論.瑞士計算機科學家沃思提出：算法徽據(jù)名構=程序。算法是對數(shù)據(jù)運算的描述，而數(shù) 據(jù)結構包括邏輯結構和存儲結構。 由此可見，程序設計的實質是針對實際問題選擇一種 好的數(shù)據(jù)結構和設計一個好的算法，而好的算法在很大程度上取決于描述實際問題的數(shù) 據(jù)結構。.數(shù)據(jù)是信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項 組成，數(shù)據(jù)項是具有獨立含義的最小標識單位。 數(shù)據(jù)對象是具有相同性質的數(shù)據(jù)元素的 集合。.數(shù)據(jù)結構指的是數(shù)據(jù)元素之間的相互關系，即數(shù)據(jù)的組織形式。數(shù)據(jù)結構一般包括以下三方面內容：數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構、數(shù)據(jù)的運算數(shù)據(jù)的邏輯結構是從邏

2、輯關系上描述數(shù)據(jù)， 與數(shù)據(jù)元素的存儲結構無關，是獨立于計 算機的。數(shù)據(jù)的邏輯結構分類：線性結構和非線性結構。線性表是一個典型的線性結構。棧、隊列、串等都是線性結構。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結構都是非線性結構。數(shù)據(jù)元素及其關系在計算機內的存儲方式，稱為數(shù)據(jù)的存儲結構(物理結構)。數(shù)據(jù)的存儲結構是邏輯結構用計算機語言的實現(xiàn)，它依賴于計算機語言。數(shù)據(jù)的運算。最常用的檢索、插入、刪除、更新、排序等。.數(shù)據(jù)的四種基本存儲方法：順序存儲、鏈接存儲、索引存儲、散列存儲(1)順序存儲：通常借助程序設計語言的數(shù)組描述。(2)鏈接存儲：通常借助于程序語言的指針來描述。(3)索引存儲：索引表由若干索引項組成。關鍵

3、字是能唯一標識一個元素的一個或多 個數(shù)據(jù)項的組合。(4)散列存儲：該方法的基本思想是：根據(jù)元素的關鍵字直接計算出該元素的存儲地址。.算法必須滿足5個準則：輸入，0個或多個數(shù)據(jù)作為輸入；輸出，產生一個或多個輸 出；有窮性，算法執(zhí)行有限步后結束；確定性，每一條指令的含義都明確；可行性，算 法是可行的。算法與程序的區(qū)別：程序必須依賴于計算機程序語言，而一個算法可用自然語言、計算機程序語言、數(shù)學語言或約定的符號語言來描述。目前常用的描述算法語言有兩類： 類Pascal和類a.評價算法的優(yōu)劣：算法的正確性”是首先要考慮的。止匕外，主要考慮如下三點：執(zhí)行算法所耗費的時間，即時間復雜性；執(zhí)行算法所耗費的存儲

4、空間，主要是輔助空間，即空間復雜性；算法應易于理解、易于編程，易于調試等，即可讀性和可操作性。以上幾點最主要的是時間復雜性，時間復雜度常用漸進時間復雜度表示。.算法求解問題的輸入量稱為問題的規(guī)模，用一個正整數(shù)n表示。.常見的時間復雜度按數(shù)量級遞增排列依次為：常數(shù)階 0(1)、對數(shù)階0(log 2n)、線性 階0(n)、線性對數(shù)階0(nlog 2n)、平方階0(n2)立方階0(n3)、k次方階0(nk)、指 數(shù)階0(2n)和階乘階0(n!)。.一個算法的空間復雜度 S(n)定義為該算法所耗費的存儲空間，它是問題規(guī)模n的函數(shù)，它包括存儲算法本身所占的存儲空間、算法的輸入輸出數(shù)據(jù)所占的存儲空間和算法

5、 在運行過程中臨時占用的存儲空間。第二章線性表.數(shù)據(jù)的運算是定義在邏輯結構上的，而運算的具體實現(xiàn)是在存儲結構上進行的。.只要確定了線性表存儲的起始位置，線性表中任意一個元素都可隨機存取， 所以順序表是一種隨機存取結構。.常見的線性表的基本運算：(1)置空表InitList (L) 構造一個空的線性表 L。(2)求表長ListLength (L)求線性表L中的結點個數(shù)，即求表長。(3)GetNode (L, i ) 取線性表L中的第i個元素。(4)LocateNode (L, x)在L中查找第一個值為x的元素，并返回該元素在L中的位置。若L中沒有元素的值為x ,則返回0值。(5)InsertLi

6、st (L, i , x)在線性表L的第i個元素之前插入一個值為x的新元素， 表L的長度加1。(6)DeleteList (L, i)刪除線性表L的第i個元素，刪除后表L的長度減1。.順序存儲方法：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元 里的方法。順序表(Sequential List )：用順序存儲方法存儲的線性表稱為順序表。順序表是 一種隨機存取結構，順序表的特點是邏輯上相鄰的結點其物理位置亦相鄰。順序表中結點ai的存儲地址：LOC (a = LOC (a1)+ (i-1 ) *c 1 i data和p- next指針變量p和結點變量*p的關系：指針變量p的值一一結點

7、地址，結點變量*p結點變量*p的值.建立單鏈表:頭插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode); 生成新 結點p-data=ch;/將讀入的數(shù)據(jù)放入新結點的數(shù)據(jù)域中p-next=head; head=p; 一h1八J% A古“苣籽的點畤初河甲鞋表卜end的頭上生成尾插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode);生成新結點p-data=ch; 將讀入的數(shù)據(jù)放入新結點的數(shù)據(jù)域中if (head=NULL) head=p;/新結點插入空表else rear-next=p; 將新結點插到*r之后rear=p

8、;尾指針指向新表尾(3)尾插法建帶頭結點的單鏈表:頭結點及作用：頭結點是在鏈表的開始結點之前附加一個結點。它具有兩個優(yōu)點.由于開始結點的位置被存放在頭結點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致，無須進行特殊處理；.無論鏈表是否為空，其頭指針都是指向頭結點的非空指針(空表中頭結點的指針域空)，因此空表和非空表的處理也就統(tǒng)一了頭結點數(shù)據(jù)域的陰影表示該部分不存儲信息。在有的應用中可用于存放表長等附加信Fl-d F1Fl-d F1th)節(jié)工牯點的隼漫眉息。具體算法:r=head;/具體算法:r=head;/尾指針初值也指向頭結點while(ch=getchar()!=n

9、)s=(ListNode *)malloc(sizeof(ListNode);/生成新結while(ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);/生成新結域中s-data=ch;/域中s-data=ch;/將讀入的數(shù)據(jù)放入新結點的數(shù)據(jù)r-next=s;r=s;r-next=NULL;/終端結點的指針域置空，或空表的頭結點指針域置空以上三個算法的時間復雜度均為O(n)。鏈表上的查找：(帶頭結點)(1)按結點序號查找：序號為0的是頭結點。算法：p=head;j=0;/從頭結點開始掃描while(p-next&jnext while(p

10、-next&jnext 為 NULL或 i=j為止p=p-next;j+；if(i=j) return p;/找到了第if(i=j) return p;/找到了第i個結點else return NULL;/當i0else return NULL;/當i0時，找不到第i個結點時間復雜度：在等概率假設下，平均時間復雜度為：為n/2=O(n)(2)按結點值查找:具體算法：ListNode *p=head-next;/從開始結點比較。表非空，p初始值指向開始結點while(p&p-data!=key)直到 p 為 NULL p-data 為 key 為止p=p-next; 掃描下一結點return p

11、; 若p=NULL則查找失敗，否則p指向值為key的結點時間復雜度為：O(n)9.插入運算：插入運算是將值為x的新結點插入到表的第i個結點的位置上，即插入到ai-i 與 ai N 間。I吠Ibend中F 幀 L，I N1| lb 二 -U 1在年鉞也插入修疝示意由s=(ListNode *)malloc(sizeof(ListNode); s-data=x; s-next=p-next; p-next=s;算法的時間主要耗費在查找結點上，故時間復雜度亦為O(n)。.刪除運算hl*R d.i 匚立二* * *曲 I 卜h * ,I單伏箍卜制除皓白示點圖r=p-next;使r指向被刪除的結點ai

12、p-next=r-next;將ai從鏈上摘下free(r);釋放結點ai的空間給存儲池算法的時間復雜度也是 O (n) .p指向被刪除的前一個結點。鏈表上實現(xiàn)的插入和刪除運算，無須移動結點，僅需修改指針。.單循環(huán)鏈表一在單鏈表中，將終端結點的指針域NULLa為指向表頭結點或開始結點 即可。判斷空鏈表的條件是 head=head-next;.僅設尾指針的單循環(huán)鏈表：用尾指針rear表示的單循環(huán)鏈表對開始結點a1和終端結點an查找時間都是0(1)。而表的操作常常是在表的首尾位置上進行，因此，實用中多采用尾指針表示單循環(huán)鏈表。判斷空鏈表的條件為rear=rear-next;.循環(huán)鏈表：循環(huán)鏈表的特點

13、是無須增加存儲量，僅對表的鏈接方式稍作改變，即可 使得表處理更加方便靈活。若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時間是0(1)。 p p； IIx 西十一-的二.|/假設/假設A,B為非空循環(huán)鏈表的LinkList Connect(LinkList A,LinkList B)尾指針LinkList p=A-next;/ 保存A表的頭結點位置A-next=B-next-next;/B表的開始結點鏈接到 A表尾free(B-next);/ 釋放B表的頭結點B-next=p;/ return B;/返回新循環(huán)鏈表的尾指針循環(huán)鏈表中沒有NULLI旨針。涉及遍歷操作時，其終止

14、條件就不再是像非循環(huán)鏈表 那樣判別p或p-next是否為空，而是判別它們是否等于某一指定指針，如頭指針或 尾指針等。在單鏈表中，從一已知結點出發(fā)，只能訪問到該結點及其后續(xù)結點，無法找到該結點之前的其它結點。而在單循環(huán)鏈表中，從任一結點出發(fā)都可訪問到表中所有結點，這一優(yōu)點使某些運算在單循環(huán)鏈表上易于實現(xiàn).雙向鏈表：雙（向）鏈表中有兩條方向不同的鏈，即每個結點中除next域存放后繼結點地址外，還增加一個指向其直接前趨的指針域priorIU（b）空的雙智環(huán)鞋花U.IU（b）空的雙智環(huán)鞋花U.雙鏈表由頭指針head惟一確定的。帶頭結點的雙鏈表的某些運算變得方便。將頭結點和尾結點鏈接起來，為雙（向） 循

15、環(huán)鏈表。.雙向鏈表的前插和刪除本結點操作雙鏈表的前插操作void DInsertBefore(DListNode *p,DataType x)在帶頭結點的雙鏈表中，將值為 x的新結點插入*p之前，設p？NULLDListNode *s=malloc(sizeof(DListNode);/ s-data=x;/ s-prior=p-prior;s-next=p;/ p-prior-next=s;/ p-prior=s;/雙鏈表上刪除結點*p自身的操作void DDeleteNode(DListNode *p) TOC o 1-5 h z /在帶頭結點的雙鏈表中，刪除結點*p，設*p為非終端結點

16、p-prior-next=p-next;p-next-prior=p-prior;free(p); /與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算法的時間復雜度均為0(1)。.順序表和鏈表比較時間性能：a、線性表：經常性的查找；b、鏈式存儲結構：經常插入刪除操作；空間性能：a、對數(shù)據(jù)量大小事先能夠知道的用線性表；b、數(shù)據(jù)量變化較大的用鏈式存儲結構。存儲密度越大，存儲空間的利用率越高。顯然，順序表的存儲密度是 1,鏈表的存儲密 度肯定小于1。第三章棧和隊列.棧稱為后進先出(Last In First Out )的線性表，簡稱為LIFO表。棧是運

17、算受限的線性表，順序棧也是用數(shù)組表示的。進棧操作：進棧時，需要將 S-top加1,S-top=StackSize-1表示棧滿上溢現(xiàn)象-當棧滿時，再做進棧運算產生空間溢出的現(xiàn)象。退棧操作：退棧時，需將 S-top減1,S-topfront=Q-rear=0;判隊空：return Q-rear=Q-front; 判隊滿：return (Q-rear+1)%QueueSize=Q-front;入隊 Q-dataQ-rear=x;/新元素插入隊尾Q-rear=(Q-rear+1)%QueueSize;出隊 temp=Q-dataQ-front;Q-front=(Q-front+1)%QueueSize

18、;/ 循環(huán)意義下的頭指針加 1return temp;取隊頭元素 return Q-dataQ-front;6.隊列的鏈式存儲結構簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。為了簡化處理，在隊頭結點之前附加一個頭結點，并設隊頭指針指向此結點。弋時I怖方隊昆骷方山)空疏阿砧)在空隊同鏈隊列的基本運算：(帶頭結點)(1)構造空隊：Q-rear=Q-front ; Q-rear-next=NULL;判隊空：return Q-rear=Q-front;入隊：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申請新結p-data=x;p-n

19、ext=NULL;p-data=x;p-next=NULL;Q-rear-next=p;/*p 鏈到原隊尾結點后Q-rear=p;隊尾指針 指向新的尾(4)出隊：當隊列長度大于1時，只需修改頭結點指針，尾指針不變 s=Q-front-next; Q-front-next=s-next;x=s-data; free(s); return x;當隊列長度等于1時，不僅要修改頭結點指針，還要修改尾指針s=Q-front-next; Q-front-next=NULL; Q-rear=Q-front;x=s-data; free(s); return x;(5) 取隊頭元素：return Q-fron

20、t-next-data; 因為有頭結點，所以用了 next和鏈棧類似，無須考慮判隊滿的運算及上溢。在出隊算法中，一般只需修改隊頭指針。但當原隊中只有一個結點時，該結點既是隊 頭也是隊尾，故刪去此結點時亦需修改尾指針，且刪去此結點后隊列變空。7.用計算機來處理計算算術表達式問題，首先要解決的問題是如何將人們習慣書寫的中 綴表達式轉換成后綴表達式。第四章 多維數(shù)組和廣義表.數(shù)組的順序存儲方式：一般采用順序存儲方法表示數(shù)組。(1 ) 7r順a 11,a 12, ,a 1n,a 21,a 22,a 2n, ,am1,a m2,amn2) 列順a 11,a 21, ,，a m1,a 12,a 22,，a

21、 m2, ,an,a 2n,，amnPascal和C語言是按行優(yōu)先順序存儲的，而 Fortran語言是按列優(yōu)先順序存儲的。按行優(yōu)先順序存儲的二維數(shù)組 Amn地址計算公式LOC(a尸LOC(a11)+(i-1)Xn+j-1 xd (注：此公式下界為1,如下界為0,則公式變?yōu)閕 xn+j)按列優(yōu)先順序存儲的二維數(shù)組 Amn地址計算公式LOC(a尸L0C(aii)+(j-1) xm+i-1 xd(注：此公式下界為1,如下界為0,則公式變 為j xm+i)按行優(yōu)先順序存儲的三維數(shù)組 Amnp地址計算公式LOC(ak 尸L0C(aiii)+(i-1)xnxp+(j-1) xp+k-1 xd (注：此公式

22、下界為 1,如下界為0,則公式變?yōu)閕 x nx p+j x p+k)2.為了節(jié)省存儲空間，可以對矩陣中有許多值相同或值為零的元素的矩陣，采用壓縮存儲。特殊矩陣是指相同值的元素或零元素在矩陣中的分布有一定的規(guī)律。常見的有對稱矩陣、三角矩陣。(1)對稱矩陣 在一個n階方陣A中，若元素滿足下述性質：a j =aji 0 i ,j n-1稱為n階對稱矩陣，它的元素是關于主對角線對稱的，所以只需要存儲矩陣上三角 或下三角元素即可，讓兩個對稱的元素共享一個存儲空間。矩陣元素aj和數(shù)組元素sa k之間的關系是k=i x(i+1)/2+j i 刁 0 kn(n+1)/2-1 k=jx (j+1)/2+i i

23、j 0 kn(n+1)/2-1對稱 矩陣的 地址計 算公式：LOC(a尸LOC(sa0)+Ix (I+1)/2+J x d ,其中I=max(i,j) , J=min(i,j)(2)三角矩陣：以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣是指 它的下三角(不包括主角線)中的元素均為常數(shù)c或零；下三角矩陣的主對角線上方均為 常數(shù)c或零。一般情況，三角矩陣的常數(shù)c均為零。三角矩陣的壓縮存儲：三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正 好有nX(n+1)/2個，因此，三角矩陣可壓縮存儲在一維數(shù)組 san(n+1)/2+1中，其中 c存放在數(shù)組的最后一個元素中。上三角矩陣中aj和

24、sak之間的對應關系k=i x(2n-i+1)/2+j-i 當 i j下三角矩陣中aj和sak之間的對應關系k=i x (i+1)/2+j 當 i 刁 k=n x (n+1)/2 當 i j三角矩陣的壓縮存儲結構是隨機存取結構。3.稀疏矩陣：設矩陣Amn中有S個非零元素，若S遠遠小于矩陣元素的總數(shù)，則稱A為稀 疏矩陣。為了節(jié)省存儲單元，可用壓縮存儲方法只存儲非零元素。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須存儲非零元素所在的行、列位置，所以可用三元組(i , j , aj)來確定非零元素。稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲(三元組表)和鏈式存儲(十字鏈表)

25、。稀疏矩陣的壓縮存儲會失去隨機存取功能。V(b.1 dro 5 o o V(b.1 d“ o 。 。 0】a ft-* t7 1瑚旗PH和它的M比一表折|4.廣義表是線性表的推廣，又稱列表。廣義表是n(nA0)個元素ai, a2,，ai,，an的有限序列。其中a或者是原子或者 是一個廣義表。廣義表通常用圓括號括起來，用逗號分隔其中的元素。為了區(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示 原子。若廣義表Ls非空(n A1),則a是LS的表頭，其余元素組成的表(ai,a2, an)稱為Ls的表尾。廣義表具有遞歸和共享的性質 廣義表的深度：一個表展開后所含括號的層數(shù)稱為廣義表的深度。

26、19.廣義表是一種多層次的線性結構，實際上這就是一種樹形結構。廣義表的兩個特殊 的基本運算：取表頭 head(Ls)和取表尾tail(Ls).任何一個非空廣義表的表頭可以是原子，也可以是子表，而其表尾必定是子表。head=(a , b尸a , tail(a , b)=(b)對非空表A和(y),也可繼續(xù)分解。注意：廣義表()和()不同。前者是長度為0的空表，對其不能做求表頭和表尾的運 算；而后者是長度為l的由空表作元素的廣義表，可以分解得到的表頭和表尾均是空表 ()。廣義表是一種有層次的非線性結構，通常采用鏈式存儲結構，每個元素用一個結點 表示，結點由3個域構成，其中一個是tag標志位，用來區(qū)分

27、結點是原子還是子表，當 tag為零時結點是子表，第二個域為 slink ,用以存放子表的地址；當tag為1時結點 是原子，第二個域為data,用以存放元素值。第五章樹和二叉樹1.樹的表示法：最常用的是樹形圖表示法；還有 3種嵌套集合、凹形、廣義表。樹結構的基本術語(1)結點的度(Degree)樹中的一個結點擁有的子樹數(shù)稱為該結點的度(Degree)。一棵樹的度是指該樹中結點的最大度數(shù)。度為零的結點稱為葉子(Leaf)或終端結點。度不為零的結點稱分支結點或非終端結點。除根結點之外的分支結點統(tǒng)稱為內部結點。根結點又稱為開始結點。(2)路徑(path)若樹中存在一個結點序列 匕，k2,，ki,使得k

28、i是ki+1的雙親(1 i 0)棵互不相交的樹的集合。樹和森林的概念相近。刪去 一棵樹的根，就得到一個森林；反之，加上一個結點作樹根，森林就變?yōu)橐豢脴洹?二叉樹與度數(shù)為2的有序樹不同：在有序樹中，雖然一個結點的孩子之間是有左右次 序的，但是若該結點只有一個孩子，就無須區(qū)分其左右次序。而在二叉樹中，即使是一 個孩子也有左右之分。二叉樹的性質：性質1二叉樹第i層上的結點數(shù)目最多為2i-1(i 1)o例如5層的二叉樹，第5層上的 結點數(shù)目最多為24=16性質2深度為k的二叉樹至多有2k-1個結點(kA 1)。例如深度為5的二叉樹，至多有 25-1=31個結點性質3在任意-棵二叉樹中，若終端結點的個數(shù)

29、為n。，度為2的結點數(shù)為巾，則=窕+1。 例如一棵深度為4的二叉樹(a),其終端結點數(shù)n。為8,度為2的結點樹為7,則8=7+1, no=n2+1 成立(b)其終端結點數(shù)n。為6,度為2的結點樹為5,則6=5+1,/=n+1成立滿二叉樹：一棵深度為k且有2k-1個結點的二又樹稱為滿二叉樹。滿二叉樹的特點：(1)每一層上的結點數(shù)都達到最大值。即對給定的高度，它是具有最多結點數(shù)的二叉樹。(2)滿二叉樹中不存在度數(shù)為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。完全二叉樹：若一棵深度為k的二叉樹，其前k-1層是一棵滿二叉樹，而最下面一層上 的結點都集中在該層最左邊的若干位置上，

30、則此二叉樹稱為完全二叉樹。特點：(1)滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。(2)在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結點后得到的二 叉樹仍然是一棵完全二叉樹。(3)在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該 結點必是葉結點。性質4具有n個結點的完全二叉樹的深度為。？ logn? +1或？ log(n+1) ?例，具有100個結點的完全二叉樹的深度為：？ lg100? +1=7,26=64 27=128所以？ lg100 ? =6 , ? lg(100+1) ? =7.完全二叉樹的編號特點：完全二叉樹中除最下面一層外， 各層都充滿了結點。每一層 的結

31、點個數(shù)恰好是上一層結點個數(shù)的 2倍。從一個結點的編號就可推得其雙親，左、 右孩子等結點的編號。編號從 。開始若i=0 ,則q為根結點，無雙親；否則，qi的雙親編號為？(i-1)/2 ?。若2i+1n,則qi的左孩子的編號是2i+1 ;否則，qi無左孩子，即qi必定是葉子。若2i+2n ,則qi的右孩子的編號是2i+2 ;否則，q無右孩子。對于完全二叉樹而言，使用順序存儲結構既簡單又節(jié)省存儲空間。 但對于一般二叉樹來 說，采用順序存儲時，為了使用結點在數(shù)組中的相對位置來表示結點之間的邏輯關系， 就必須增加一些虛結點使其成為完全二叉樹的形式。.鏈式存儲結構：二叉樹的每個結點最多有兩個孩子。用鏈接方

32、式存儲二叉樹時，每個 結點除了存儲結點本身的數(shù)據(jù)外，還應設置兩個指針域Ichild和rchild ,分別指向該 結點的左孩子和右孩子。結點的結構為：二叉鏈表是一種常用的二叉樹存儲結構。建立二叉鏈表方法：a、按廣義表方法，靠近左括號的結點是在左子樹上，而逗號右邊 結點是在右子樹上。b、按完全二叉樹的層次順序建立結點具有n個結點的二叉鏈表中，共有2n個指針域。其中有n-1個用來指示結點的左、右 孩子，其余的n+1個為空。二叉樹遍歷算法中的遞歸終止條件是二叉樹為空。中序遍歷的遞歸算法定義：（1）遍歷左子樹；（2）訪問根結點；（3）遍歷右子樹。先序遍歷的遞歸算法定義：（1）訪問根結點；（2）遍歷左子樹

33、；（3）遍歷右子樹。后序遍歷得遞歸算法定義：（1）遍歷左子樹；（2）遍歷右子樹；（3）訪問根結點。遞歸工作棧中包括兩項：一項是遞歸調用的語句編號，另一項則是指向根結點的指針。已知一棵二叉樹的前序和中序遍歷序列或中序和后序遍歷序列，可唯一確定一棵二叉樹。具體方法如下：首先根據(jù)前序或后序遍歷序列確定二叉樹的各子樹的的根，然后根據(jù)中序遍歷序列確 定各子樹根的左右子樹。.線索二叉樹：n個結點的二叉鏈表必定存在 n+1個空指針域，可以利用這些空指針域, 存放指向結點在某種遍歷次序下的前趨和后繼結點的指針， 這種指向前驅和后繼結點的 指針稱為線索，這種加上線索的二叉鏈表稱為線索鏈表， 相應的二叉樹稱為線索

34、二叉 樹(Threaded BinaryTree)。1childdatarrhi1d產上也士中的通如產上也士中的通如校第二其中:ltag和rtag是增加的兩個標志域，用來區(qū)分結論中學唔ft叱/論中學唔ft叱/井標士汗門口 _/口上代加提指向結點晌左孩子的指針 工何心目U1出“娓指向結點的前趨的左線索志也目/0,k加提指向結點的右孩子的指針 卜一疝娓指向結點的后維的右線索志也目圖中的實線表示指針，虛線表示線索。線索二叉樹中，一個結點是葉結點的充要條件為：左、右標志均是 1.二叉樹的線索化：把對一棵二叉線索鏈表結構中所有結點的空指針域按照某種遍歷 次序加線索的過程稱為線索化。和中序遍歷算法一樣，遞

35、歸過程中對每結點僅做一次訪問。因此對于n個結點的二叉樹, 線索化的算法時間復雜度為O(n)。.樹、森林到二叉樹的轉換：樹中每個結點最多只有一個最左邊的孩子 (長子)和一個右 鄰的兄弟。將樹轉換成二叉樹：在所有兄弟結點之間加一道連線； 對每個結點，除了保留與其 長子的連線外，去掉該結點與其它孩子的連線。由于樹根沒有兄弟，故樹轉化為二叉樹 后，二叉樹的根結點的右子樹必為空。第必.樹中廝打兄希右兄 之間加11線A、第二步t對第必.樹中廝打兄希右兄 之間加11線A、第二步t對5個結點，除了保 別。其的長了的在線外r 公掉慢站點。乩他找子的 連續(xù)/ /lE -F （； H-l-J將一個森林轉換為二叉樹將

36、森林中的每棵樹轉化成二叉樹，然后再將二叉樹的根節(jié)點看做兄弟連在一起，形成一棵二叉樹p 141第二步T將* 父樹的強點根 為兄弟從左至右連住一 厘.就形成一株二丈一棵二叉樹p 141第二步T將* 父樹的強點根 為兄弟從左至右連住一 厘.就形成一株二丈料9.二叉樹到樹、森林的轉換方式是：若二叉樹中結點x是雙親y的左孩子，則把x的右孩子，右孩子的右孩子，, 都與y用連線連起來，最后去掉所有雙親到右孩子的連線。10.樹的存儲結構：.雙親表示法：雙親鏈表表示法利用樹中每個結點 的雙親唯一性，在存儲結點信息的同時，為每個結 點附設一個指向其雙親的指針 parent ,惟一地表示 任何-棵樹。(1)雙親鏈表

37、表示法的實現(xiàn)A國&iTOi)分析：E10.樹的存儲結構：.雙親表示法：雙親鏈表表示法利用樹中每個結點 的雙親唯一性，在存儲結點信息的同時，為每個結 點附設一個指向其雙親的指針 parent ,惟一地表示 任何-棵樹。(1)雙親鏈表表示法的實現(xiàn)A國&iTOi)分析：E和F所在結點的雙親域是1,它們的雙親結點在向量中的位置是 1,即B是它們的雙親注意： 根無雙親，其parent域為-1。 雙親鏈表表示法中指針parent向上鏈接，適合求指定結點的雙親或祖先(包括根)；求指定結點的孩子或其它后代時，可能要遍歷整個數(shù)組。.孩子鏈表法：孩子鏈表表示法是為樹中每個結點設置一個孩子鏈表，并將這些結點及相應的

38、孩子鏈表的頭指針存放在一個向量中注意： 孩子結點的數(shù)據(jù)域僅存放了它們在向量空間的序號 與雙親鏈表表示法相反，孩子鏈表表示便于實現(xiàn)涉及孩子及其子孫的運算,但不便于實現(xiàn)與雙親有關的運算將雙親鏈表表示法和孩子鏈表表示法結合起來，可形成雙親孩子鏈表表示pm；舊 pm；舊 I- I / c I J a UI I a | )MEI 4-TTfTTI I 卜4+ IA1III -Hl-vn國瓦LT國帙化力又柑S)力用的覆了坨弟位舞3.孩子兄弟表示法：在存儲結點信息的同 時，附加兩個分別指向該結點最左孩子和 右鄰兄弟的指針域，即可得樹的孩子兄弟 鏈表表示。汪息：這種存儲結構的最大優(yōu)點是：它和二叉樹的二叉鏈表表

39、示完全一樣?？衫枚鏄涞乃惴▉韺崿F(xiàn)對樹的操作。11.樹的遍歷：一般都只給出兩種次序遍歷樹的方法：前序 （先根次序）遍歷和后序（后根次序）遍歷。前序遍歷一棵樹等價于前序遍歷該樹對應的二叉樹 后序遍歷一棵樹等價于中序遍歷該樹對應的二叉樹。對下面（a）圖中所示的森林進行前序遍歷和后序遍歷，則得到該森林的前序序列和后序序列分別為ABCDEFIGJH口 BDCAIFJGHE而（b）圖所示二叉樹的前序序列和中序序列也分另U分另U為 ABCDEFIGJ和 BDCAIFJGHE前序遍歷森林等同于前序遍歷該森林對應的二叉樹后序遍歷森林等同于中序遍歷該森林對應的二叉樹12.從根結點到某結點之間的路徑長度與該結點

40、上權的乘積稱為該結點的帶權路徑長度，樹種所有葉子結點的帶權路徑長度之和稱為樹的帶權路徑長度。帶權路徑長度WP最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。哈夫曼樹不一定是二叉樹。哈夫曼樹又稱為最優(yōu)樹，是一類 帶權路徑長度最短的樹。完全二叉樹就是這種 路徑長度最短的二叉樹。 只有葉結點上的權值均相同時，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹 不一定是最優(yōu)二叉樹。 最優(yōu)二叉樹中，權越大的葉子離根越近。 最優(yōu)二叉樹的形態(tài)不唯一，WP最小。13.哈夫曼算法：基本思想是：(1)根據(jù)給定的n個權值w, w,，wn構成n棵二叉樹的森林F=， 丁2,，Tn,其中每棵二叉樹T中都只有一個權值為W的根結點，其左右子樹

41、均空。(2)在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時，可以從中 任選兩棵)，將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新 結點作為新樹的根，并將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關緊要)，將這兩個孩子的權值之和作為新樹根的權值。(3)對新的森林F重復(2),直到森林F中只剩下一棵樹為止。這棵樹便是哈夫曼 樹。注意： 初始森林中的n棵二叉樹，每棵樹有一個孤立的結點，它們既是根，又是葉 子n個葉子的哈夫曼樹要經過n-1次合并，產生n-1個新結點。最終求得的哈 夫曼樹中共有2n-1個結點。哈夫曼樹是嚴格的二叉樹，沒有度數(shù)為 1的分支結點圖5,

42、27哈夫曼樹的構造過程示例圖5,27哈夫曼樹的構造過程示例14.哈夫曼編碼:數(shù)據(jù)壓縮過程稱為編碼，反之，解壓縮的過程稱為解碼。設計一種長短不等的編碼，則必須保證任一字符的編碼都不是另一個字符編碼的前綴， 這種編碼稱為前綴編碼?？梢岳枚鏄鋪碓O計二進制的前綴編碼，其左分支表示字符0,右分支表示字符1,則以根結點到葉結點路徑上的分支字符組成的串作為該葉節(jié)點的字符編碼。因此設計電文總長最短的二進制前綴編碼， 就是以n種字符出現(xiàn)的頻率作為權構造一 棵哈夫曼樹，由哈夫曼樹求得的編碼就是哈夫曼編碼。譯碼過程是從樹根結點出發(fā)，逐個讀入電文中的二進制碼。第六章圖.圖G由兩個集合構成，頂點集合和邊集合，也可以

43、圖G只有頂點而沒有邊。用尖括號 表示圖的有向邊,有向邊又稱為弧，起點稱為弧尾，終點稱為弧頭。無向圖的頂 點對用圓括號表示(Vi,Vj)。在無向圖中，稱Vi和Vj相鄰接，在有向圖中稱頂點Vi鄰接到Vj,頂點Vj鄰接于Vi 在無向圖中，n的取值范圍是0-n(n-1)/2 ,將具有n(n-1)/2條邊的無向圖稱為無向完 全圖。在有向圖中，n的取值范圍是0-n(n-1),將具有n(n-1)條邊的有向圖稱為有向完全圖。無向圖中，頂點的度定義為以該頂點為一個端點的邊的數(shù)目，有向圖的度等于出度和入度之和。在無向圖中，任意兩頂點都有路徑，則稱兩頂點連通。若圖G中的任意兩個頂點都連通，稱G為連通圖。無向圖的極大

44、連通子圖稱為連通分量，顯然，任何連通圖的連通分 量只有一個，即其自身，而非連通的無向圖有多個連通分量。在有向圖中，圖G中任意兩頂點連通，稱為強連通圖，極大連通子圖稱為強連通分量。若在一個圖的每條邊上標上某種數(shù)值，該數(shù)值稱為該邊的權。邊上帶權的圖稱為帶權圖， 帶權的連通圖稱為網絡。.圖的存儲結構：鄰接矩陣和鄰接表表示法。圖的頂點編號從 0開始。鄰接矩陣表示法：Vi,Vj或(Vi,Vj)是邊，則值為1,不是邊則值為0。無向圖的鄰接矩陣是按主對角線對稱的。 若G是帶權圖，只要把1換成相應邊上的權值 即可，0的位置上可以不動或將其換成無窮大表示。無向圖的鄰接矩陣表示法可以僅存 儲主對角線以下的元素，時

45、間復雜度為 O(n2)鄰接表表示法：鄰接表是圖的一種鏈式存儲結構。 將無向圖的鄰接表稱為邊表，將有 向圖的鄰接表稱為出邊表，將鄰接表的表頭向量稱為頂點表。若無向圖有 n個頂點和e 條邊，則它的鄰接表共有n個頭結點和2e個表結點。建立鄰接表的時間復雜度是 O(n+e)。圖的鄰接表表示不是唯一的，這是因為在每個頂 點的鄰接表中，各邊結點的鏈接次序可以是任意的，其具體鏈接次序與邊的輸入次序和 生成算法有關。.圖的遍歷：遍歷圖的算法是求解圖的連通性、圖的拓撲排序等算法的基礎。圖的遍歷常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種方法。深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷。按訪問頂點的先后次

46、序得到的頂點 序列稱為圖的深度優(yōu)先遍歷序列，或簡稱為DFS序列。共需要搜索n2個矩陣元素，時間復雜度為鄰接矩陣O(n2)或鄰接表O(n+e)。廣度優(yōu)先搜索遍歷(BFS)類似于樹的按層次遍歷，先被訪問的頂點，其鄰接點也先被 訪問，就是先進先出。時間復雜度為鄰接矩陣 O(n2)或鄰接表O(n+e),空間復雜度都是 O(n)。.生成樹是連通圖的包含圖中所有頂點的一個極小連通子圖，一個圖的極小連通子圖恰為一個無回路的連通圖，也就是說，若圖中任意添加一條邊，就會出現(xiàn)回路，若去掉任意一條邊，都會使之成為非連通圖。因此，一個具有n個頂點的生成樹有且僅有n-1條邊，但有n-1條邊的圖不一定是生 成樹，同一個圖

47、可以有不同的生成樹。生成樹定義為：若從圖的某頂點出發(fā)，可以系統(tǒng)的訪問到圖的所有頂點， 則遍歷時經過的邊和圖的所有頂點所構成的子圖，稱為該圖的生成樹。最小生成樹：圖的生成樹不唯一，把權值最小的生成樹稱為最小生成樹( MST。構造最小生成樹的算法：普里姆Prim算法的時間復雜度為O( n2)與網中邊數(shù)無關適 于稠密圖?？唆斔箍朘ruskal算法的時間復雜度為 O (eloge),主要取決于邊數(shù)，較適合于稀疏圖【例03】利用普里姆算法，給出求圖6.17 (a)所示的無向網絡的最小生成樹的過程。5.最短路徑：Dijkstra迪杰斯特拉算法，提出了按路徑長度遞增的順序產生諸頂點的最短路徑算法拓撲排序：

48、子工程稱為活動，頂點代表活動，有向邊代表活動的先后關系。這樣的有向無環(huán)圖DA第為頂點活動網，簡稱為AOV。將有向無環(huán)圖G中所有頂點排成一個線性序列，若6E (G),則在線性序列u在v之前，這種線性序列稱為拓撲序 列。由AO颯構造拓撲序列的過程稱為拓撲排序。檢測的方法是：對有向圖構造其頂點的拓撲序列，若網中所有頂點都在他的拓撲序列 中，則AOVJ必定不存在環(huán)。AOV網的拓撲序列不是唯一的。拓撲排序的描述思想：a、在有向圖中選一個沒有前趨(入度為零)的頂點，且輸出之 b、從有向圖中刪除該頂點及其與該頂點有關的所有邊。 c、重復上述步驟，直到全部頂 點都已輸出或圖中剩余的頂點中沒有前趨頂點為止。d、

49、輸出剩余的無前趨結點。拓撲排序實際上是對鄰接表表示的圖G進行遍歷的過程。時間復雜度是 O(n+e)圖6.22迪杰斯特拉算法求圖621的單源最短路惶示意圖第七章排序.如果待排序文件中存在多個關鍵字相同的記錄，經過排序后，這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；反之，則是不穩(wěn)定的。排序在內存中處理，不涉及數(shù)據(jù)的內外存交換，稱為內部排序，反之為外部排序。內部排序又分為五類：插入、選擇、交換、歸并和分配排序。在排序過程中需進行兩種操作：比較兩個關鍵字的大小、改變指向記錄的指針或移動 記錄本身，而待排序記錄的存儲形式一般有三種：順序結構、鏈式結構和輔助表。評價排序算法的標準：

50、執(zhí)行算法需要的時間，以及算法所需要的附加空間。還有算法 本身的復雜度。排序的時間開銷，一般情況下可用算法中關鍵字的比較次數(shù)和記錄的移動次數(shù)來衡 里。.插入排序：每次將一個待排序記錄按其關鍵字大小插入到前面已排好序的文件中的適 當位置。直接插入排序：每次從無序區(qū)取出第一個元素把它插入到有序區(qū)的適當位置，使之成為新的有序區(qū)，經過n-1次插入后完成。算法中R0作用：保存Ri副本，監(jiān)視數(shù)組 下標變量j是否越界。所以R0稱為哨兵。每次的比較是從后往前比較的。時間復雜度最好是O(n),最壞是O(n2),所以是O(n2)。空間復雜度0(1),所以是就地 排序。是穩(wěn)定的算法。初始情況是有序區(qū)中只有一個元素 R

51、1,無序區(qū)中R2.n。希爾排序(縮小增量排序)：算法不穩(wěn)定。記錄的總比較次數(shù)和總移動次數(shù)都要比直接插入排序少得多，特別是當n越大越明顯。希爾排序的時間依賴于增量序列，最后一個增量必須是1,盡量避免增量互為倍數(shù)的情況。 TOC o 1-5 h z F 標1之3*1567g9 IQ期怕矣檀字36254H27652543 576 321, -tld=s 2525 4827 3236435876 65L_LII _IIJ卡 3店 25 36 27 32 48 43 58 76 分25 25 27 32 36 43 4s SB d 7&圖7希爾排序示例.交換排序：兩兩比較待排序記錄的關鍵字，如果發(fā)現(xiàn)兩個

52、記錄的次序相反時即進行交 換，直到沒有反序位置。冒泡排序(起泡排序)：通過相鄰元素之間比較和交換，使較小移向頂部，從后往前兩 兩比較。時間復雜度最好是0(n),最壞是0(n2),所以是0(n2)。是穩(wěn)定的排序算法?？焖倥判?劃分交換排序)：是冒泡排序的改進。比較和交換從兩端向中間進行。一趟快速排序步驟：設兩個指針i和j ,初值分別為low和high ,基準為x=Ri,首 先從j位置開始向前搜索第一個小于基準 x.key的記錄存入i所指位置上，i自增1, 然后從i所指位置向后搜索找到第一個大于基準x.key的記錄存入j所指位置上，j自O(nlog 2n),減1,O(nlog 2n),快速排序是不

53、穩(wěn)定的。有非常好的時間復雜度，優(yōu)于其他各種排序算法,但是當記錄關鍵字有序或基本有序時復雜度反而大了使之轉變成冒泡排序為O(n2)?？焖倥判蚴沁f歸的，需要一個?？臻g，空間復雜度O(log2n)。初始關鍵字45 S3 18 49 36 76 13 97 36 32一次劃分后3236181336 45 76 97 49 53二次劃分后131832 3636 45 53 49 76 97三次劃分后1318323636 45(49 53 76 97最后的結果1318323636 45 49 53 76 97.選擇排序：每一趟在待排序的記錄中選出關鍵字最小的記錄，依次存放在已排序好的記錄序列的最后。直接選

54、擇排序：初始時，R1.n為無序區(qū)，R1為空；第一趟是在 R1.n中選出 最小的記錄與R1交換，R1為有序區(qū)；第二趟是在R2.n中選出最小的記錄與 R2 交換，R1.2為有序區(qū)。時間復雜度 O(n2),是不穩(wěn)定的。初始情況是有序區(qū)為空，無序區(qū)中R1.n,第一趟從R1.n選擇最小記錄與 R1交換。堆排序：是對直接選擇排序的改進，是一種樹形選擇排序?；舅枷耄涸谂判蜻^程中， 將記錄數(shù)組R1.n看成是一棵完全二叉樹的順序存儲結構， 利用完全二叉樹中雙親結 點和孩子結點之間的內在關系，在當前無序區(qū)中選擇關鍵字最大或最小記錄。每一趟排序：將當前無序區(qū)調整為一個大根堆，選取關鍵字最大的堆頂記錄，將他和無序區(qū)

55、中最后一個記錄交換。堆排序是一個不斷建堆的過程。構造堆的過程：R1作為二叉樹的根，R2.n依次逐層從左到右順序排列，構成一棵完全二叉樹，任意名點Ri的左孩子是R2i,右孩子 是R2i+1,雙親是R? i/2 ?,此稱為篩選法。從？ n/2?開始。每一趟的時間復雜度是 O(log 2n),整個堆排序的時間復雜度是 O(nlog 2n)。.歸并排序：首先將待排序文件看成n個長度為1的有序子文件，把這些子文件兩兩歸 并，得到？ n/2?個長度為2的有序子文件，然后再將他們兩兩歸并，如此反復，直到 得到一個長度為n的有序文件，此稱為二路歸并排序。每一趟歸并排序的時間復雜度是O(n),所以總的時間復雜度

56、是 O(nlog2n)及=7U2(18 53JL 口可 1J4國1J吧一蹲歸并:|1872J 36 53J四陽四:Afi打井；J18 72】北48三精歸并：ILK31北364SS3明.分配排序：前面方法都至少需要進行 ？ nlogn ?次比較，而分配排序將時間復雜度降為 O(n)。箱排序(桶排序)：基數(shù)排序：是對箱排序的改進和推廣。箱排序只適用于關鍵字取值范圍較小的情況， 否則所需箱子數(shù)目太多。每個分量可能取值的個數(shù)rd稱為基數(shù)，基數(shù)的選擇和關鍵字的分解因關鍵字的類型而異。d趟箱排序?；鶖?shù)排序中，沒有進行關鍵字的比較和記錄的移動，而只是掃描鏈表和進行指針賦值，所以排序的時間主要用在修改指針上，

57、初始化鏈表時間為O(n)。.內部排序方法分析比較：本章除基數(shù)排序外，都是在順序表上實現(xiàn)的。時間復雜度空間復雜度穩(wěn)定性插入直接插入O(n2)O(1)穩(wěn)定希爾排序O(nlog 2n)或 O(n1.25)O(1)不穩(wěn)定交換冒泡排序O(n2)O(1)穩(wěn)定快速排序O(nlog 2n)O(log 2n)不穩(wěn)定選擇直接選擇O(n2)0(1)不穩(wěn)定堆排序O(nlog 2n)0(1)不穩(wěn)定歸并排序歸并排序O(nlog 2n)0(n)穩(wěn)定分配排序基數(shù)排序O(d*(rd+n)rd 是基數(shù)，d是關鍵字位數(shù).n是元素個數(shù)0(rd+n)穩(wěn)定箱排序選取排序方法時需要考慮的主要因素：a、待排序的記錄個數(shù)，b、記錄本身的大小和

58、存 儲結構，c、關鍵字的分布情況，d、對排序穩(wěn)定性的要求，e、時間和空間復雜度要等 排序方法的選?。篴、若待排序的一組記錄數(shù)目n較小(如nW 50)時，可采用插入排序或選擇排序；b、n 較大時，則應采用快速排序、堆排序或歸并排序；c、若待排序記錄按關鍵字基本有序時，則宜選用直接插入排序或冒泡排序；d、當n很大，而且關鍵字位數(shù)較少時，采用鏈式基數(shù)排序較好；e、關鍵字比較次數(shù)與記錄的初始排列順序無關的排序方法是選擇 排序。一般的排序方法都可以在順序結構上實現(xiàn)，當記錄本身信息量較大時，可采用鏈式存 儲結構。插入、歸并、基數(shù)排序易于在鏈表上實現(xiàn)；快速排序和堆排序可以提取關鍵字建立索 引表，然后對索引表

59、進行排序。第八章：查找.查找又稱檢索，是數(shù)據(jù)處理中經常使用的一種重要運算。查找也分為內查找和外查找。運算查找的主要操作是關鍵字的比較，因此把查找過程中的平均比較次數(shù)（也稱為平均查找長度）作為衡量算法效率優(yōu)劣的標準。.順序表的查找：順序查找和二分查找順序查找又稱線性查找：查找成功的平均查找長度（n+1）/2 ,即約為表長的一半。如果查找成功和不成功機會相等，那么平均查找長度3（n+1）/4。優(yōu)點是簡單，對表的結構無任何要求，無論是順序存儲和鏈式存儲、無論是否有序，都 同樣適用，缺點是效率低。對于有序表來說，該算法的平均查找長度是 （n+1）/2。二分查找（折半查找）：要求查找對象的線性表必須是順

60、序存儲結構的有序表。查找過程是遞歸的。樹中每個子樹的根節(jié)點對應當前查找區(qū)間的中位記錄 Rmid,它的左子樹和右子樹 分別對應區(qū)間的左子表和右子表， 通常將此樹稱為二叉判定樹。由于二分查找是在有序 表上進行的，所以其對應的判定樹必定是一棵二叉排序樹。二叉判定樹一定是二叉排序樹，二叉排序樹又稱為二叉查找樹。從判定樹上可見，關鍵字比較的次數(shù)恰好為該結點在樹中的層數(shù)。因此，二分查找算法在查找成功時進行關鍵字比較的次數(shù)最多不超過判定樹的深度。查找成功時的平均查找長度（n+1）/nlog 2（n+1）-1 ,當n很大時，可近似用log2（n+1）-1表示。因為判定樹 度數(shù)小于2的結點只可能在最下面的兩層，