電子科大820數(shù)據(jù)結構考綱考點歸納

1、ch1. 數(shù)據(jù)結構及算法的相關概念和術語（1） 數(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ù)據(jù)的存儲結構、數(shù)據(jù)的運算數(shù)據(jù)的邏輯結構：線性結構（線性表）、非線性結構（集合、樹和圖）。數(shù)據(jù)的存儲結構：順序存儲：優(yōu)點：可

2、以隨機存取，每個元素占用最少存儲空間缺點：可能產(chǎn)生較多碎片現(xiàn)象鏈式存儲：優(yōu)點：不會出現(xiàn)碎片現(xiàn)象缺點：每個元素占用較多存儲空間，只能實現(xiàn)順序存儲索引存儲：優(yōu)點：檢索速度快缺點：增加了附加的索引表，會占用較多存儲空間散列存儲：優(yōu)點：檢索、增加和刪除結點的操作都很快缺點：可能出現(xiàn)存儲單元的沖突，解決沖突會增加時間和空間的開銷（3）算法的定義及特性；算法：對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。算法的特性：有窮性、確定性、可行性、輸入、輸出算法設計的要求：正確性、可讀性、健壯性、效率與低存儲量需求* 同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低（4）算法時

3、間復雜度和空間復雜度的分析方法。時間復雜度：主要分析語句頻度（一條語句在算法中被重復執(zhí)行的次數(shù)）之和t(n)的數(shù)量級加法原則：t(n)=t1(n)+t2(n)=o(max(f(n),g(n)乘法原則：t(n)=t1(n)t2(n)=o(f(n)·g(n)* 常見時間復雜度比較：o(1)<o(n)<o(nlogn)<o(n2)<o(n3)<o(2n)<o(n!)<o(nn)空間復雜度：算法所耗費的存儲空間，s(n)=o(g(n)算法原地工作是指算法所需輔助空間是常量，即o(1)ch2線性表（1）線性表的定義線性表：具有相同數(shù)據(jù)類型的n(n0)個

4、數(shù)據(jù)元素的有限序列，一般表示如下：l=(a1, a2, , ai+1, , an)其中，a1是唯一的“第一個”數(shù)據(jù)元素，稱為表頭元素；an是唯一的“最后一個”數(shù)據(jù)元素，稱為表尾元素；除第一個元素外，每個元素有且僅有一個直接前趨；除最后一個元素外，每個元素有且僅有一個直接后繼。線性表的特點：表中元素具有邏輯上的順序性，表中元素都是數(shù)據(jù)元素，表中元素的數(shù)據(jù)類型都相同，表中元素具有抽象性。（2）線性表的基本操作及在順序存儲及鏈式存儲上的實現(xiàn)；線性表的基本操作：initlist(&l) 構造一個空的線性表listlength(l) 求表長，即求線性表中數(shù)據(jù)結點（如果是帶頭結點單鏈表，則不含頭結

5、點）的個數(shù)locateelem(l, e) 按值查找getelem(l, i) 按位查找listinsert(&l, i, e) 在表l中的第i個位置插入指定元素listdelete(&l, i, &e) 刪除表l中的第i個位置的元素，并輸出其值printlist(l) 按前后順序輸出線性表l的所有元素值listempty(l) 判空，若l為空表，返回true，否則返回falsedestroylist(&l) 銷毀線性表，并釋放表l占用的內存空間clearlist(&l) 將l重置為空表priorelem(l,cur_e,&pre_e) 若cur

6、_e是表l的數(shù)據(jù)元素，且不是第一個，用pre_e返回其前驅nextelem(l,cur_e,&next_e) 若cur_e是表l的元素，且不是最后一個，用next_e返回其后繼listtraverse(l,visit() 表的遍歷，即依次對l的每個元素調用函數(shù)visit()線性表的順序存儲（順序表）：線性表中第i+1個數(shù)據(jù)元素的存儲位置loc(ai+1)和第i個數(shù)據(jù)元素的存儲位置loc(ai)之間關系：loc(ai+1)= loc(ai)+l線性表的第i個數(shù)據(jù)元素ai的存儲位置：loc(ai)= loc(a1)+(i-1)·l順序表的特點：可以進行隨機存取，即通過首地址和元素

7、序號可以在o(1)的時間內找到指定元素，但插入和刪除元素操作需要移動大量元素順序表結構的定義：順序表的靜態(tài)分配：#define maxsize 50typedef structelemtype datamaxsize;int length;sqlist;順序表的動態(tài)分配：#define initsize 50typedef structelemtype *data;int listsize,length;sqlist;* 動態(tài)分配語句：l.data=(elemtype *)malloc(sizeof(elemtype)*initsize);順序表基本操作的實現(xiàn)：初始化操作：構造一個空的順序表l

8、bool initlist_sq(sqlist &l)l.data=(elemtype *)malloc(initsize*sizeof(elemtype);if(!l.data) exit(overflow);l.length=0;l.listsize=initsize;return true;/initlist_sq插入操作：在第i(1in)個元素之前插入一個元素，需將第n至第i(共n-i+1)個元素向后移動一個位置。bool listinsert_sq(sqlist &l,int i,elemtype e)/在順序表l中的第i個位置插入新元素e/i的合法值為1il.len

9、gth+1if(i<1|i>l.length+1) return false; /i值不合法if(l.length>=listsize) /當前存儲空間已滿，不能插入return false;for(i=l.length;j>=i;j-) /將第i個位置及之后元素后移l.dataj=l.dataj-1;l.datai-1=e;/在位置i處放入el.length+;/表長加1return true;/listinsert_sq時間復雜度：最好情況：在表尾插入，無須移動元素，t(n)=o(1)最壞情況：在表頭插入，需要移動第一個元素后面所有元素，t(n)=o(n)平均情況：

10、t(n)=n/2=o(n)刪除操作：在順序表l中刪除第i(1in)個元素，需將第n至第i(共n-i+1)個元素向前移動一個位置。bool listdelete_sq(sqlist &l,int i,elemtype e)/在順序表l中刪除第i個元素，并用e返回其值/i的合法值為1il.lengthif(i<1|i>l.length) return false; /i值不合法e=l.datai-1;for(int j=i;j<l.length;j+)l.dataj-1=l.dataj;l.length-;return true;/listdelete_sq時間復雜度t(

11、n)：最好情況：刪除表尾元素，無須移動元素，t(n)=o(1)最壞情況：刪除表頭元素，需要移動第一個元素后面所有元素，t(n)=o(n)平均情況：t(n)=(n-1)/2=o(n)按值查找（順序查找）:int locateelem(sqlist l,int i,elamtype e)/查找順序表中值為e的元素，若查找成功，返回元素位序，否則返回0for(int i=0;i<l.length;i+)if(l.datai=e) return i+1; /下標為i的元素值等于e，返回其位號i+1return 0;/locateelem順序表的歸并：t(n)=o(la.length+lb.len

12、gth)void mergelist_sq(sqlist la, sqlist lb, sqlist &lc)/已知順序表la和lb的元素按值非遞減排列/歸并la和lb得到新的順序表lc，lc的元素也按值非遞減排列pa=la.data;pb=lb.data;lc.listsize=lc.length=la.length+lb.length;pc=lc.data=(elemtype *)malloc(lc.listsize*sizeof(elemtype);if(!lc.data) exit(overflow);pa_last=la.data+la.length-1;pb_last=lb

13、.data+lb.length-1;while(pa<=pa_last&&pb<=pb_last) /開始歸并if(*pa<=*pb) *pc+=*pa+;else *pc+=*pb+;while(pa<=pa_last) *pc+=*pa+;while(pb<=pb_last) *pc+=*pb+;/mergelist_sq線性表的鏈式存儲（單鏈表）：單鏈表結構的定義：typedef struct lnodeelemtype data;struct lnode *next;lnode,*linklist;引入頭結點的單鏈表：頭結點的數(shù)據(jù)域可以不設

14、任何信息，也可以記錄表長等信息，頭結點的指針域指向線性表的第一個結點。* 引入頭結點的兩個優(yōu)點：(1) 由于開始結點的位置被存放在頭結點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致，無須進行特殊處理(2) 無論鏈表是否為空，其頭指針是指向頭結點的非空指針（空表中頭結點的指針域空），因此空表和非空表的處理也就統(tǒng)一了單鏈表基本操作的實現(xiàn)：單鏈表的建立1（頭插法）：時間復雜度o(n)void createlist1_l(linklist &l,int n)/從表尾到表頭逆位序輸入n個元素的值，建立帶頭結點的單鏈表l/每次均在頭結點之后插入元素l=(linklist)

15、malloc(sizeof(lnode); /創(chuàng)建頭結點l->next=null; /初始為空表for(i=n;i>0;i-)p=(linklist)malloc(sizeof(lnode); /創(chuàng)建新結點scanf(&p->data);p->next=l->next;l->next=p;/將新結點插入表中/createlist1_l單鏈表的建立2（尾插法）：時間復雜度o(n)void createlist2_l(linklist &l,int n)/從表頭到表尾正向輸入n個元素的值，建立帶頭結點的單鏈表l/每次均在表尾插入元素l=(link

16、list)malloc(sizeof(lnode); /創(chuàng)建頭結點l->next=null; /初始為空表q=l; /表尾指針for(i=n;i>0;i-)p=(linklist)malloc(sizeof(lnode); /創(chuàng)建新結點scanf(&p->data);r->next=p;r=p;/將新結點插入表中r->next=null;/表尾指針置空/createlist2_l單鏈表的查找1（按位置查找）：lnode* getelem_l(linklist l,int i)/l為帶頭結點的單鏈表的頭指針/當?shù)趇個元素存在時，返回第i個結點的指針，否則返回

17、nullint j=1;/計數(shù)，初始為1p=l->next;/初始化，p指向每一個結點while(p&&j<i)/順時針向后查找，直到p指向第i個元素或p為空p=p->next;j+;if(!p|j>i) return null; /若i大于表長，p=null直接返回nullreturn p;/返回第i個結點的指針/getelem_l單鏈表的查找2（按值查找）：lnode* locateelem_l(linklist l,elemtype e)/l為帶頭結點的單鏈表的頭指針/當值查找成功時返回數(shù)據(jù)域值等于e的結點指針，否則返回nullint i=0;p=

18、l->next;while(p&&p->data!=e) /順時針向后查找，直到p指向值為e的元素或p為空p=p->next;return p;/找到后返回該結點指針，否則返回null/locateelem_l插入操作(前插)：先找到前驅結點*p，然后完成在*p后插入*s，時間復雜度t(n)=o(n)bool listinsert_l(linklist &l,int i,elemtype e)/在帶頭結點的單鏈表l中第i個位置插入元素ep=getelem_l(l,i-1);/查找插入位置的前趨結點if(!p) return false;/插入位置不合法

19、s=(linklist)malloc(sizeof(lnode);/生成新結點s->data=e;/插入l中s->next=p->next;p->next=s;return true;/listinsert_l插入操作（后插）：設p指向單鏈表中某結點，s指向待插入值為e的新結點，將*s插入到*p之后。時 間復雜度t(n)=o(1)/只給出關鍵代碼段s->next=p->next;/修改指針域，順序不能顛倒p->next=s;e=p->data;/交換數(shù)據(jù)域部分p->data=s->data;s->data=e刪除操作1：先找到被

20、刪結點的前趨，然后完成在*p后刪除被刪結點，時間復雜度t(n)=o(n)bool listdelete_l(linklist &l,int i,elemtype &e)/在帶頭結點的單鏈表l中，刪除第i個元素，并由e返回其值p=getelem_l(l,i-1); /查找第i個結點，并令p指向其前趨if(!p) return false;/刪除位置不合法q=p->next;/令q指向被刪除結點p->next=q->next;/將*q結點從鏈中斷開e=q->data;/取其數(shù)據(jù)域的值free(q);/釋放結點的存儲空間return true;/listdel

21、ete_l刪除操作2：將結點*p后繼結點的值賦予其自身，然后刪除后繼結點，時間復雜度t(n)=o(1)/只給出關鍵代碼段q=p->next;/修改指針域，順序不能顛倒p->data=p->next->data; /和后繼結點交換數(shù)據(jù)域e=p->data;p->next=q->next; /將*q結點從鏈中斷開free(q);/釋放結點的存儲空間單鏈表的歸并：void mergelist_l(linklist la, linklist lb, linklist &lc)/已知單鏈表la和lb的元素按值非遞減排列/歸并la和lb得到新的單鏈表lc，

22、lc的元素也按值非遞減排列pa=la->next;pb=lb->next;lc=pc=la;/用la的頭結點作為lc的頭結點while(pa&&pb)/開始歸并if(pa->data<=pb->data)pc->next=pa;pc=pa;pa=pa->next;elsepc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;/插入剩余段free(lb); /釋放lb頭結點/mergelist_l（3）各種變形鏈表（循環(huán)鏈表、雙向鏈表、帶頭結點的鏈表等）的表示和基本操作的實現(xiàn)；循

23、環(huán)鏈表：循環(huán)單鏈表：表尾結點的next域指向l，表中沒有指針域為null的結點，因此循環(huán)單鏈表的判空條件是看它的頭結點的指針域是否等于頭指針；循環(huán)單鏈表在任何一個位置上插入和刪除操作都是等價的，無需判斷是否表尾；循環(huán)單鏈表可以從表中任一結點開始遍歷整個鏈表。循環(huán)單鏈表不設頭指針而只設尾指針，可使一些操作效率更高。循環(huán)雙鏈表：與循環(huán)單鏈表不同的是，循環(huán)雙鏈表中頭結點的prior指針還指向表尾結點；在循環(huán)雙鏈表l中，某結點*p為尾結點時，p->next=l；當循環(huán)雙鏈表為空時，對其頭結點*p，有p->prior=p->next=l。雙向鏈表：其結點有兩個指針域，一個指向直接后繼，

24、另一個指向直接前趨，雙向鏈表的插入、刪除結點算法的時間復雜度為o(1)。雙向鏈表結構的定義：typedef struct dulnodeelemtype data;struct lnode *prior,*next;dulnode, *dulinklist;雙向鏈表的插入操作：/只給出關鍵代碼段/在結點*p之后插入值為e的新結點*ss->data=e;s->next=p->next;p->next->prior=s;/語句執(zhí)行順序不唯一，但這兩步必須在最后一步之前s->prior=p;p->next=s;/在結點*p之前插入值為e的新結點*ss->

25、;data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;雙向鏈表的刪除操作：/只給出關鍵代碼段/刪除結點*p的后繼結點*q，并用e返回其值e=q->data;p->next=q->next;q->next->prior=p;free(q);/刪除結點*q的前趨*p，并用e返回其值e=p->data;q->prior=p->prior;p->prior->next=q;free(p);帶頭結點的鏈表：帶頭結點的鏈表結構定義：typ

26、edef struct lnode/結點類型elemtype data;struct lnode *next;*link,*position;typedef struct/鏈表類型link head,tail;/分別指向鏈表的頭結點和尾結點int length;/線性表中元素的個數(shù)linklist;ch3棧與隊列（1）棧和隊列的基本概念；棧和隊列的順序存儲結構、鏈式儲存結構及其存儲特點；棧：限定在表尾進行插入或刪除操作（頭進尾出）的線性表，表尾稱為棧頂（top），表頭稱為棧底（bottom），不含任何元素的棧稱為空棧，棧又被稱為后進先出（lifo）線性表。隊列：只允許在表的一端進行插入，另一端

27、進行刪除操作（尾進頭出），允許插入的一端叫做隊尾（rear）， 允許刪除的一端叫做隊頭（front），是一種先進先出（fifo）的線性表。棧的基本操作：initstack(&s) 初始化，構造一個空棧sstackempty(s) 棧s判空stacklength(s) 求棧長，即棧s的元素個數(shù)push(&s,x) 入棧，插入元素為x的新棧頂元素pop(&s,x) 出棧，刪除棧s的棧頂元素，并用x返回其值gettop(s,&x) 取棧頂，用x返回棧s的棧頂元素clearstack(&s) 將棧s清空destroystack(&s) 銷毀棧，并釋放其存

28、儲空間棧的順序存儲（順序棧）：可能發(fā)生上溢基本操作：/只給出關鍵語句initstack(&s) /棧滿條件s.top-s.base=s.stacksizes.top=s.base;s.stacksize=initsize; /?？諚l件s.top=s.basegettop(s, &e)e=*(s.top-1);push(&s,e)*s.top+=e;/入棧時棧頂指針先加1，再送值到棧頂元素pop(&s,&e)e=*-s.top;/出棧時先取棧頂元素值，再將棧頂指針減1棧的鏈式存儲（鏈棧）：便于多個棧共享存儲空間和提高其效率，不存在棧滿上溢的情況，規(guī)定鏈棧沒

29、有頭結點，lhead指向棧頂元素?；静僮鳎?只給出關鍵語句initstack(&s)/初始化p->next=s->next;s->next=p;push(&s,e)/入棧p->data=e;s->next=p;p->next=s->next;pop(&s,&e)/出棧p=s->next;e=p->data; s->next=p->next;free(p);destroystack（&s）/銷毀棧p=s;s=s->next;free(p);隊列的鏈式存儲（鏈隊列）：基本操作：/只給出

30、關鍵語句initqueue(&q)/初始化q.front=q.rear=(queueptr)malloc(sizeof(qnode);q.front->next=null;destroyqueue(&q)/銷毀隊列q.rear=q.front->next;free(q.front);q.front=q.rear;enqueue(&q,e)/入隊p->data=e;p->next=null;q.rear->next=p;q.rear=p;dequeue（&q,&e）/出隊p=q.front->next;e=p->d

31、ata;q.front->next=p->next;if(q.rear=p)q.rear=q.front;free(p);隊列的順序存儲（循環(huán)隊列）：約定初始化建空隊列時，令front=rear=0，每當插入新的元素時，尾指針增1，當刪除隊列元素時，頭指針增1，因此在非空隊列中，頭指針始終指向頭元素，尾指針始終指向隊列尾元素的下一個位置* 如果用戶的應用程序中設有循環(huán)隊列，則必須為它設定一個最大隊列長度，若用戶無法預估所用隊列的最大長度，宜采用鏈隊列（2）循環(huán)隊列的判滿、判空方法；方法一：另設一個標志位以區(qū)別隊列是空還是滿方法二：犧牲一個單元來區(qū)分隊空和隊滿，入隊時少用一個隊列單元

32、，約定以隊頭指針在隊尾指針的下一位置作為隊滿的標志隊滿條件：(q.rear+1)%maxsize=q.front隊空條件：q.rear=q.front隊列中元素個數(shù)：（q.rear-q.front+maxsize）%maxsize（3）棧和隊列的應用棧的應用：數(shù)制轉換、括號匹配、表達式求值、迷宮求解、實現(xiàn)遞歸隊列的應用：層次遍歷、解決主機與外部設備之間速度不匹配的問題，解決由多用戶引起的資源競爭問題（4）遞歸過程的特點及實現(xiàn)方法；遞歸的兩個必要條件：1) 遞歸表達式（遞歸體）2) 邊界條件（遞歸出口）* 遞歸的精髓在于能否將原始問題轉的為屬性相同但規(guī)模較小的問題（5）特殊矩陣的壓縮儲存； 數(shù)組

33、的存儲結構：行優(yōu)先：loc(i,j)=loc(0,0)+(b2·i+j)l列優(yōu)先：loc(i,j)=loc(0,0)+(b2·j+i)l 特殊矩陣的壓縮存儲：對稱矩陣：將n2個元素壓縮存儲到n(n+1)/2個元素的空間中，可以行序為主序存儲基下三角（含對角線）中的元素，以一維數(shù)組san(n+1)/2作為n價對稱矩陣a的存儲結構，則sak和矩陣元aij之間存在著一一對應關系：k= i(i-1)2+j-1, &ij (下三角區(qū)和主對角線元素)j(j-1)2+i-1, &i<j (上三角區(qū)元素aij=aji)=tm×n稀疏矩陣：假設在m×

34、n的矩陣中，有t個元素不為零，令稱為矩陣的稀疏因子，通常認0.05時稱為稀疏矩陣，存儲時只存儲稀疏矩陣的非零元，可用三元組順序表和十字鏈表兩種方式存儲。行號列號元素值ije三元組表格式：十字鏈表：在鏈表中，每個非零元可用一個含5個域的結點表示，其中i、j和e這3個域分別表該非零元所在的行、列和非零元的值，向右域right用以鏈接同一行中下一個非零元，向下域down用以鏈接同一列中下一個非零元 /十字鏈表結構定義 typdef struct olnode int i,j;elemtype e;struct olnode *right,*down; olnode;*olink; typedef s

35、tructolink *rhead,*chead;int mu,nu,tu; crosslist;ch4廣義表的基本概念、存儲結構和基本操作廣義表的定義：廣義表一般記作ls=(1，2，n)其中，ls是廣義表(1，2，n)的名稱，n是它的長度，i可以是單個元素，也可以是廣義表，分別稱為ls的原子和子表，當廣義表ls非空時，稱第一個元素1為ls的表頭(head)，稱其余元素組成的表(2，3，n)是ls的表尾(tail)幾類廣義表：a=()a是一個空表，它的長度為零b=(e)列表b只有一個原子e，b的長度為1c=(a,(b,c,d)列表c長度為2，兩個元素分別為原子a和子表(b,c,d)d=(a,b

36、,c)列表d的長度為3，3個元素都是列表，代入a、b和c的值后，有d=(),(e),(a,(b,c,d)e=(a,e)列表e是一個遞歸的表，它的長度為2，深度為廣義表的存儲結構：頭尾鏈表、擴展線性鏈表擴展線性鏈表中結點的類型：表結點：tag=1hptp原子結點：tag=0atomtp廣義表的主要操作：gethead(ls) 取表頭（第一個元素）gettail(ls) 取表尾（除第一個元素外其余元素組成的表）ch5樹和二叉樹（1）樹與森林的基本概念樹的定義：樹是n(n0)個結點的有限集。在任意一棵非空樹中：(1) 有且僅有一個特定的稱為根的結點；(2) 當n>1時，其余結點可分為m(m&g

37、t;0)個互不相交的有限集t1，t2，tm，其中每一個集合本身又是一棵樹，并稱為根的子樹。樹是一種遞歸的數(shù)據(jù)結構，樹作為一種邏輯結構，同時也是一種分層結構。樹的特點：1) 樹的根結點沒有前驅結點，除根結點之外的所有結點有且只有一個前驅結點2) 樹中所有結點可以有零個或多個后繼結點樹的一些基本術語：結點的度：樹中一個結點的子結點數(shù)樹的度：樹中結點的最大度數(shù)分支結點：度大于0的結點（非終端結點）葉子結點：度為0的結點（終端結點）結點的層次：從根開始定義起，根為第一層，根的孩子為第二層，若某結點在第l層，則其子樹的根就在第l+1層樹的深度（高度）：樹中結點的最大層次森林：m(m>0)棵互不相交

38、的樹的集合，對樹中的每個結點而言，基子樹的集合即為森林* 注：由于樹中的分支是有向的，所以樹中的路徑是從上到下的，同一雙親結點的兩個孩子結點之間不存在路徑樹的性質：1) 樹中結點數(shù)=所有結點的度數(shù)(樹中的邊數(shù))+12) 度為m的樹中第i層上至多有mi-1個結點(i1)3) 高度為h的m叉樹至多有(mh-1)/(m-1)個結點4) 具有n個結點的m叉樹的最小高度為<logm(n(m-1)+1)>（<x>表示不小于x的最小整數(shù)）（2）二叉樹的定義及6大性質二叉樹的定義：二叉樹是別一種樹型結構，其特點是每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點），并且二叉樹的子

39、樹有左右之分，其次序不能任意顛倒二叉樹的性質：性質1：在二叉樹的第i層上至多有2i-1個結點(i1)性質2：深度為k的二叉樹至多有2k-1個結點(k1)滿二叉樹：一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹完全二叉樹：深度為k的有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱之為完全二叉樹，其特點是：(1) 葉子結點只可能在層次最大的兩層出現(xiàn)；(2) 對任一結點，若其右分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1性質3：對任何一棵二叉樹t，如果其葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則n0=n2+1，設b為分支數(shù)

40、，n為結點總數(shù)，則有n=n1+2n2+1=b+1性質4：具有n個結點的完全二叉樹的深度為log2n+1（x表示不大于x的最大整數(shù)）性質5：如果對一棵有n個結點的完全二叉樹的結點按編號（從第1層到第log2n+1層，每層從左到右），則對任一結點i(1in)，有：1) 如果i=1則結點i是二叉樹的根，無雙親；如果i>1，則其雙親parent(i)是結點i/2（x表示不大于x的最大整數(shù)），即當i為偶數(shù)時，其雙親為結點i/2；當i為奇數(shù)時，其雙親為結點(i-1)/22) 如果2i>n，則結點i無左孩子（結點i為葉子結點）；否則其左孩子lchild(i)是結點2i3) 如果2i+1>n

41、，則結點i無右孩子；否則其右孩子rchild(i)是結點2i+1性質6： 給定n個節(jié)點，能構成h(n)種不同的二叉樹。（嚴版教材未給出，科大考綱涉及）*注：h(n)為卡特蘭數(shù)的第n項。計算方法為：hn=c2nnn+1（3）二叉樹的順序儲存與鏈式儲存結構順序存儲：約定用一組地址連續(xù)的存儲單元依次自上而下，自左至右存儲完全二叉樹上的結點元素，即將完全二叉樹上編號為i的結點元素存儲在一維數(shù)組中下標為i-1的分量中，以0表示不存在的結點，這種順序存儲結構僅適用于完全二叉樹。結構定義：#define maxsize 100/二叉樹最大結點數(shù)typedef telemtype sqbitreemaxsiz

42、e;/0號單元存儲根結點sqbitree bt;* 最壞情況：一個深度為k且只有k個結點的單支樹，需要長度為2k-1的一維數(shù)組鏈式存儲：二叉鏈表結點包含3個域，數(shù)據(jù)域和左、右指針域（三叉鏈表還增加了指向其雙親結點的parent指針域），鏈表的頭指針指向二叉樹的根結點，易證在含有n個結點的二叉鏈表中有n+1個空鏈域。結構定義：typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;bitnode,*bitree;（4）二叉樹的先序、中序、后序三種遍歷方式的關系以及實現(xiàn)；層序遍歷的實現(xiàn)先序遍歷：根左右若二叉樹非空，則先

43、訪問根結點，然后先序遍歷左子樹，最后先序遍歷右子樹（遞歸過程）/算法實現(xiàn)：先序遍歷的遞歸算法bool preordertraverse(bitree t,bool(*visit)(telemtype e)if(t)if(visit(t->data)if(preordertraverse(t->lchild,visit)if(preordertraverse(t->rchild,visit) return true;return false;else return true;/preordertraverse/先序建立二叉樹：按先序依次輸入二叉樹中結點的值，空格表示空樹bool

44、 createbitree(bitree &t)scanf(&ch);if(ch= ) t=null;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) return false;t->data=ch;createbitree(t->lchild);createbitree(t->rchild);return true;/createbitree中序遍歷：左根右若二叉樹非空，則先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹（遞歸過程）/算法實現(xiàn)：中序遍歷的非遞歸算法（棧實現(xiàn)）bool inordertraverse1

45、(bitree t,bool(*visit)(telemtype e)initstack(s);push(s,t); /根指針進棧while(!stackempty(s)while(gettop(s,p)&&p)push(s,p->lchild);/向左走到盡頭pop(s,p);/空指針退棧if(!stackempty(s)/訪問結點，向右一步pop(s,p);if(!visit(p->data) return false;push(s,p->rchild);/inordertraverse1return true;/inordertraverse/第2種非遞

46、歸算法bool inordertraverse2(bitree t,bool(*visit)(telemtype e)initstack(s);p=t;while(p|!stackempty(s)if(p)push(s,p);p=p->lchild;elsepop(s,p);if(!visit(p->data) return false;p=p->rchild;return true;/inodertraverse2后序遍歷：左右根若二叉樹非空，則先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問根結點（遞歸過程）/算法實現(xiàn)：后序遍歷的遞歸算法bool postordertrav

47、erse(bitree t,bool(*visit)(telemtype e)if(t)if(postordertraverse(t->lchild,visit)if(postordertraverse(t->rchild,visit)if(visit(t->data) return true;return false;else return true;/postordertraverse層次遍歷：從上到下、從左到右按層次遍歷二叉樹/算法描述（隊列實現(xiàn)）void levelordertraverse(bitree t,bool(*visit)(telemtype e)init

48、queue(q);p=t;visit(p->data);/ 訪問根節(jié)點enqueue(q,p);/根結點入隊while(p|!queueempty(q)dequeue(q,p);/隊頭元素出隊visit(p->data);/訪問當前節(jié)點if(p->lchild)enqueue(q,p->lchild);/若存在左孩子，左孩子進隊列if(p->rchild)enqueue(q,p->rchild);/若存在右孩子，右孩子進隊列/levelordertraverse由遍歷序列構造二叉樹：1) 先序遍歷中，第一個結點一定是二叉樹的根結點2) 中序遍歷中，根結點必然

49、將中序序列分割成兩個子序列3) 后序序列的最后一個結點一定是二叉樹的根結點4) 由二叉樹的遍歷能否唯一地確定一棵二叉樹先序中序后序層序先序××中序后序××層序××（5）線索二叉樹的基本概念與構造方法線索二叉樹：引入線索二叉樹的是為了加快查找結點前驅和后繼的速度規(guī)定：若結點有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅；若結點有右子樹，則其rchild域指示其右孩子，否則令rchild域指示其后繼。結點增加兩個標志域ltag和rtag，結點結構變?yōu)椋簂childltagdatartagrchild其中：ltag

50、= 0 lchild域指示結點的左孩子1 lchild域指示結點的前驅 rtag= 0 lchild域指示結點的右孩子1 lchild域指示結點的后繼結構定義：線索鏈表/指向結點前驅和后繼的指針叫做線索，加上線索的二叉樹稱為線索二叉樹/對typedef enum pointertaglink,thread;typedef struct bithrnodetelemtype data;struct bithrnode *lchild,*rchild;pointertag ltag,rtag;bithrnode,*bithrtree;線索二叉樹的構造：線索化的實質是將二叉鏈表中的空指針改為指向前驅

51、或后繼的線索，而前驅或后繼的信息只有遍歷時才能得到，因此，線索化的過程即為在遍歷的過程中修改空指針的過程。中序建立中序線索化鏈表：bool inorderthreading1(bitree &thrt,bithrtree t)/構造算法1/附設一個指針pre始終指向剛剛訪問過的結點/若指針p指向當前訪問的結點，則pre指向它的前驅if(!(thrt=(bithrtree)malloc(sizeof(bithrnode)return false;thrt->ltag=link;thrt->rtag=thread;thrt->rchild=thrt;if(!t) thrt

52、->lchild=thrt;elsethrt->lchild=t;pre=thrt;inthreading(t);pre->lchild=thrt;pre->rtag=thread;thrt->rchild=pre;return true;/inorderthreading1void inthreading(bithrtree p)/構造算法2if(p)inthreading(p->lchild);if(!p->lchild)p->ltag=thread;p->lchild=pre;if(!pre->rchild)pre->rtag=thread;pre->rchid=p;pre=p;inthreading(p->rchild);/inthreading* 中序線索樹中結點前驅的后繼的確定：根據(jù)中序遍歷的規(guī)律，結點的后繼應是遍