數據結構知識點整理(清華大學出版社)

1、第一章緒論1. 數據結構：主要研究非數值計算問題中計算機的操作對象有哪些結構(邏輯結構)、這些結構在計算機中的表示及其操作的定義和實現問題。2. 邏輯結構：不考慮實現，僅看問題域中數據元素根據相互間的邏輯關系形成的結構稱為數據結構的邏輯結構。通常說的數據結構即此義。分類：如書目表根據一對一相鄰關系形成線性結構盤格局間根據下棋規(guī)則(一對多)形成一個樹形數據結構，城市間據通路(多對多)形成圖狀結構，此外還有集合結構(除同屬一個集合外，無其它關聯)，共四類3. 數據結構(數據元素及關系/結構)在計算機中的表示或者說映像稱為該數據結構的物理結構或存儲結構。4. 順序存儲結構：關系采取順序映像表示，即借

2、助元素在存儲器中的位置上的”相鄰”關系隱式表示數據元素間具有關系。此時物理結構對應一個數組。優(yōu)點：可根據起始地址隨機訪問各元素。缺點：需事先分配一足夠大空間，且插入刪除結點需移動大量數據。鏈式存儲結構：關系采取鏈式映像表示，即借助附加信息指針顯式表示元素間的關系，對應一個鏈表。優(yōu)點是 更有效利用空間、插入或者刪除結點快，但要順序訪問各元素。5. 度量指標：算法運行時間主要取決于基本操作的執(zhí)行次數(頻度)，執(zhí)行次數通常隨問題規(guī)模擴大而增加，增加越快意味著算法隨問題規(guī)模的擴大，運行時間增長的也快，從而該種算法效果較差；增長越慢算法越好，故可用基本操作的頻度隨問題規(guī)模的增長率反映算法的效率。6. 時

3、間復雜度：頻度函數的增長率基本與函數中“關鍵項”(去掉低次項和常數項)的增長率相同，故可用“關鍵項”反映算法效率。假設關鍵項為f(n),用T(n)=O(f(n)表示算法時間增長率與f(n)增長率同階。稱O(f(n)為算法的漸近時間復雜度，簡稱時間復雜度。f(n)的增長率為f(n +1)/f(n)，如對復雜度為 0(n)的算法其運行時間隨問題規(guī)模增長率為1+1/n,復雜度為0(1)的算法時間增長率為 1。7. 按增長率由小至大的順序排列下列各函數(2/3)n -2100 -log 2n-n 12-n -n log 2n-n3 2-2n-n!-n n第二章線性表1. 順序表：借助元素在存儲器中位置

4、上的”相鄰”關系表示數據元素間具有的關系，如此存儲的線性表稱為順序表。順序表優(yōu)點是實現簡單方便，可隨機訪問各元素；缺點是插入或刪除元素時會引起大量的數據元素移動俵尾除外)；對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常得不到充分利用。2. 線性鏈表：采用鏈式存儲結構的線性表對應一個鏈表。結點包含數據域和指針域兩部分。鏈表名指向第一個結點(頭指針)，尾結點指針域值為 NULL。鏈表優(yōu)點是空間利用好，插入刪除不移動數據，表頭表尾操作快(改進的單鏈 表),位置概念強；缺點是需要順序訪問各元素，位序概念弱。順序表相關程序：#define LIST_INIT_SIZE 100#d

5、efine LISTINCREMENT 10typedef * ElemType;typedef structElemType *elem; /存儲空間基址 intlen gth; intlistsize; /SqList;SqList La,Lb,Lc;Status In itList_Sq(SqList &L)/構造空線性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE *sizeof(ElemType) if(L.elem=0) exit(OVERFLOW);L.length=O;/初始化表長為0, “空"表L.listsize=LIS

6、T_INIT_SIZE;初 始化存儲容量 return(OK);/I nitList_Sqvoid ListDelete(SqList &L,i nt i,ElemType &e)/在順序表L中刪除第i個元素，用e返回其值.i 的合法值是1, ListLength(L) if(i<1|i>Length) return ERROR;/ 刪除位置不合理 ElemType *p=&L.elemi-1,*q=L.elem+L.le ngth-1; e=*p;while(p<q)*p=*(p+1);+p;刪除位置后元素左移 -L .len gth;return

7、Ok;/ListDelete_SqStatus ListInsert_Sq(SqList &L,int i, ElemType e)/在順序表L的第i個位置前插入元素e,i的合法值為1.L .le ngth+1if(i<1|i>L.length+1) return ERROR;/ 插入不合法 if(L.len gth>=L .li stsize) /表滿，增加存儲容量ElemType*newbase=(ElemType *)realloc (L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType) if(!n ewbase)

8、exit(OVERFLOW);L.elem=n ewbase;Listsize+=LISTINCREMENT;ElemType *q=&L.elemi-1, *p=&L.elemL.le ngth-1; while(p>=q)線性表相關程序：typedef * ElemType;typedef struct LNodeElemTypedata;/ 數據域struct LNode *next;/ 指針域LNode,*LinkList;/默認帶頭結點需說明 LNode no del;Lin kList La;Status GetElem_L(L in kList L,i nt

9、 i,ElemType &e)/L為帶頭結點的單鏈表的頭指針。第i個元素存在時其值賦給e并返回OK否則返回ERRORLNode *p=L->next; /p 指向"第 1 個"結點，int j=1;/ j為指向結點的位序while(p&&j<i) 順序查找，只要 p不空且未到第i結點就前進p=p->n ext;+j;if(!p)return ERROR; /第i個元素不存在 e=p->data;/取第i個元素return OK ；Status ListI nsert_L(L in kList &L, int i, El

10、emType e)/向鏈表L中第i個位置插入eLNode *p=L; int j=0;/*p始終指向第j個結點*/while(p&&j<i-1)p=p->next; +j;/ 尋找第 i-1 個結點 if(!p) return ERROR;LNode *temp;temp=(LNode *)Malloc(sizeof(LNode); if(!temp) exit(OVERFLOW);temp->data=e;相關兩表的歸并void MergeList_Sq (SqList La,SqList Lb,Sqlist &Lc)/歸并非降順序表La與Lb構成非

11、降順序表 LcLci stsize=Lcen gth=La .len gth+Lben gth;Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);If(!Lc.elem) exit(OVERFLOW); /存儲分配失敗ElemType *pa=La.elem, *pb=Lb.elem, *pc=Lc.elem;ElemType *paast=La.elem+La .l istsize-1;ElemType *pb_last=Lb.elem+La .li stsize-1; while(pa<=pa_last&&p

12、b<=pb_last) *(p+1)=*p; -p; /插入位置后的元素右移*q=e;+L .len gth;return OK;/ListI nsert_Stemp->n ext=p->n ext;p-> next=temp;return(OK);/List In sert_LStatus ListDelete_L(LinkList &L, int i, ElemType &e)LNode *p=L,*q; int j=0;/*p 始終指向第 j 個結點 */while(p&&j<i-1)p=p->next; +j;/ 尋找

13、第 i-1 個結點，j最終為i-1,除非到表尾p空 if(!p|!p-> next)returnERROR;/第 i個或更前結點不存在q=p->n ext;e=q->data;p->n ext=q->n ext;free(q);return(OK);/ListDelete_LStatus CreateList_L(Li nkList & L, i nt n)/逆位序輸入n個元素的值，建立帶頭結點的單鏈表L。LNode *p;L=(L in kList) malloc(sizeof(LNode);L-> next=NULL;for(i nt i=1;i

14、<=n ;+i)p=(LNode *)malloc(sizeof(LNode);/LNode * 等同 Lin kList sca nf(“”-劉郎)；p->n ext=L->n ext;L->next=p;插入到表頭/CreateList_L/歸并if(*pa<=*pb) *pc+=*pa+;else*pc+=*pb+;while(pa<pa_last) *pc+=*pa+;/ 插入 La 剩余段while(pb<pb_last) *pc+=*pb+; / 插入 Lb 剩余段 /MergeList_SqStatus ListMerge_SortedL

15、(SortedSqList La,SortedSqList Lb,SortedSqList & Lc)/將兩個有序順序表 La與Lb歸并為有序順序表Lcint la_le n=ListLe ngth_Sq(La);int lb_le n=ListLe ngth_Sq(Lb);int i=1,j=1,k=1;ElemType a,b;In itList_Sq(Lc);while(i<=la_le n&&j<=lb_le n) /歸并GetElem_Sq(La,i,a);GetElem_Sq(Lb,j,b); if(a<b) ListI nsert_Sq(

16、Lc,k+,a);+i; else ListInsert_Sq(Lc, k+,b); +j;while(i<=la_len) 插入La的剩余元素GetElem_Sq(La,i+,a); ListInsert_Sq(Lc, k+,a);while(j<=lb_len)/插入Lb的剩余元素 GetElem_Sq(Lb,j+,b); ListI nsert_Sq(Lc,k+,b); return OK;3. 注意鏈表中next指針的應用，如插入，刪除等操作各個元素的鏈接。4. 順序表的就地逆置思路：分別設兩個指針p與q指向第一個和最后一個元素，當p<q時*p與*q互換，之后+p,-

17、q。單鏈表的就地逆置思路：令指針p指向首元結點，頭結點斷開,將p所指結點插入到表頭后,p后移，直至p為空Status ListI nverse_Sq(SqList &L)/順序表就地逆置ElemType *p,*q;ElemType e;p=L.elem;q=L.elem+L.le ngth-1;while(p<q) temp=*p;*p=*q;*q=temp;+p; -q;return OK;Status ListI nverse_L(L in kList &L)/思路:令指針p指向首元結點，頭結點斷開，將p所指結 點插入到表頭后,p后移，至p空LNode *p,*q;

18、p=L->n ext;L-> next=NULL;while(p!=NULL)q=p->next; /令q指向p的后繼結點，以便以后p后移接下來兩句將p所指向節(jié)點插入到頭結點后p->n ext=L->n ext;L_>n ext=p;p=q;/q 后移return OK;有序順序表插入Status ListI nsert_SortedSq(SqList &L,ElemType e)/在非降順序表L中插入元素e,使得L中各元素仍然非降。注意插入位置據 e求得/思路：從最后一個元素開始，只要它比待插入元素大 就后移。條件不成立時退出循環(huán)，將e插入當前位置

19、后即可。順序表插入操作莫忘表滿的處理。只要是順序表 的插入操作就需要判斷是否表滿，對于鏈表則無此要求if(L.len gth>=L .li stsize)/表滿，增加存儲容量ElemType *n ewbase=(ElemType *) realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);5.循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的特點和基本操作。主要是 /-線性表的雙向(循環(huán))鏈表存儲結構-typedef struct DuLNodeElemTypeif(!n ewbase) exit(OVERFLOW);L.elem=n e

20、wbase;L.listsize+=LISTINCREMENT;/下面從最后一個元素開始，只要大于e就后移,最后插入當前位置后p=L.elem+Len gth-1;while(p>=L.ele m&&*p>e)*(p+1)=*p;-p;*(p+1)=e;+L.length; / 表長加 1return OK;data;插入刪除的相關指針操作。struct DuLNode *prior;struct DuLNode *n ext;DuLNode,*DuLi nkList;Status ListInsert_DuL(DuLinkList &L,int i,Ele

21、mType &e)/ 復雜度 O(ListLength(La)+ListLength(Lb),因只在表尾插 入)/在帶頭結點的雙向鏈表L的第i個位置插入e,1w iw表長+1DuLNode *p=L; int j=0;while(j<i-1 &&p)p=p-> next;+j;if(!p) return ERROR;s=(DuLNode *)malloc(sizeof(DuLNode); if(!s)exit(OVERFLOW);s->data=e;s->prior=p;s->next=p->next;/記:注意分析指針改變p_>

22、;n ext->prior=s;p->next=s; /次序對結果的影響 return OK;另外看下多項式的相關課件，老師復習提綱上有寫這方面的代碼。第三章棧和隊列1. 棧(Stack)是定義在線性結構上的抽象數據類型，其操作類似線性表操作，但元素的插入、刪除和訪問都必須在表的一端進行，為形象起見，稱允許操作端為棧頂(Top)，另一端為棧底(base),注意Top指向待插入位置。特性:LastIn First Out后進先出/總是訪問最近插入的一個/按插入順序倒著訪問。#define STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10typ

23、edef ? SElemType;/ 棧元素類型typedef structSElemType *base; / 棧底指針SElemType *top; / 棧頂指針int stacksize; / 棧容量SqStackStatus In itStack(SqStack &S)/構造空棧SS.base=(SElemType*) malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base)exit(OVERFLOW); 存儲分配失敗 S.top=S.base; / 空棧 S.stacksize=STACK_INIT_SIZE;return(O

24、K);/lnitStack復雜度 ” O(1) ”Status DestroyStack(SqStack &S)/銷毀棧Sfree(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK; /復雜度O(1)Status ClearStack(SqStack &S)/置S為空棧S.top=S.base; return OK; /復雜度O(1)Status Push(SqStack &S, SElemType e)/插入e為棧頂元素2. 隊列類似線性表和棧，也是定義在線性結構上的ADT端進行。類似日常生活中排隊，允許插入

25、的一端為隊尾if(S.top-S.base=S.stacksize> 判斷棧滿/棧滿則應重新分配空間S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) exit(OVERFLOW); S.top=(S.base+S.stacksize);/使得 S.top 重新指向 棧頂，因reallocS.stacksize+=STACKINCREMENT;*S.top +=e; /top指向待插入位置 return(OK);/Push ,復雜度 O(1)Statu

26、s Pop(SqStack & S,SElemType &e)/若棧不空則棧頂元素出棧并用e帶回其值if(S.top=S.base) return ERROR/ 判斷棧空 e=*(-S.top);/ 棧頂元素為 *(S.top-1)return OK; /復雜度O(1)Status StackEmpty(SqStack S)if(S.top=S.base) return TRUE; elsereturn FALSE;int StackLength (SqStack S) return (S.top-S.base); Status GetTop(SqStack S,SElemTy

27、pe &e)if(S.top=S.base) return ERROR;e=*(S.top-1);/注意top指向待插入位置return OK;棧的遍歷一直沒用到，可以自己找找課件看。線性表和棧的區(qū)別在于，元素的插入和刪除分別在表的兩(rear),允許刪除端稱隊頭(front)。特性:First In First Out先進#define * QEIemTypetypedef struct QNode QEIemType data; struct QNode *n ext; QNode, *QueuePtr;typedef struct QueuePtr front; 隊頭指針Queu

28、ePtr rear; / 隊尾指針 LinkQueue;/ 鏈隊列Status Ini tQueue (Lin kQueue &Q)/構造一個空隊列 QQ.fro nt=Q.rear=(QueuePtr)malloc(sizeof(QNode);if (!Q.fro nt) exit (OVERFLOW);Q.front->next = NULL; / 莫忘！return OK;/時間復雜度0(1)Status DestroyQueue (Lin kQueue &Q)/銷毀隊列Q,此處不同于教材，先清空元素結點，后釋 放頭結點QueuePtr p=Q.fro nt->

29、;n ext;while(p)/依次釋放首元素至最后一個元素Q.front->n ext=p->n ext; free(p);3. 循環(huán)隊列#define MAXQSIZE 100/ 最大隊列長度typedef struct QElemType *base;/ 動態(tài)分配存儲空間int front; /頭指針，隊列不空則指向隊列頭元素int rear; /尾指針，指向待插入元素位置 SqQueue;Status Ini tQueue (SqQueue &Q)/構造一個空隊列 QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof (QElemTy

30、pe);if (!Q.base) exit (OVERFLOW); / 存儲分配失敗Q.fro nt = Q.rear = 0;return OK;/復雜度0(1)Status DestroyQueue(SqQueue &Q)/銷毀隊列Qfree(Q.base);Q.fro nt = Q.rear = 0;return OK;/時間復雜度O(1)，比鏈隊列快p=Q.fr ont->n ext;free(Q.fro nt);Q.fro nt=NULL;Q.rear=NULL;return OK;/去掉下劃線部分為置空操作，復雜度O(n)Status En Queue (Lin kQ

31、ueue &Q, QElemType e)/插入元素e為Q的新的隊尾元素QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if (!p)exit(OVERFLOW);/存 儲分配失敗p->data = e;p->next = NULL;/ 莫忘！Q.rear- >n ext = p; Q.rear = p;return OK;/復雜度O(1)Status DeQueue (Lin kQueue &Q, QElemType &e)/若隊列不空，則刪除Q的隊頭元素，用e返回其值” if (Q.fro nt =Q.r

32、ear) return ERROR;/ 空隊列 QueuePtr p= Q.fron t- >n ext;e = p->data;Q.front->n ext = p->n ext;if(Q.rear = p) Q.rear=Q.front; 只 1 個結點時改尾指 針free (p);return OK;/復雜度O(1)Status ClearQueue(SqQueue &Q)/將隊列Q置空Q.front=Q.rear=O;只要想等即可return OK;/復雜度O(1)比鏈隊列快Status En Queue (SqQueue &Q, QElemTy

33、pe e)/插入元素e為Q的新的隊尾元素，無法插入(已滿) 則返回ERRORif(Q.rear+1)%MAXQSIZE=Q.fro nt)return ERROR;/判斷循環(huán)隊列滿的條件Q.baseQ.rear = e;Q.rear = (Q.rear+1) % MAXQSIZE; / 加便可能越界， 故取余return OK;/時間復雜度O(1)Status DeQueue (SqQueue &Q, ElemType &e) /隊列不空則刪除隊頭元素，用e帶回其值并返 OK;否 貝U返ERRORif (Q.rear=Q.front ) return ERROR;/判斷循環(huán)隊列

34、空e = Q.baseQ.fr on t;Q.fro nt = (Q.fro nt+1) % MAXQSIZE;/加就可能越界，故取余return OK; 時間復雜度0(1)int QueueLe ngth(SqQueue Q) /返回隊長return (Q.rear-Q.fro nt+MAXQSIZE)%MAXQSIZE; /減可能為負/時間復雜度O(1),比鏈隊列快，可修改鏈隊列定義Status QueueEmpty(SqQueue Q) /判斷隊列空if (Q.rear=Q.fro nt) return TRUE; else return FALSE;/O(1)Status GetHea

35、d(SqQueue Q,QEIemType &e)if (Q.rear=Q.fro nt)return ERROR;e=Q.baseQ.fro nt;return OK;/ O(1)若要修改對頭元素的值可新設SetHead(&Q,e)4. 證明：若借助棧由輸入序列12f得到的輸出序列為 p1p2pn(它是輸入序列的一個排列)，則在輸出序列中不可能出現這樣的情形：存在i<j<k使pj<pk<pi。思路：假設 pj<pk<pi往證i<j<k不成立。進一步假設 j<k成立，則pj在pk及pk以后的元素”入棧前已經出棧，故pk及pk

36、以后的元素”必然后于pj出現，而pi就是這樣的一個元素，其出現次序為i，故i>j,從而i<j<k不成立。第四章串第五章數組和廣義表1. 三元組順序表存儲結構：#defi ne MAXSIZE 12500typedef struct int i, j; /非零元的下標ElemType e; /非零元的值 Triple; /三元組類型typedef structTriple dataMAXSIZE + 1;/data0不用intmu,nu,tu;行列數與非零元個數 TSMatrix; /稀疏矩陣類型col從1變到n,2. 初始化一個“空”的稀疏矩陣，按照目標矩陣中的出現次序對原矩

37、陣中的元素逐個轉置，列號每次從頭至尾掃描 M.data，對列標等于col的三元組，將其行標、列標互換后依次放入T.data中。M.chead匚M.rhead3. 稀疏矩陣的十字鏈表表示：typedef StructOLink *rhead,*chead;/行頭指針與列頭指針數組int mu, nu, tuCrossList4. 上下三角矩陣存到一位數組的下標轉換。相關稀疏矩陣的程序可以看看課件。第六章樹和二叉樹1. 樹的結構特點：樹是一個層次結構，“有且僅有一個根結點無前驅(第一層)；有一或多個葉結點無后繼；其余結點有唯一前驅和若干后繼”。遞歸定義：樹由根結點(唯一)及該根結點的若干(零或多個

38、)“子樹”組成。不含任 何結點也是樹，稱為空樹2. 樹的相關術語如結點，度，見P120。(1) 結點(node):一個數據元素及其若干指向其子樹的分支。(2) 結點的度(degree)、樹的度：結點所擁有的子樹的棵數稱為結點的度。樹中結點度的最大值稱為樹的度。(3) 葉子(left)結點、非葉子結點：樹中度為0的結點稱為葉子結點(或終端結點)。相對應地，度不為 0的結點稱為非葉子結點（或非終端結點或分支結點）。除根結點外，分支結點又稱為內部結點。（4）孩子結點、雙親結點、兄弟結點：一個結點的子樹的根稱為該結點的孩子結點（child）或子結點；相應地，該結點是其孩子結點的雙親結點（pare nt

39、）或父結點。3. 性質1:在二叉樹的第i層上最多有2i-1個結點（i > 1） 性質2:深度為K的二叉樹最多有2K-1個結點（K> 1）性質3:對于任意一棵二叉樹 BT,如果度為0的結點個數為n0,度為2的結點個數為n2,則n0=n2+1。 證：二叉樹上結點總數n = n0 + n1 + n2。二叉樹上邊的總數e = n 1+2n2。根結點外每個結點都有且僅有一條邊（分支）'進入”，故 e = n-1。由此 n-1= n0 + n1 + n2 - 1，進而 n0 = n2 + 1 。性質4 :含n個結點的完全二叉樹深度為log2n +1。性質5:若對含n個結點的完全二叉樹從

40、上到下且從左至右進行1至n的編號，則對完全二叉樹中編號為i的結點：（1）若i=1，則該結點是二叉樹的根，無雙親，否則，編號為i/2的結點為其雙親結點；（2）若2i>n，則該結點無左孩子，否則，編號為2i的結點為其左孩子結點；（3）若2i+1>n,則該結點無右孩子，否則，編號為2i+1的結點為其 右孩子結點。4. 含n個結點的樹中，只有度為k的分支結點和度為 0的葉子結點，試求該樹含有的葉子結點數提示：n0+nk= n; e=knk=k（n-n0）=n-1故：n0=（nk-n+1）/k5. 二叉樹是度不大于2的有序樹（每個結點最多兩棵子樹，子樹有左右之分）。6. 滿二叉樹：設深度為

41、k,含 2k-1個結點的二叉樹。結點數達最大。7. 完全二叉樹：設樹中含n個結點，它們和滿二叉樹中編號為1至n的結點位置上一一對應（編號規(guī)則為由上到下，從左到右）。相比滿二叉樹僅少“最后的”若干個，不能少中間的。完全二叉樹特點：（1）葉子結點出現在最后2層或多或1層。（2）對于任意結點，若其右分支下的子孫的最大層次為L,則左分支下的子孫的最大層次為L或L+1。8. 二叉樹順序存儲：將二叉樹映射到完全二叉樹上，不存在的結點以空標記，之后用地址連續(xù)的存儲單元（一維數組）依次自上而下、自左而右存儲完全二叉樹上的各元素（將一般二叉樹以完全二叉樹形式存儲），最壞情況下k個結點需2k-1個單元。但適合完全

42、二叉樹的存儲，操作簡單方便。9. 二叉樹鏈表存儲：二叉鏈表包含內容，左孩子及右孩子的指針。三叉鏈表多了一個指向雙親結點的指針。typedef struct BiTNode typedef struct TriTNode TElemTypedata;struct T訂 Node*pare nt;struct BiTNode *lchild, *rchild;TElemTypedata; BiTNode, *BiTree;struct T訂 Node*lchild, *rchild;BiTree T; TilT Node, *T ilTre10. 先（根）序遍歷：樹非空則訪問根結點 ，后遞歸地先序

43、遍歷其左子樹；再遞歸地先序遍歷其右子樹；空則無操作。 中（根）序遍歷：樹非空則遞歸地中序遍歷根左子樹；后訪問根結點，再遞歸地中序遍歷右子樹；空則無操作。后（根）序遍歷：樹非空則遞歸地后序遍歷根右子樹；后遞歸地后序遍歷右子樹，再訪問根結點；空則無操作 層次遍歷：由上到下，由左到右，不宜遞歸T=(BiTree)malloc(sizeof(BiTNode);typedef struct BiTNode TEIemType data;struct BiTNode *lchild, *rchild; BiTNode, *BiTree;BiTree T;typedef int TEIemType;Stat

44、us CreateBiTree(BiTree &T)/遞歸創(chuàng)建二叉樹TEIemType e; sca nf("%d", &e); if(e=0) T=NULL;elseif(!T) exit(OVERFLOW); T->data=e;CreateBiTree(T->lchild);CreateBiTree(T->rchild);return OK;/若元素為字符型則輸入時不可隨意加空格Status DestroyBiTree(BiTree &T)/二叉鏈表的后序遞歸銷毀if(!T) return OK;elseDestroyBiTr

45、ee(T->lchild);DestroyBiTree(T->rchild);free(T);T=NULL;不可丟！return OK;Status PreOrderTraverse(BiTree T,Status(*visit)(TEIemType)/先序遍歷，先序輸出函數只要把(*visit)換為輸出函數if(T)if( (*visit)(T->data)if( PreOrderTraverse(T->lchild,(*visit)if( PreOrderTraverse(T->rchild,(*visit)return OKreturn ERROR;else

46、 return OK;int TreeDepth(BiTree T)/遞歸法求樹的深度。思路：如果樹為空樹則深度為0,否則，先遞歸計算出左子樹的深度，再計算出右子樹的深度，最后，樹的深度為兩子樹深度的最大值加1if(T=NULL)d=0;elsed仁 TreeDepth(T->lchild1);d2=TreeDepth(T->rchild);if(d1>d2) d=d1+1;else d=d2+1;return d;/其余操作類似實現，務必掌握int NodeCou nt (BiTree T)/遞歸求結點數，若二叉樹為空樹則節(jié)點數為0,否則先遞歸求左子樹和右子樹的節(jié)點數，整棵

47、樹的節(jié)點數是 左右子樹節(jié)點數之和再加1if(T=NULL) return 0;elsereturn1+NodeCou nt(T->lchild)+ NodeCou nt(T->rchild);int LeafCount (BiTree T)/求葉子數，思路：若二叉樹為空樹則葉子節(jié)點數為0，若二叉樹只含有一個節(jié)點則葉子數為1,否則先遞歸求左子樹和右子樹的葉節(jié)點數，整棵樹的節(jié)點數是左右子 樹葉節(jié)點數之和。if(T=NULL) retur n 0;else if(T->lchild=NULL&& T->rchild=NULL)return 1;elseretu

48、rn LeafCou nt(T->lchild)+ LeafCou nt(T->rchild);Status Excha ngeBiTree(BiTree &T)/二叉樹用二叉鏈表存儲，左右互換BiTNode *temp;if(T= =NULL) return OK;elsetemp=T->lchild;T->lchild=T->rchild;T->rchild=temp;Excha ngeBiTree(T->lchild);Excha ngeBiTree(T->rchild);return OK;11. 由遍歷序列確定二叉樹：先序序列+

49、中序序列：先序序列中第 1個元素X為根，中序序列中唯有遍歷完 X的左子樹后方訪問 X，故X之前 的abc必構成X的左子樹，X之后的def必構成X的右子樹。對于子樹類似處理，第1個在先序序列中出現的元素Y為該左子樹的根，中序序列中Y左側的元素構成 Y的左子樹，右側構成右子樹，依此類推，最終可定。中序序列+后序序列：后序序列中最后一個元素為根，中序序列中該結點前的元素為左子樹，后的元素為右子樹。對于左/右子樹，最后一個在后序序列中出現的元素為子樹的根結點，再看中序序列，依此類推。先序輸出+后序輸出不能確定。如 AB和BA。12. 二叉樹線索化的實質是建立結點與其在相應序列中的前驅或后繼之間的直接聯

50、系，若結點有左子樹，則其lchild域指示其左孩子，否則令 lchild域指示其前驅；若結點有右子樹，則其rchild域指示其右孩子，否則令 rchild域指示其后繼。為了避免混淆，增加兩個標志位LTag與 RTag其為0是表示域指向孩子，為1時表示指向其前驅或者后繼。（詳細見課本P132）13. 二叉樹的線索化：設一棵二叉樹有n個結點，則有n-1條邊（指針連線），而n個結點共有2n個指針域（Lchild和Rchild），顯然有n+1個空閑指針域未用。 則可以利用這些空閑的指針域來存放結點的直接前驅和直接后繼信息。增設頭結點，左標記為Link，左指針指根結點，右標記為Thread，右指針指向最

51、后被訪問的結點，樹空則均指向頭結點。又稱雙向線索鏈表，先寫出遍歷序列，后添加頭結點，再據序列增加線索即可。用這種結點結構構成的二叉樹的存儲結構；叫做線索鏈表；指向結點前驅和后繼的指針叫做線索；按照某種次 序遍歷，加上線索的二叉樹稱之為線索二叉樹。14. 樹的雙親表示法：以一組連續(xù)空間存儲結點，各結點附設指示器指示其雙親結點的位置（數據域+ 雙親下標域）。線索化n雙親表示法15. 樹的孩子表示法：結點中為其每個孩子附設一個指針。具體定義時各結點指針的個數可取最大，也可根據各自 的度不同而不同。前者同構，實現簡單；后者需動態(tài)開辟指針域，實現復雜但空間省。child 1 chiW2chtidMAX1

52、6.孩子雙親表示法:鏈式存儲與順序存儲結合，將各結點存儲在一個數組中，每個數組元素附加一指針域指向結點的孩子形成的鏈表。若經常進行訪問雙親結點的操作則可向數組元素追加雙親位置域。孩子雙親表示法孩子兄弟表示法17. 樹的孩子兄弟表示法（二叉鏈表存儲）：鏈式存儲，每個結點包括數據域和兩個指針域，左指針指向第一個孩子結點，右指針指向兄弟結點又稱二叉鏈表存儲法。（表示法能畫出來應該就可以，各個存儲結構應該不會考吧，有興趣的自己找找書P135）18. 森林的孩子兄弟表示法 （二叉鏈表存儲）：單顆樹的二叉鏈表存儲結構中根結點的右指針必為空，若要存儲多顆樹組成的森林，可將后一顆樹的根結點看成前一顆樹根結點的

53、兄弟，即將后一顆樹對應的二叉鏈表拼接到前一顆樹根結點的右指針上，這稱為森林的孩子兄弟表示法或二叉鏈表存儲法。19. 樹、森林與二叉樹的轉換：以二叉鏈表存儲結構為轉換依據，將左右指針所指結點理解為左右孩子結點則得到二叉樹；將左指針所指結點理解為孩子，右指針所指結點理解為當前結點的兄弟則得樹或森林。20. 樹采用二叉鏈表存儲，對樹進行遍歷即對二叉鏈表進行遍歷。先序遍歷二叉鏈表（先根結點后左子樹再右子樹），對應到樹上是 先根，后自左到右遞歸遍歷各子樹”，稱為樹的先根序遍歷。對二叉鏈表進行中序遍歷（先左子樹中根再右子樹）對應到樹上是先從左到右各子樹，后根”，稱為樹的后根序遍歷。21. 森林采用二叉鏈表

54、存儲（孩子兄弟表示法），先序遍歷二叉鏈表 （先根結點后左子樹再右子樹 ），對應到樹上為 從 左到右依次先根遍歷各顆樹”，稱為森林的先序遍歷。森林采用二叉鏈表存儲（孩子兄弟表示法），對二叉鏈表 先左子樹中根再右子樹”中序遍歷，對應到森林為 從左 到右依次后根遍歷各顆樹”，稱為森林的中序遍歷。22. 由樹的先根和后根遍歷序列確定樹：方法一（間接法，借助二叉鏈表）：樹的先根序列對應二叉鏈表的先序序列、后根序列對應二叉鏈表的中序序列，由先序序列與中序序列可確定出二叉鏈表，再根據此二叉鏈表按照孩子兄弟表示法的含義可得此二叉鏈表對應的樹。方法二（直接法，根據先根后根）：先根序列中第1個X 一定是整顆樹的根

55、結點，而后根序列中唯有遍歷完X的所有子樹后方訪問 X,故X必然出現在最后；先根序列中第二個頂點必然是第一個子樹的根結點，后根序列中 該結點前的結點為此子樹中各結點；除去第一顆子樹中的結點后，先根序列中第一個結點必為第二顆子樹的根 結點，而后根序列中此結點前的結點構成第二顆子樹，以此類推，最終可確定。23. 由森林的先序和中序遍歷序列確定森林：方法一（間接法，借助二叉鏈表）：森林的先序序列對應二叉鏈表的先序序列、中序序列對應二叉鏈表的中序序列，由先序序列與中序序列可確定出二叉鏈表，再根據此二叉鏈表按照孩子兄弟表示法的含義可得此二叉鏈表對應 的森林方法二（直接法，根據先根后根）：先序序列中第1個X 一定是第一顆樹的根結點，而中序序列中在遍歷完第一顆 樹的最后訪問X故中序序列中X之前的結點構成森林的第一顆樹，這些結點在先序和中序序列中的出現次序即 為第一顆樹的先根序列和后根序列，根據樹的確定方法可得第一顆樹；除去第一顆樹的結點后，先序序列中余 下的第一個結點為第二顆樹的