復習 數(shù) 據(jù) 結(jié) 構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)第1章 緒論重點歸納1、（1）數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中的計算機操作對象以及它們之間的關(guān)系和操作的學科。（2）數(shù)據(jù)結(jié)構(gòu)是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。（3）數(shù)據(jù)結(jié)構(gòu)是一個二元組Data_Structure （D，R），其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。2、數(shù)據(jù)是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。抽象數(shù)據(jù)類型是指一個數(shù)學模型以及定

2、義在該模型上的一組操作。它實際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義，定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。抽象數(shù)據(jù)類型用三元組（D，S，P）描述.3、邏輯結(jié)構(gòu)是指數(shù)據(jù)之間的相互關(guān)系。通常分為四類結(jié)構(gòu)：（1）集合（2）線性結(jié)構(gòu)（3）樹型結(jié)構(gòu)（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 4、存儲結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，又稱為數(shù)據(jù)的物理結(jié)構(gòu)。通常由四種基本的存儲方法實現(xiàn)：（1）順序存儲方式（2）鏈式存儲方式（3）索引存儲方式（4）散列存儲方式5、算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。具有下列特性：有窮性確定性可行性輸入輸出。評價算法：正確可讀健壯高效。6、時間

3、復雜度：以基本運算的原操作重復執(zhí)行的次數(shù)作為算法的時間度量。一般情況下，算法中原操作重復執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)T(n)。常見的漸進時間復雜度有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n) O(n!) O(nn)注意：有的情況下，算法中基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。7、算法的存儲空間度量：若輸入數(shù)據(jù)所占空間只取決與問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。原地工作：若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。8、（1）for (int i=1; i<=n; i+) for (int j

4、=1; j<=i; j+)語句頻度是n (n+1)/2（2）for( i=1; i<=n; i+) for (j=1; j<=i; j+) for (k=1; k<=j; k+)語句頻度是n (n+1)(n+2)/6（3）循環(huán)條件是 (y+1)2n, 即 y-1,而 y 的初始值是0，則語句頻度應為。習題：1. 以下屬于邏輯結(jié)構(gòu)的是（ ）。A順序表 B. 散列表 C. 有序表 D. 單鏈表第2章 線性表重點歸納1、線性表是具有相同數(shù)據(jù)類型的n(n0)個數(shù)據(jù)元素的有限序列，是最簡單、最基本、也是最常用的一種線性結(jié)構(gòu)，2、順序表上基本運算的實現(xiàn)（1）順序表具有按數(shù)據(jù)元素的序

5、號隨機存取的特點，時間復雜度為O(1)。（2）按值x查找：主要運算是比較，比較的次數(shù)與值x在表中的位置有關(guān)，也與表長有關(guān)，平均比較次數(shù)為（n+1）/2，時間復雜度為O(n)。（3）插入運算：在第i個位置上插入x，從an到ai都要向下移動一個位置，共移動ni1個元素。等概率情況下，平均移動數(shù)據(jù)元素的次數(shù)： 說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素，時間復雜度為O(n)。（4）刪除運算：刪除第i個元素，從ai+1到an都要向上移動一個位置，共移動 n-i 個元素。等概率情況下，平均移動數(shù)據(jù)元素的次數(shù)： 說明：順序表上作刪除運算時大約需要移動表中一半的元素，時間復雜度為O(n)。3、單鏈表

6、上基本運算的實現(xiàn)（1）建立帶頭結(jié)點的單鏈表頭插法：讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的。LinkList Creat_LinkList1( ) LinkList L=(LNode *)malloc(sizeof(LNode); L->next=NULL； /*空表*/LNode *s;int x; /*設(shè)數(shù)據(jù)元素的類型為int*/scanf(%d,&x);while (x!=flag) s=malloc(sizeof(LNode);s->data=x;s->next=L->next; L->next=s; scanf (%d,&x)

7、; return L;尾插法：讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是一致的。LinkList Creat_LinkList2( ) LinkList L=(LNode *)malloc(sizeof(LNode); L->next=NULL； /*空表*/LNode *s,*r=L;int x; /*設(shè)數(shù)據(jù)元素的類型為int*/scanf(%d,&x);while (x!=flag) s=malloc(sizeof(LNode); s->data=x;r->next=s; r=s; /*r指向新的尾結(jié)點*/ scanf(%d,&x);r->nex

8、t=NULL; return L;（2）求表長設(shè)L是帶頭結(jié)點的單鏈表(線性表的長度不包括頭結(jié)點)。int Length_LinkList1 (LinkList L) LNode * p=L; /*p指向頭結(jié)點*/int j=0;while (p->next) p=p->next; j+ /*p所指的是第 j 個結(jié)點*/return j;設(shè)L是不帶頭結(jié)點的單鏈表。int Length_LinkList2 (LinkList L) LNode * p=L;int j;if (p=NULL) return 0; /*空表的情況*/j=1; /*在非空表的情況下，p所指的是第一個結(jié)點*/w

9、hile (p->next ) p=p->next; j+ return j;兩個算法的時間復雜度均為O(n)。不帶頭結(jié)點的單鏈表空表情況要單獨處理，而帶上頭結(jié)點之后則不用了。在以后的算法中不加說明則認為單鏈表是帶頭結(jié)點的。（3）查找按序號查找 Get_Linklist(L,i)Lnode * Get_LinkList(LinkList L, int i); /*在單鏈表L中查找第i個元素結(jié)點*/ LNode * p=L;int j=0;while (p->next !=NULL && j<i ) p=p->next; j+; if (j=i) r

10、eturn p;else return NULL; 按值查找即定位 Locate_LinkList(L,x)Lnode * Locate_LinkList( LinkList L, ElemType x) /*在單鏈表L中查找值為x的結(jié)點*/ LNode * p=L->next;while ( p!=NULL && p->data != x)p=p->next; return p;以上兩個算法的時間復雜度均為O(n)。（4）插入圖1-2-1 在*p之后插入*s p s×后插結(jié)點：設(shè)p指向單鏈表中某結(jié)點，s指向待插入的值為x的新結(jié)點，將*s插入到*p的

11、后面，插入過程如圖1-2-1。圖1-2-2 在*p之前插入*s s×pq操作如下： s->next=p->next;p->next=s;注意：兩個指針的操作順序不能交換。后插操作的時間復雜度為O(1)。前插結(jié)點：設(shè)指向鏈表中某結(jié)點，指向待插入的值為x的新結(jié)點，將*s插入到*p的前面，插入過程如下圖1-2-2，與后插不同的是：首先要找到*p的前驅(qū)*q，然后再完成在*q之后插入*s，設(shè)單鏈表頭指針為L。操作如下：q=L;while (q->next!=p) q=q->next; /*找*p的直接前驅(qū)*/s->next=q->next; q->

12、;next=s;前插操作因為要找*p的前驅(qū)，時間性能為O(n)。其實前插操作可以用后插操作來實現(xiàn)，即仍然可以將 *s 插入到 *p 的后面，然后將->data與s->data交換即可，這樣即滿足了邏輯關(guān)系，也能使得時間復雜度為O(1)。（5）刪除刪除p結(jié)點：設(shè)p指向單鏈表中某結(jié)點，刪除*p。操作過程如下圖1-2-3。要實現(xiàn)對結(jié)點*p的刪除，首先要找到*p的前驅(qū)結(jié)點*q，然后完成指針的操作即可。圖1-2-3 刪除*p pq×操作如下：q=L;while (q->next!=p) q=q->next; /*找*p的直接前驅(qū)*/q->next=p->ne

13、xt;free(p);顯然找*p前驅(qū)的時間復雜度為O(n)。刪除p結(jié)點的后繼結(jié)點：若要刪除*p的后繼結(jié)點(假設(shè)存在)，則可以直接完成：操作如下：s=p->next;p->next=s->next;free(s);該操作的時間復雜度為O(1)。4、循環(huán)鏈表：在循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已，沒有其它較大的變化。對于單鏈表只能從頭結(jié)點開始遍歷整個鏈表，而對于單循環(huán)鏈表則可以從表中任意結(jié)點開始遍歷整個鏈表。不僅如此，有時對鏈表常做的操作是在表尾、表頭進行，此時可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結(jié)點的指針

14、R來標識，可以使得操作效率得以提高。5、雙向鏈表圖1-2-5 雙向鏈表中刪除結(jié)點p××（1）插入：設(shè)p指向雙向鏈表中某結(jié)點，s指向待插入的值為x的新結(jié)點，將*s插入到*p的前面，插入過程如下圖1-2-4。圖1-2-4 雙向鏈表中的結(jié)點插入p××操作如下：s->prior=p->prior; p->prior->next=s;s->next=p; p->prior=s;指針操作的順序不是唯一的，但也不是任意的，操作必須要放到操作的前面完成，否則*p的前驅(qū)結(jié)點的指針就丟掉了。只要把每條指針操作的涵義搞清楚，就不難理解了。（

15、2）刪除：設(shè)p指向雙向鏈表中某結(jié)點，刪除*p。操作過程如下圖1-2-5。操作如下：p->prior->next=p->next;p->next->prior=p->prior; free(p); 6、靜態(tài)鏈表靜態(tài)鏈表借助數(shù)組來描述線性表的鏈式存儲結(jié)構(gòu)，這里的指針是結(jié)點的相對地址(數(shù)組的下標)。有關(guān)基于靜態(tài)鏈表上的線性表的操作基本與動態(tài)鏈表相同，除了一些描述方法有些區(qū)別外，算法思路是相同的。習題：1. 表長為n的順序存儲的線性表，當在任何位置上刪除一個元素的概率相等時，刪除一個元素所需移動元素的平均個數(shù)為（ ）。An B. n/2 C. (n-1)/2 D.

16、(n+1)/22. 在一個長度為n的順序存儲線性表中，刪除第i個元素(1in+1)時，需要從前向后依次前移（ ）個元素。A. n-i B. n-i+1 C. n-i-1 D. i3. 設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為TYPEDEF STRUCT NODE /鏈表結(jié)點定義ELEMTYPE DATA; /數(shù)據(jù)STRUCT NODE * NEXT; /結(jié)點后繼指針 LISTNODE;已知指針P所指結(jié)點不是尾結(jié)點，若在*P之后插入結(jié)點*S，則應執(zhí)行下列哪一個操作（ ）。A S->NEXT = P; P->NEXT = S; B S->NEXT = P->NEXT; P->NEXT

17、= S;C S->NEXT = P->NEXT; P = S; D P->NEXT = S; S->NEXT = P;4. 在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（ ）。A. HL = p; p->next = HL; B. p->next = HL; HL = p;C. p->next = HL; p = HL; D. p->next = HL->next; HL->next = p;5. 非空的循環(huán)單鏈表FIRST的尾結(jié)點（由P所指向）滿足：（ ）AP->NEXT = NULL; BP = NULL

18、; CP->NEXT = FIRST; DP = FIRST;第3章 棧、隊列和數(shù)組重點歸納1、棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。棧又稱為后進先出的線性表，隊列又稱為先進先出的線性表。線性表棧隊列Insert(L, i, x)1in+1Insert(S, n+1, x)Insert(Q, n+1, x)Delete(L, i) 1inDelete(S, n)Delete(Q, 1)2、順序棧形式描述：靜態(tài)分配：#define STACKSIZE 100typedef struct SElemType elemSTACKSIZE; int top; SqStack;這

19、里注意，非空棧時top始終在棧頂元素的位置。動態(tài)分配：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct SElemType *base;SElemType *top;int stacksize; SqStack;這里注意，非空棧時top始終在棧頂元素的下一個位置。順序棧上基本操作的實現(xiàn)（1）入棧：若棧不滿，則將 e 插入棧頂靜態(tài)分配：Status Push (SqStack &S, SElemType e)if(S.top=STACKSIZE-1) return ERROR;/*棧滿不能入棧*/else

20、 S.elem+S.top=e;/*top始終在棧頂元素的位置*/return OK;動態(tài)分配：Status Push (SqStack &S, SElemType e) if (S.top-S.base>=S.stacksize) /*棧滿，追加存儲空間*/ *S.top+ = e; /*top始終在棧頂元素的下一個位置*/ return OK;（2）出棧：若棧不空，則刪除S的棧頂元素，用 e 返回其值，并返回OK，否則返回ERROR。靜態(tài)分配：Status Pop(Sqstack &s, SElemType &e) if(S.top=-1) return ER

21、ROR; e= S.elemS.top- -; return OK; 動態(tài)分配：Status Pop (SqStack &S, SElemType &e) if (S.top=S.base) return ERROR; e = *-S.top; return OK;3、鏈棧：因為棧中的主要運算是在棧頂插入、刪除，顯然在鏈表的頭部做棧頂是最方便的，而且沒有必要象單鏈表那樣為了運算方便附加一個頭結(jié)點。鏈棧上基本操作的實現(xiàn)（1）入棧：Status Push（LinkStack &S, SElemType e） StackNode *q; q=（StackNode *）mall

22、oc（sizeof（StackNode）; q->data=e; q->next=S; S=q;return OK; （2）出棧Status Pop (LinkStack &S, SElemType &e) StackNode *p;if （S= =NULL） return ERROR;else e = S->data;p = S; S = S->next;free (p);return OK; 4、鏈隊列上基本操作的實現(xiàn)（1）入隊：插入元素e為Q的新的隊尾元素Status EnQueue (LinkQueue &Q, QElemType e)

23、QNode *p;p = （QNode *）malloc（sizeof（QNode）;p->data = e; p->next = NULL;Q.rear->next = p; Q.rear = p; return OK;（2）出隊：若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK；否則返回ERROR。Status DeQueue (LinkQueue &Q, QElemType &e) if (Q.front = Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front-&

24、gt;next = p->next; if(Q.rear=p) Q.rear= Q.front; free (p);return OK;5、順序隊列：設(shè)隊頭指針指向隊頭元素前面一個位置，隊尾指針指向隊尾元素（這樣的設(shè)置是為了某些運算的方便，并不是唯一的方法）。（1）入隊： sq->data+sq->rear=x; （2）出隊： x=sq->data+sq->front;6、循環(huán)隊列上基本操作的實現(xiàn)（1）入隊：Status EnQueue (SqQueue &Q, QElemType e) if(Q.rear+1)%MAXQSIZE = Q.front) r

25、eturn ERROR; Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;（2）出隊：Status DeQueue (SqQueue &Q, QElemType &e) if (Q.front = = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;（3）循環(huán)隊列元素個數(shù)：(Q.rear-Q.front+MAXQSIZE) %MAXQSIZE7、數(shù)組：一般采用順序存儲，是一個隨機存取結(jié)構(gòu)

26、。二維數(shù)組按行優(yōu)先尋址計算方法，每個數(shù)組元素占據(jù)d個地址單元。設(shè)數(shù)組的基址為LOC(a11)：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*d設(shè)數(shù)組的基址為LOC(a00)：LOC(aij)=LOC(a00)+( i*n+j )*d二維數(shù)組按列優(yōu)先尋址計算方法。設(shè)數(shù)組的基址為LOC(a11)：LOC(aij)=LOC(a11)+(j-1)*n+i-1)*d設(shè)數(shù)組的基址為LOC(a00)：LOC(aij)=LOC(a00)+( j*n+i )*d8、特殊矩陣的壓縮存儲（假設(shè)以行序為主序）（1）對稱矩陣：將對稱矩陣A壓縮存儲到SAn(n+1)/2中，aij的下標i、j與在SA中的對

27、應元素的下標k的關(guān)系。（2）三角矩陣與對稱矩陣類似，不同之處在于存完下（上）三角中的元素之后，接著存儲對角線上（下）方的常量，因為是同一個常數(shù)，所以存一個即可。將三角矩陣A壓縮存儲到SAn(n+1)/2+1中，aij的下標i、j與在SA中的對應元素的下標k的關(guān)系。（3）三對角矩陣將三對角矩陣A壓縮存儲到SA3n-2中，aij的下標i、j與在SA中的對應元素的下標k的關(guān)系。習題：選擇題：1. 若已知一個棧的入棧序列是1,2,3,.n，其輸出序列為p1,p2,p3,.pn，若p1=n，則pi為（ ）A. i B. n-i C. n-i+1 D.不確定2. 若一個棧的輸入序列為1，2，3 .n，輸出

28、序列的第一個元素是i，則第j個輸出元素是（ ）Ai-j-1 B. i-j C. j-i+1 D. 不確定3. 棧在（ ）中應用。A. 遞歸調(diào)用 B. 子程序調(diào)用 C. 表達式求值 D. A，B，C4. 設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B. 隊列 C. 線性表的鏈式存儲結(jié)構(gòu) D. 棧5. 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應該是一個（ ）結(jié)構(gòu)。A. 棧 B. 隊列C. 數(shù)組 D. 線性表6. 向一個帶頭結(jié)點HS的鏈

29、棧中插入一個s所指結(jié)點時，則執(zhí)行（ ）A.HS->next = s; B. s->next = HS->next; HS->next = s ;C.s->next = HS ; HS = s ; D.s->next = HS ; HS = HS->next;7. 一個循環(huán)隊列Q最多可存儲m個元素，已知其頭尾指針分別是front和rear，則判定該循環(huán)隊列為滿的條件是（ ）A.Q.rear - Q.front = m B.Q.rear != Q.frontC.Q.front =( Q.rear +1)%mD.Q.front = Q.rear %m +18

30、. 循環(huán)隊列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別為front和rear，則當前元素個數(shù)為（ ）。A(rear-front+m) mod m Brear-front+1 Crear-front-1 Drear-front9. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( ) A. 1和5 B. 2和4 C. 4和2 D. 5和110. 二維數(shù)組A的每個元素是由6個字符組成的串，其行下標i=0,1,8,列下標j=1,2,10。若A按行先存儲，元素A8,5的起始地址與當

31、A按列先存儲時的元素（ ）的起始地址相同。設(shè)每個字符占一個字節(jié)。A. A8,5 B. A3,10 C. A5,8 D. A0,911. 設(shè)n階方陣是一個上三角矩陣，則需存儲的元素個數(shù)為（ ）An Bn*n Cn*n/2 Dn(n+1)/2 12. 設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85（即該元素下標i=85）的地址為（ ）。A. 13 B. 33 C. 18 D. 4013. 若對n階對稱矩陣A1.n，1.n以行序為主序方式下將其下三角的元素（包括主對角線上的所有元素）依次存放于一維數(shù)組B1.n(n+1)

32、/2中，則在B中確定aij (i<j)的位置k的關(guān)系為（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i第4章 樹和二叉樹重點歸納1、二叉樹：是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。完全二叉樹：一棵深度為k的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進行編號，如果編號為i（1in）的結(jié)點與滿二叉樹中編號為i的結(jié)點在二

33、叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點是：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部。2、二叉樹的性質(zhì)：性質(zhì)1：一棵非空二叉樹的第i層上最多有2i-1個結(jié)點（i1）。性質(zhì)2：一棵深度為k的二叉樹中，最多具有2k1個結(jié)點。性質(zhì)3：對于一棵非空的二叉樹，如果葉子結(jié)點數(shù)為n0，度數(shù)為2的結(jié)點數(shù)為n2，則有：n0n21 性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度k為+1。性質(zhì)5：對于具有n個結(jié)點的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序編號，則對于任意的序號為i的結(jié)點，有：（1）如果i1，則序號i的結(jié)點的雙親結(jié)點的序號為；

34、如果i1，則序號為i的結(jié)點是根結(jié)點，無雙親結(jié)點。（2）如果2in，則序號為i的結(jié)點的左孩子結(jié)點的序號為2i；如果2in，則序號為i的結(jié)點無左孩子。（3）如果2i1n，則序號為i的結(jié)點的右孩子結(jié)點的序號為2i1；如果2i1n，則序號為i的結(jié)點無右孩子。此外，若對二叉樹的根結(jié)點從0開始編號，則相應的i號結(jié)點的雙親結(jié)點的編號為，左孩子的編號為2i1，右孩子的編號為2i2。3、二叉樹的存儲結(jié)構(gòu)二叉鏈表形式描述：typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /*左右孩子指針*/ BiTNode,*BiTree

35、;盡管在二叉鏈表中無法由結(jié)點直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，對于一般情況的二叉樹，甚至比順序存儲結(jié)構(gòu)還節(jié)省空間。后面所涉及到的二叉樹的鏈式存儲結(jié)構(gòu)不加特別說明的都是指二叉鏈表結(jié)構(gòu)。4、遍歷二叉樹（必背的七個算法） 遍歷二叉樹是以一定規(guī)則將二叉樹中結(jié)點排列成一個線性序列，實質(zhì)是對一個非線性結(jié)構(gòu)進行線性化操作。（1）前序遍歷的遞歸實現(xiàn)void PreOrder（BiTree bt）/*前序遍歷二叉樹bt*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/Visit（bt->data）; /*訪問結(jié)點的數(shù)據(jù)域*/ PreOrder（bt->lchi

36、ld）; /*前序遞歸遍歷bt的左子樹*/PreOrder（bt->rchild）; /*前序遞歸遍歷bt的右子樹*/ （2）中序遍歷的遞歸實現(xiàn)void InOrder（BiTree bt） /*中序遍歷二叉樹bt*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/InOrder（bt->lchild）; /*中序遞歸遍歷bt的左子樹*/Visit（bt->data）; /*訪問結(jié)點的數(shù)據(jù)域*/InOrder（bt->rchild）; /*中序遞歸遍歷bt的右子樹*/ （3）后序遍歷的遞歸實現(xiàn)void PostOrder（BiTree bt）/*后

37、序遍歷二叉樹bt*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/PostOrder（bt->lchild）; /*后序遞歸遍歷bt的左子樹*/PostOrder（bt->rchild）; /*后序遞歸遍歷bt的右子樹*/ Visit（bt->data）; /*訪問結(jié)點的數(shù)據(jù)域*/（4）層序遍歷的實現(xiàn)一維數(shù)組QueueMAX_TREE_SIZE用以實現(xiàn)隊列，變量front和rear分別表示當前對隊首元素和隊尾元素在數(shù)組中的位置。void LevelOrder（BiTree bt） /*層序遍歷二叉樹bt*/BiTree QueueMAX_TREE_SI

38、ZE; int front,rear; if (bt=NULL) return; front=-1; rear=0; queuerear=bt;while(front!=rear) Visit(queue+front->data); /*訪問隊首結(jié)點數(shù)據(jù)域*/ if (queuefront->lchild!=NULL) /*將隊首結(jié)點的左孩子結(jié)點入隊列*/ queue+rear=queuefront->lchild; if (queuefront->rchild!=NULL) /*將隊首結(jié)點的右孩子結(jié)點入隊列*/queue+rear=queuefront->rch

39、ild; （5）前序遍歷的非遞歸實現(xiàn)二叉樹以二叉鏈表存放，一維數(shù)組stackMAX_TREE_SIZE用以實現(xiàn)棧，變量top用來表示當前棧頂?shù)奈恢?。void NRPreOrder（BiTree bt）/*非遞歸先序遍歷二叉樹*/ BiTree stackMAX_TREE_SIZE,p; int top; if (bt=NULL) return;top=0;p=bt;while(!(p=NULL&&top=0) while(p!=NULL) Visit(p->data); /*訪問結(jié)點的數(shù)據(jù)域*/ if(top MAX_TREE_SIZE-1)/*將當前指針p壓棧*/ st

40、acktop+=p; else printf(“棧溢出”)； return； p=p->lchild； /*指針指向p的左孩子結(jié)點*/ if (top<=0) return; /*?？諘r結(jié)束*/ else p=stack- -top;/*從棧中彈出棧頂元素*/p=p->rchild; /*指針指向p的右孩子結(jié)點*/（6）中序遍歷的非遞歸實現(xiàn)只需將先序遍歷的非遞歸算法中的Visit(p->data)移到p=stack- -top和p=p->rchild之間即可。（7）后序遍歷的非遞歸實現(xiàn)后序遍歷與先序遍歷和中序遍歷不同，在后序遍歷過程中，結(jié)點在第一次出棧后，還需再次

41、入棧，也就是說，結(jié)點要入兩次棧，出兩次棧，而訪問結(jié)點是在第二次出棧時訪問。因此，為了區(qū)別同一個結(jié)點指針的兩次出棧，設(shè)置一標志flag，令：1 第一次出棧，結(jié)點不能訪問2 第二次出棧，結(jié)點可以訪問 flag當結(jié)點指針進、出棧時，其標志flag也同時進、出棧。因此，可將棧中元素的數(shù)據(jù)類型定義為指針和標志flag合并的結(jié)構(gòu)體類型。定義如下：typedef struct BiTree link; int flag;stacktype;后序遍歷二叉樹的非遞歸算法如下。在算法中，一維數(shù)組stackMAX_TREE_SIZE用于實現(xiàn)棧的結(jié)構(gòu)，指針變量p指向當前要處理的結(jié)點，整型變量top用來表示當前棧頂?shù)奈?/p>

42、置，整型變量sign為結(jié)點p的標志量。void NRPostOrder(BiTree bt) /*非遞歸后序遍歷二叉樹bt*/ stacktype stackMAX_TREE_SIZE;BiTree p;int top,sign;if (bt=NULL) return;top=-1; /*棧頂位置初始化*/p=bt;while (!(p=NULL && top=-1) if (p!=NULL) /*結(jié)點第一次進棧*/ stack+top.link=p; stacktop.flag=1; p=p->lchild; /*找該結(jié)點的左孩子*/ else p=stacktop.l

43、ink; sign=stacktop- -.flag; if (sign=1) /*結(jié)點第二次進棧*/ stack+top.link=p; stacktop.flag=2; /*標記第二次出棧*/ p=p->rchild; else Visit(p->data); /*訪問該結(jié)點數(shù)據(jù)域值*/ p=NULL; 5、建立二叉鏈表方式存儲的二叉樹void CreateBinTree(BinTree *bt) /*以加入結(jié)點的前序序列輸入，構(gòu)造二叉鏈表*/char ch; scanf("%c",&ch); if (ch='0') *bt=NULL

44、; /*讀入0時，將相應結(jié)點置空*/ else *bt=(BinTNode *)malloc(sizeof(BinTNode); /*生成結(jié)點空間*/ (*bt)->data=ch; CreateBinTree(&(*bt)->lchild); /*構(gòu)造左子樹*/ CreateBinTree(&(*bt)->rchild); /*構(gòu)造右子樹*/6、線索二叉樹（1）按照某種遍歷方式對二叉樹進行遍歷，可把二叉樹中所有結(jié)點排列為一個線性序列，二叉樹中每個結(jié)點在這個序列中的直接前驅(qū)結(jié)點和直接后繼結(jié)點是什么，二叉樹的存儲結(jié)構(gòu)中并沒有反映出來，只能在對二叉樹遍歷的動態(tài)過程

45、中得到這些信息。為了保留結(jié)點在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息，可以利用具有n個結(jié)點的二叉樹中的葉子結(jié)點和一度結(jié)點的n1個空指針域來指示，這些指向直接前驅(qū)結(jié)點和指向直接后繼結(jié)點的指針被稱為線索，加了線索的二叉樹稱為線索二叉樹。線索二叉樹將為二叉樹的遍歷提供許多遍歷，遍歷時可不需要棧，也不需要遞歸了。（2）線索二叉樹的存儲表示的描述：typedef enum PointerTag Link,Thread;typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild;PointerTag Ltag,Rt

46、ag;BiThrNode, *BiThrTree;（3）建立一棵中序線索二叉樹：實質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，Visit操作是檢查當前結(jié)點的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點或后繼結(jié)點的線索。為實現(xiàn)這一過程，設(shè)指針pre始終指向剛剛訪問過的結(jié)點，即若指針p指向當前結(jié)點，則pre指向它的前驅(qū)，以便增設(shè)線索。int InOrderThr(BiThrTree &head,BiThrTree T) /*中序遍歷二叉樹T，將其中序線索化，head指向頭結(jié)點。*/if (!(head=(BiThrNode *)malloc(sizeof(BiThrNode) retu

47、rn 0;head->Ltag=0; head->Rtag=1; /*建立頭結(jié)點*/head->rchild=head; /*右指針回指*/ if (!T) head->lchild =head; /*若二叉樹為空，則左指針回指*/else head->lchild=T; pre= head; InThreading(T); /*中序遍歷進行中序線索化*/ pre->rchild=head; pre->rtag=1; /*最后一個結(jié)點線索化*/ head->rchild=pre; return 1;void InTreading(BiThrTre

48、e p) if (p) InThreading(p->lchild); /*左子樹線索化*/if (!p->lchild) /*前驅(qū)線索*/ p->ltag=1; p->lchild=pre;if (!pre->rchild) /*后繼線索*/ pre->rtag=1; pre->rchild=p; pre=p;InThreading(p->rchild); /*右子樹線索化*/ 7、樹形結(jié)構(gòu)： 在樹形結(jié)構(gòu)中，結(jié)點間具有分支層次關(guān)系，每一層上的結(jié)點只能和上一層中的至多一個結(jié)點相關(guān)，但可能和下一層的多個結(jié)點相關(guān)。一棵樹采用孩子兄弟表示法所建立的存儲

49、結(jié)構(gòu)與它所對應的二叉樹的二叉鏈表存儲結(jié)構(gòu)是完全相同的。8、樹、森林與二叉樹的轉(zhuǎn)換設(shè)森林F = (T1，T2，Tn);T1 = ( root，t11, t12, , t1m);二叉樹B =( LBT, Node(root), RBT );（1）森林轉(zhuǎn)換為二叉樹的方法：若 F = ，則 B = ;否則，由 ROOT(T1) 對應得到Node(root);由 (t11, t12, , t1m )對應得到 LBT;由 (T2，T3，Tn )對應得到 RBT。（2）二叉樹轉(zhuǎn)換為樹和森林：樹和森林都可以轉(zhuǎn)換為二叉樹，二者不同的是樹轉(zhuǎn)換成的二叉樹，其根結(jié)點無右分支，而森林轉(zhuǎn)換后的二叉樹，其根結(jié)點有右分支。這

50、一轉(zhuǎn)換過程是可逆的，即可以依據(jù)二叉樹的根結(jié)點有無右分支，將一棵二叉樹還原為樹或森林。若 B = , 則 F = ;否則，由 Node(root) 對應得到ROOT(T1);由 LBT對應得到(t11, t12, , t1m );由 RBT對應得到(T2，T3，Tn )。由此，樹和森林的各種操作均可與二叉樹的各種操作相對應。應當注意的是，和樹對應的二叉樹，其左、右子樹的概念已改變?yōu)椋?左是孩子，右是兄弟。9、樹和森林的遍歷：可采用對應二叉樹的遍歷算法來實現(xiàn)的樹森林二叉樹先根遍歷前序遍歷前序遍歷后根遍歷中序遍歷中序遍歷10、哈夫曼樹：最小帶權(quán)路徑長度的二叉樹（1）構(gòu)造哈夫曼樹的基本思想是：常見錯誤

51、：在合并中不是選取根結(jié)點權(quán)值最小的兩棵二叉樹（包括已合并的和未合并的），而是選取未合并的根結(jié)點權(quán)值最小的一棵二叉樹與已經(jīng)合并的二叉樹合并。哈夫曼樹的特點：具有n個葉子結(jié)點的哈夫曼樹共有2n1個結(jié)點。（2）哈夫曼編碼：求哈夫曼編碼，實質(zhì)上就是在已建立的哈夫曼樹中，從葉結(jié)點開始，沿結(jié)點的雙親鏈域回退到根結(jié)點，每回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結(jié)點到相應葉結(jié)點所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。利用哈夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。難點釋疑遍歷二叉樹的應用（1）二叉樹遞歸算法的設(shè)計技巧對于二叉樹，一般遞歸模型如下：f(b)=c 當b=NULL時f(b)=g(f(b->lchild),f(b->lchild),c) 其他情況其中，f()為遞歸函數(shù)，g為非遞歸函數(shù)，c為常量。（2）統(tǒng)計一棵給定二叉樹中的所有葉子結(jié)點數(shù)解析：遞歸模型如下：f(b)=0 若b=NULLf(b)=1 若b