數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料(親自整理)

1、索引存儲(chǔ)結(jié)構(gòu)、簡(jiǎn)答題1、鏈表：鏈表就是一串存儲(chǔ)數(shù)據(jù)的鏈?zhǔn)浇Y(jié)構(gòu)。鏈?zhǔn)降膬?yōu)點(diǎn)在于，每個(gè)數(shù)據(jù)之間都是相 關(guān)聯(lián)的。2、線性結(jié)構(gòu)：線性結(jié)構(gòu)是一個(gè)有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊(duì)列，雙 隊(duì)列，數(shù)組，串。3、樹與二叉樹二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹；樹是由n (n>=1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。樹和二叉樹的2個(gè)主要差別：1 .樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2;2 .樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分。4、堆堆通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象。堆總是滿足下列性質(zhì)： 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值； 堆總是一

2、棵完全二叉樹。5、二叉排序樹二叉排序數(shù)的(遞歸)定義：1、若左子樹非空，則左子樹所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)；2、若右子樹非空，則右子樹所有節(jié)點(diǎn)的值均大于于它的根節(jié)點(diǎn)；3、左右子樹也分別為二叉排序樹。、應(yīng)用題1、樹與二叉樹前中后序遍歷序列一、已知前序、中序遍歷，求后序遍歷例：前序遍歷：GDAFEMHZ中序遍歷：ADEFGHMZ畫樹求法：第一步，根據(jù)前序遍歷的特點(diǎn)，我們知道根結(jié)點(diǎn)為G第二步，觀察中序遍歷 ADEFGHMZ其中root節(jié)點(diǎn)G左側(cè)的ADEF必然是 root的左子樹，G右側(cè)的HMZ必然是root的右子樹。第三步，觀察左子樹 ADEF,左子樹的中的根節(jié)點(diǎn)必然是大樹的root的leftch

3、ild。在前序遍歷中，大樹的 root的leftchild位于root之后，所以左子樹 的根節(jié)點(diǎn)為D。第四步，同樣的道理，root的右子樹節(jié)點(diǎn) HMZ中的根節(jié)點(diǎn)也可以通過前 序遍歷求得。在前序遍歷中，一定是先把root和root的所有左子樹節(jié)點(diǎn)遍歷完之后才會(huì)遍歷右子樹，并且遍歷的左子樹的第一個(gè)節(jié)點(diǎn)就是左子樹的根節(jié)點(diǎn)。 同理，遍歷的右子樹的第一個(gè)節(jié)點(diǎn)就是右子樹的根節(jié)點(diǎn)。樹與二叉樹的轉(zhuǎn)換 樹轉(zhuǎn)換為二叉樹：步輯2：去線二叉樹線索化撲鼻和層次調(diào)曼多竦；2金除長(zhǎng)子外的孩子去線二叉樹轉(zhuǎn)換為樹:步舞h加線步1給兄第那線步驟3;層秋調(diào)整（b；中用我索鏈表中序線索二叉樹及其存儲(chǔ)能構(gòu)汪思：圖中的實(shí)線表示指針，虛線

4、表示線索。結(jié)點(diǎn)C的左線索為空，表示 C是中序序列的開始結(jié)點(diǎn)，無前趨；結(jié)點(diǎn)E的右線索為空，表示 E是中序序列的終端結(jié)點(diǎn)，無后繼。線索二叉樹中，一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為：左、右標(biāo)志均是1。2、圖鄰接表一、鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鄰接表中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè) 單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（對(duì)有向圖是以頂點(diǎn) Vi為尾的?。?。鄰接表中的表結(jié)點(diǎn)和頭結(jié)點(diǎn)結(jié)構(gòu)：表結(jié)點(diǎn)adj vexn ex t a r cinfo頭結(jié)點(diǎn)dataf i r s t arc、無向圖的鄰接表4、圖 7-5三、有向圖的鄰接表和逆鄰接表（一）在有向圖的鄰接表中，第i個(gè)單鏈表鏈接的邊都是頂點(diǎn) i發(fā)

5、出的邊。（二）為了求第i個(gè)頂點(diǎn)的入度，需要遍歷整個(gè)鄰接表。因此可以建立逆鄰接表。（三）在有向圖的逆鄰接表中，第i個(gè)單鏈表鏈接的邊都是進(jìn)入頂點(diǎn)i的邊。出邊表人邊表四、鄰接表小結(jié) 設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則用鄰接表表示無向圖時(shí)， 需要n個(gè)頂點(diǎn)結(jié)點(diǎn)，2e 個(gè)表結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需 n個(gè)頂點(diǎn)結(jié)點(diǎn)，e個(gè) 邊結(jié)點(diǎn)。 在無向圖的鄰接表中，頂點(diǎn) vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)。 在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)vi的出度。在逆鄰接表中的第 i個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)為 Vi的入度。鄰接矩陣（有向、無向）1 .圖的鄰接矩陣表示法在圖的鄰接矩陣表示法中:用鄰接矩陣表示頂點(diǎn)間的

6、相鄰關(guān)系用一個(gè)順序表來存儲(chǔ)頂點(diǎn)信息2 .圖的鄰接矩陣(Adacency Matrix)設(shè)G=(V , E)是具有n個(gè)頂點(diǎn)的圖，則 G的鄰接矩陣是具有如下性質(zhì)的n階方陣:1若1卬u J或=是宜中的邊0若OjuJ或)不是百中的邊WIV【例】下圖中無向圖 G 5和有向圖G 6的鄰接矩陣分別為 A l和A 2廣度優(yōu)先遍歷廣度優(yōu)先遍歷是連通圖的一種遍歷策略。其基本思想如下:1、從圖中某個(gè)頂點(diǎn) V0出發(fā)，并訪問此頂點(diǎn)；2、從V0出發(fā)，訪問V0的各個(gè)未曾訪問的鄰接點(diǎn)W1, W2,，Wk;然后，依次從W1,W2,Wk出發(fā)訪問各自未被訪問的鄰接點(diǎn)；3、重復(fù)步驟2,直到全部頂點(diǎn)都被訪問為止。例如下圖中：1 .從0

7、開始，首先找到0的關(guān)聯(lián)頂點(diǎn)3,42 .由3出發(fā)，找到1, 2;由4出發(fā)，找到1,但是1已經(jīng)遍歷過，所以忽略。3 .由1出發(fā)，沒有關(guān)聯(lián)頂點(diǎn)；由 2出發(fā)，沒有關(guān)聯(lián)頂點(diǎn)。所以最后順序是0,3,4,1,2深度優(yōu)先遍歷深度優(yōu)先遍歷是連通圖的一種遍歷策略。其基本思想如下：設(shè)x是當(dāng)前被訪問頂點(diǎn)，在對(duì) x做過訪問標(biāo)記后，選擇一條從x出發(fā)的未檢測(cè)過的邊（x, y）。若發(fā)現(xiàn)頂點(diǎn)y已訪問過，則重新選擇另一條從x出發(fā)的未檢測(cè)過的邊，否則沿邊（x, y）到達(dá)未曾訪問過的 v,對(duì)y訪問并將其標(biāo)記為已訪問過；然后從 y開始搜索，直到搜索完從 y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達(dá)的頂點(diǎn)之后，才回到頂點(diǎn) x,并且再選擇一

8、條從 x出發(fā)的未檢測(cè)過的邊。上述過程直至 從x出發(fā)的所有邊都已檢測(cè)過為止。例如下圖中：1 .從0開始，首先找到0的關(guān)聯(lián)頂點(diǎn)32 .由3出發(fā)，找到1;由1出發(fā)，沒有關(guān)聯(lián)的頂點(diǎn)。3 .回到3,從3出發(fā)，找到2;由2出發(fā)，沒有關(guān)聯(lián)的頂點(diǎn)。4 .回至IJ 4,出4出發(fā)，找到1,因?yàn)?已經(jīng)被訪問過了，所以不訪問。所以最后順序是0,3,1,2,4Prim算法基本思想：假設(shè) G=(V, E)是連通的，TE是G上最小生成樹中邊的集合。算法從 U=u0 (u0CV)、TE=開始。重復(fù)執(zhí)行下列操作：在所有uCU, vCVU的邊(u, v)C E中找一條權(quán)值最小的邊(u0,v0)并入集合TE中，同 時(shí)v0并入U(xiǎn),直

9、到V=U為止。此時(shí)，TE中必有n-1條邊，T=(V, TE)為G的最小生成樹。Prim算法的核心：始終保持TE中的邊集構(gòu)成一棵生成樹。注意：prim算法適合稠密圖，其時(shí)間復(fù)雜度為O(n"),其時(shí)間復(fù)雜度與邊得數(shù)目無關(guān)，而kruskal算法的時(shí)間復(fù)雜度為 O(eloge)跟邊的數(shù)目有關(guān)，適合稀疏圖。(b>(e)(d) © © ©irK用電造地小土“山用'Krusal算法圖中先將每個(gè)頂點(diǎn)看作獨(dú)立的子圖，然后查找最小權(quán)值邊，這條邊是有限制條件的，邊得兩個(gè)頂點(diǎn)必須不在同一個(gè)圖中，如上圖，第一個(gè)圖中找到最小權(quán)值邊為（ v1, v3）,且滿 足限制條件

10、，繼續(xù)查找到邊（v4, v6）, （v2, v5）, （v3, v6）,當(dāng)查找到最后一條邊時(shí)，僅 僅只有（v2, v3）滿足限制條件，其他的如（v3, v4）, （v1, v4）都在一個(gè)子圖里面，不滿足條件，至此已經(jīng)找到最小生成樹的所有邊。a(b)(C)(d)(c)用笄法構(gòu)造最小生成對(duì)的逑器www.WuTianQixom拓?fù)渑判蛴赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判?。?duì)上圖進(jìn)行拓?fù)渑判虻慕Y(jié)果:2->8->0->3->7->1->5->6->9->4->11 ->10->125、檢索二叉排序建立

11、typedef struct node int data;struct node * Ichild;struct node * rchild;node;void Init(node *t)t = NULL;void InOrder(node * t)/ 中序遍歷輸出if(t != NULL) InOrder(t ->lchild);printf("%d ", t ->data);InOrder(t ->rchild);二叉排序刪除btree * DelNode(btree *p)if (p->lchild)btree *r = p->lchil

12、d; /r 指向其左子樹； btree *prer = p->lchild; /prer 指向其左子樹 ;while(r ->rchild != NULL)/搜索左子樹的最右邊的葉子結(jié)點(diǎn)rprer = r; r = r->rchild; p->data = r->data;if(prer != r)/若r不是p的左孩子，把r的左孩子作為r的父親的 右孩子prer->rchild = r->lchild; elsep->lchild = r->lchild; /否則結(jié)點(diǎn) p的左子樹指向 r的左子樹free(r); return p; else

13、 btree *q = p ->rchild; /q 指向其右子樹； free(p);return q;Huffman樹、編碼與解碼例.給定有18個(gè)字符組成的文本：A A D A T A R A E F R T A A F T ER各字符的哈夫曼碼。(1) 統(tǒng)計(jì)：字符A頻度1DEFT1223(2) 構(gòu)造 Huffman 樹：r ； I 2 1 23 i 37 I"W65合并1和2合并2和3© 一® ® <®©合并3和3排序，色排序2上 排序一®3住序合并7和11(3) 在左分枝標(biāo)0,右分枝標(biāo)1:luff man

14、W(4) 確定Huffman編碼:字符1ADEFTR頻度712233騙碼010101011100110111(5)譯碼: ill)N產(chǎn)一f 1 (2 JD EHuffman樹例.給定代碼序列：0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 10 文本為：A A F A R A D E T散列存儲(chǔ)6、內(nèi)排序希爾排序I初始關(guān)醺字L49 38 6576 13 27 49 56 04一精楮序結(jié)果：二例排序結(jié)果：三總排序結(jié)果:d為當(dāng)前增量void ShellPass(SeqList R int d)希爾排序中的一趟排序，for(i=d+1;i<=n ; i+) 將Rd+

15、1. n分別插入各組當(dāng)前的有序區(qū) if(Ri.key<Ri-d.key)R0=Ri;j=i-d;/R只是暫存單元，不是哨兵 do 查找Ri的插入位置Rj+d; =Rj;后移記錄j=j-d;查找前一記錄while(j>0&&R0.key<Rj.key);Rj+d=R0; 插入Ri到正確的位置上 /endif /ShellPassvoid ShellSort(SeqList R) int increment=n ; 增量初值，不妨設(shè) n>0do increment=increment/3+1 ; 求下一增量ShellPass(R increment) ; /

16、 一趟增量為 increment 的 Shell 插 入排序while(increment>1) /ShellSort直接插入排序void lnsertSort(SeqList R) 對(duì)順序表R中的記錄R1.n按遞增序進(jìn)行插入排序 int i, j;for(i=2;i<=n ; i+) 依次才f入 R2,，Rn if(Ri.key<Ri-1.key)/若Ri.key大于等于有序區(qū)中所有的keys,則Ri/應(yīng)在原有位置上R0=Ri;j=i-1; R0是哨兵，且是 Ri的副本do 從右向左在有序區(qū)R1. . i-1中查找Ri的插入位置Rj+1=Rj; /將關(guān)鍵字大于 Ri.key

17、的記錄后移 j- while(R0.key<Rj.key) ; / 當(dāng) Ri.key> Rj.key 時(shí)終止Rj+1=R0; /Ri插入到正確的位置上/endif/InsertSort選擇排序初始值：2 1 5 7 2 4 9tI IIII - Fl I/ H = 一 I 3!II ， |- TH *KJF 123 4 5678 第弟第弟第第第第void SelectSort(SeqList R)int i, j, k;for(i=1;i<n;i+)/ 做第 i 趟排序(1 & i< n-1)k=i；for(j=i+1;j<=n;j+) /在當(dāng)前無序區(qū) R

18、i.n中選key最小的記錄 Rk if(Rj.key<Rk.key)k寸k記下目前找到的最小關(guān)鍵字所在的位置if(k!=i) / 交換 Ri和 RkR0=Ri； k； Rk=R0; /R0作暫存單元 /endif /endfor /SeleetSort交換排序void BubbleSort(SeqList R) /R (l.n)是待排序的文件，采用自下向上掃描，對(duì)R做冒泡排序int i, j;Boolean exchange; 交換標(biāo)志for(i=1;i<n;i+) / 最多做 n-1 趟排序exchange=FALSE； / 本趟排序開始前，交換標(biāo)志應(yīng)為假for(j=n -1;j

19、>=i； j-) / 對(duì)當(dāng)前無序區(qū)Ri.n 自下向上掃描if(Rj+1.key<Rj.key)/ 交換記錄R0=Rj+1 ； /R0 不是哨兵，僅做暫存單元Rj+1=Rj；Rj=R0；exchange=TRUE； / 發(fā)生了交換，故將交換標(biāo)志置為真if(!exchange) / 本趟排序未發(fā)生交換，提前終止算法return ； /endfor( 外循環(huán) ) /BubbleSortvoid QuickSort(SeqList R， int low ， int high) / 對(duì) Rlow.high 快速排序int pivotpos ； / 劃分后的基準(zhǔn)記錄的位置if(low<h

20、igh)/ 僅當(dāng)區(qū)間長(zhǎng)度大于1 時(shí)才須排序pivotpos=Partition(R ， low ， high) ； / 對(duì) Rlow.high 做劃分QuickSort(R， low ， pivotpos-1)； / 對(duì)左區(qū)間遞歸排序QuickSort(R， pivotpos+1 ， high) ； / 對(duì)右區(qū)間遞歸排序 /QuickSort 歸并排序void Merge(SeqList R， int low ， int m ， int high)將兩個(gè)有序的子文件Rlow.m)和Rm+1.high歸并成一個(gè)有序的/ 子文件Rlow.highint i=low ， j=m+1 ， p=0 ；

21、/ 置初始值RecType *R1；/R1 是局部向量，若p 定義為此類型指針?biāo)俣雀霷1=(ReeType *)malloc(high -low+1)*sizeof(RecType) ；if(! R1) / 申請(qǐng)空間失敗Error("Insufficient memory available!") ；while(i<=m&&j<=high) 兩子文件非空時(shí)取其小者輸出到R1p上R1p+=(Ri.key<=Rj.key)?Ri+ ： Rj+；while(i<=m) / 若第 1 個(gè)子文件非空，則復(fù)制剩余記錄到 R1 中R1p+=Ri+

22、 ；while(j<=high) / 若第 2 個(gè)子文件非空，則復(fù)制剩余記錄到 R1 中R1p+=Rj+；for(p=0 ， i=low ； i<=high ； p+ ， i+)Ri=R1p ； / 歸并完成后將結(jié)果復(fù)制回Rlow.high /Merge、選擇題1、二叉樹的第i層至多有2A(i - 1)個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2” - 1個(gè)結(jié)點(diǎn) (根結(jié)點(diǎn)的深度為1)2、二維數(shù)組A 1020, 5.10采用行序?yàn)橹鞔娣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，且A 10, 5的存儲(chǔ)地址為1000,則A 18, 9的存儲(chǔ)地址？a.不管按行還是按列，都是順序存儲(chǔ)。按行存儲(chǔ)，每行 10-5+1

23、共6個(gè)元素。A10, 9 距離A10, 5之間相差4個(gè)元素；A18, 9與A10, 9相差8行，共8X 6=48個(gè)元素；所 以A18, 9與A10, 5相差4+48=52個(gè)元素，共 52 X 4=208個(gè)存儲(chǔ)單元；A18, 9的地址 應(yīng)該是1208。b.更一般的算法：基地址 +(行標(biāo)之差X每行元素個(gè)數(shù) +列標(biāo)之差)X元素所占存儲(chǔ)單3、n個(gè)頂點(diǎn)的連通圖最多多少邊、最少多少條邊？答：最多 n (n-1) /2,最少n-14、設(shè)一個(gè)無向圖有5頂點(diǎn)，度數(shù)分別是4,3,3,2,2,求該圖邊數(shù)？答：每條邊與兩個(gè)頂點(diǎn)相 連接，所以所有頂點(diǎn)上的度數(shù)之和就是圖中邊的兩倍，本題中共有4+3+3+2+2=14個(gè)邊的

24、端點(diǎn)，因而共有14/2=7條邊。6、建立最小堆int A0=氏12,17,30,50,20,60,65,4.49 卜建堆過程6、huffman 編碼回回四店回回四火a亙下 心 £ 1. I r| |T| r7iT TT|A.j I J %7、直接排序法過程用直接排序法將無序列49, 38, 65, 97, 76, 13, 27按照從大到小的順序排 為有序列時(shí)，每一趟將把當(dāng)前最大的放到第一位，然后例舉出前五趟就是每一趟將把當(dāng)前最大的放到第一位.即第一趟 97, 49, 38, 65, 76, 13,27第二趟97, 76, 49, 38, 65, 13, 27,第三趟97, 76, 6

25、5, 49, 38, 13, 27,第四趟97, 76, 65, 49, 38, 13, 27,第五趟97, 76, 65, 49, 38, 13, 278、四、編程題1、二叉樹：二叉樹的建立：#include <stdio.h>#define ElemType char節(jié)點(diǎn)聲明，數(shù)據(jù)域、左孩子指針、右孩子指針typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/ 先序建立二叉樹BiTree CreateBiTree()char ch;BiTree T;scanf("

26、%c",&ch);if(ch='#')T=NULL;elseT = (BiTree)malloc(sizeof(BiTNode);T->data = ch;T->lchild = CreateBiTree();T->rchild = CreateBiTree();return T;/ 返回根節(jié)點(diǎn)/ 先序遍歷二叉樹void PreOrderTraverse(BiTree T)if(T)printf("%c",T ->data);PreOrderTraverse(T->lchild);PreOrderTravers

27、e(T->rchild);/ 中序遍歷void InOrderTraverse(BiTree T)if(T)PreOrderTraverse(T->lchild);printf("%c",T ->data);PreOrderTraverse(T->rchild);/ 后序遍歷void PostOrderTraverse(BiTree T)if(T)PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild); printf("%c",T ->data);void

28、main()BiTree T;T = CreateBiTree();/ 建立PreOrderTraverse(T);/ 輸出 getch(); 在二叉樹中插入結(jié)點(diǎn)x ，找中序首點(diǎn)(順著左支一直走)、尾點(diǎn)(順右)/ 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、 右兒子。 將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。 /typedef struct nodeint data;struct node * lchild;struct node * rchild;node;node * Insert(node *t , in

29、t key)if(t = NULL)node * p;p = (node *)malloc(sizeof(node);p->data = key;p->lchild = NULL;p->rchild = NULL;t = p;elseif(key < t->data)t->lchild = Insert(t ->lchild, key);elset->rchild = Insert(t->rchild, key);return t; /important!typedef struct Nodeint data;struct Node *lc

30、,*rc;node,*Link;void insert( Link *L,int n )if( *L = NULL )( *L ) = new node;/ 若找到插入位置，則新申請(qǐng)節(jié)點(diǎn)( *L ) -> lc = ( *L ) -> rc = NULL;( *L ) -> data = n;elseif( n = ( *L ) -> data )/若 n 與當(dāng)前節(jié)點(diǎn)的值相等，則不需插入了 return ;else if( n < ( *L ) -> data )/ 若 n 比當(dāng)前節(jié)點(diǎn)的值小，則往當(dāng)前節(jié)點(diǎn)的左子樹插insert( &( *L ) -&

31、gt; lc,n );else/ 若 n 比當(dāng)前節(jié)點(diǎn)的值大，則往當(dāng)前節(jié)點(diǎn)的右子樹插insert( &( *L ) -> rc,n );中序遍歷：typedef struct BiTNode/* 結(jié)點(diǎn)結(jié)構(gòu) */int data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Inorder(BiTree T) /* 中序遍歷二叉樹*/if (T) Inorder(T ->lchild); /* 遍歷左子樹*/ printf("%d ",T ->data);/* 訪問結(jié)點(diǎn) */ Inorder(T

32、 ->rchild);/* 遍歷右子樹*/當(dāng)調(diào)用該子函數(shù)時(shí)：加入傳的就是根節(jié)點(diǎn)，他將不斷的遞歸一直到最左的一個(gè)葉子節(jié)點(diǎn)，就是不斷重復(fù)T 位最左葉子節(jié)點(diǎn)是那么第一句再遞歸式就失敗了，所有退回上一層輸出，緊接著就執(zhí)行開始遞歸以此類推在遞歸第三句時(shí)候也是嚴(yán)格按著1,2,3 這個(gè)順序執(zhí)行。 求一度結(jié)點(diǎn)，葉子結(jié)點(diǎn)int count=0; void preOrder(TTree:tree) if (tree!=NULL) count+;/ 先根訪問，且計(jì)數(shù)/ 這里顯示 tree 的數(shù)據(jù) if (tree->Left!=NULL) preOrder(tree ->Left);if(tree

33、 ->Right!=NULL) preOrder(tree ->Right); main() count=0;preOrder(tree);/ 顯示 count2、 檢索： 二分法搜索(遞歸與非遞歸)必背！ ！ ！ 遞歸：void Search(int p,int low,int height,int key) int middle=(low+height)/2; if(low>height) printf(" 沒有該數(shù)！ "); return; if(pmiddle=key)printf("%dn",middle); return;else if(pmiddle>key) Search(p,low,middle -1,key); else if(pmiddle<key)Search(p,middle+1,height,key); int main()int p5=1,2,3,4,