數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)要點

1、第一章 數(shù)據(jù)結(jié)構(gòu)概述基本概念與術(shù)語1數(shù)據(jù) ：數(shù)據(jù)是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被 計算機(jī)程序所處理的符號的總稱。2. 數(shù)據(jù)元素 ：數(shù)據(jù)元素是數(shù)據(jù)的基本單位， 是數(shù)據(jù)這個集合中的個體， 也稱之為元素， 結(jié)點， 頂點記錄。(補充：一個數(shù)據(jù)元素可由若干個 數(shù)據(jù)項 組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。 )3數(shù)據(jù)對象：數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。(有時候也叫做屬性。)4 數(shù)據(jù)結(jié)構(gòu) ：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。(1) 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的固有邏輯關(guān)系，常稱為數(shù) 據(jù)結(jié)構(gòu)。數(shù)據(jù)的

2、邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲無關(guān)，是 獨立于計算機(jī)的。依據(jù)數(shù)據(jù)元素之間的關(guān)系，可以把數(shù)據(jù)的邏輯結(jié)構(gòu)分成以下幾種：1. 集合 ：數(shù)據(jù)中的數(shù)據(jù)元素之間除了“同屬于一個集合“的關(guān)系以外，沒有其他關(guān)系。2. 線性結(jié)構(gòu) ：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對一“的關(guān)系。若結(jié)構(gòu)為非空集合，則除了第 一個元素之外，和最后一個元素之外，其他每個元素都只有一個直接前驅(qū)和一個直接后繼。3. 樹形結(jié)構(gòu) ：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對多“的關(guān)系。若數(shù)據(jù)為非空集，則除了第一 個元素 (根)之外，其它 每個數(shù)據(jù)元素都只有一個直接前驅(qū)， 以及多個或零個 直 接后繼。4. 圖狀結(jié)構(gòu) ：結(jié)構(gòu)中的數(shù)據(jù)

3、元素存在“多對多”的關(guān)系。若結(jié)構(gòu)為非空集，折每個數(shù)據(jù)可有 多個(或零個)直接后繼。(2) 數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 想要計算機(jī)處理數(shù)據(jù)， 就必須把數(shù)據(jù)的邏輯結(jié)構(gòu)映射為數(shù)據(jù)的存儲結(jié)構(gòu)。 邏輯結(jié)構(gòu)可以映射 為以下兩種存儲結(jié)構(gòu)：1. 順序存儲結(jié)構(gòu) ：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置也相鄰的存儲單元中，借助元素 在存儲器中的相對位置來表示數(shù)據(jù)之間的邏輯關(guān)系。2. 鏈?zhǔn)酱鎯Y(jié)構(gòu) ：借助指針表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系。 不要求邏輯上相鄰的數(shù)據(jù)元素物 理位置上也相鄰。5. 時間復(fù)雜度分析 ：1.常量階：算法的時間復(fù)雜度與問題規(guī)模n 無關(guān)系 T(n)=O(1)2

4、. 線性階：算法的時間復(fù)雜度與問題規(guī)模n 成線性關(guān)系 T(n)=O(n)3. 平方階和立方階：一般為 循環(huán)的嵌套 ，循環(huán)體最后條件為 i+ 時間復(fù)雜度的大小比較：O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )<O(n!)<O(n n)6. 算法與程序：(1)算法的 5 個特性1、輸入：有零個或多個輸入2、輸出：有一個或多個輸出3、有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個指令序 列的執(zhí)行在有限的時間內(nèi)結(jié)束。 (程序與算法的區(qū)別在于，程序不需要有有

5、窮性)4、確定性：算法中的每一個步驟都必須是確定的，而不應(yīng)當(dāng)含糊、模棱兩可。沒有歧義。5、可行性：算法中的每一個步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。(2).算法設(shè)計的要求：1、正確性(達(dá)到預(yù)期效果，滿足問題需求)2、健壯性(能處理合法數(shù)據(jù)，也能對不合法的數(shù)據(jù)作出反應(yīng)，不會產(chǎn)生不 可預(yù)期的后果)3、可讀性(要求算法易于理解，便于分析)4、可修改可擴(kuò)展性5、高效率(較好的時空性能)補充內(nèi)容：1、名詞解釋：數(shù)據(jù)結(jié)構(gòu)、二元組 數(shù)據(jù)結(jié)構(gòu)就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 二元組就是一種用來表示某個數(shù)據(jù)對象以及各個元素之間關(guān)系的有限集合。2、根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)的邏輯

6、結(jié)構(gòu)可以分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和 圖狀結(jié)構(gòu)四種類型。3、常見的數(shù)據(jù)存儲結(jié)構(gòu)一般有兩種類型，它們分別是順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)6. 在一般情況下，一個算法的時間復(fù)雜度是問題規(guī)模的函數(shù) 7常見時間復(fù)雜度有：常數(shù)階 0 (1 )、線性階0 (n)、對數(shù)階O (log 2 n)、平方階0(nA2)、 指數(shù)階0(2人n)。通常認(rèn)為，具有常數(shù)階量級的算法是好算法，而具有指數(shù)階量級的算法是 差算法。第二章 線性表定義：線性表是n個數(shù)據(jù)元素的有限序列。一個數(shù)據(jù)元素可由若干個 數(shù)據(jù)項組成。1. 順序表結(jié)構(gòu)線性表的順序存儲是指在內(nèi)存中 用地址連續(xù)的 一塊存儲空間順序存放線性表的各元素， 用這 種存儲形式存

7、儲的線性表稱為順序表。2. 單鏈表( 1 )鏈表結(jié)點結(jié)構(gòu)線性表中的數(shù)據(jù)元素可以 用任意的一組存儲單元 來存儲，用指針表示邏輯關(guān)系邏輯相鄰的兩 元素的存儲空間可以是不連續(xù)的。( 2)初始化：鏈表操作算法：初始化、插入、輸出、刪除、遍歷 p=(struct student *)malloc(sizeof(struct student);插入： p->next=head->next; head->next=p; 輸出： printf( “%d ”,p->data);刪除： q=p->next; p->next = q->next ; free(q); 結(jié)點遍

8、歷： for(p=head;p;p=p->next);補充內(nèi)容：1、線性表中，第一個元素沒有直接前驅(qū)，最后一個元素沒有直接后驅(qū)。2、 在一個單鏈表中，若p所指結(jié)點是q所指結(jié)點的前驅(qū)結(jié)點，則刪除結(jié)點q的操作語句為P->next = q->next ; free（q）;3、在長度為 N 的順序表中，插入一個新元素平均需要移動表中 N/2 個元素，刪除一個元素 平均需要移動（ N-1 ） /2 個元素。4、若線性表的主要操作是在最后一個元素之后插入一個元素或刪除最后一個元素，則采用 順序表 存儲結(jié)構(gòu)最節(jié)省運算時間。5、 已知順序表中每個元素占用3個存儲單元，第 13 個元素的存儲地

9、址為 336，則順序表的 首地址為 300。（第 n 個元素的地址即首地址 +（n-1）* 每個元素的存儲空間，如 a12 （第 13 個元素）的地址 =a0+12*3 ）6、 設(shè)有一帶頭結(jié)點單鏈表L,請編寫該單鏈表的初始化，插入、輸出和刪除函數(shù)。（函數(shù)名自定義）結(jié)點定義：typedef int datatype; /結(jié)點數(shù)據(jù)類型，假設(shè)為 inttypedef struct node /結(jié)點結(jié)構(gòu)datatype data;struct node *next;/ 雙向鏈表還應(yīng)加上 *previous Lnode, * pointer ; / 結(jié)點類型 ,結(jié)點指針類型 typedef pointe

10、r lklist; /單鏈表類型，即頭指針類型1. 初始化：lklist initlist() pointer head;head=new node;/這是 C+ 做法/head=( pointer)malloc(sizeof(Lnode);這是 C 語言做法head->next=NULL;/循環(huán)鏈表則是 head->next=head;/雙向鏈表應(yīng)加上 head->previos=NULL;return head;2插入：(C語言中需要把head轉(zhuǎn)化為全局變量才能實現(xiàn)此程序)int insert(lklist head,datatype x,int i)pointer q,

11、s;q=get(head,i-1); /找第 i-1 個點if(q=NULL)/無第 i-1 點，即 i<1 或 i>n+1 時cout<<"非法插入位置!n”這是C+做法，即C語言中的printf(非法插入位置!n”;return 0;s=new node;/ 生成新結(jié)點即 C 語言中的 s=( pointer)malloc(sizeof(Lnode);s->data=x;s->next=q->next;/新點的后繼是原第i 個點q->next=s;/原第 i-1 個點的后繼是新點return 1;/插入成功3刪除：(C語言中需要把h

12、ead轉(zhuǎn)化為全局變量才能實現(xiàn)此程序)int delete(lklist head,int i) pointer p,q;q=get(head,i-1);/找待刪點的直接前趨if(q=NULL | q->next=NULL)/即 i<1 或 i>n 時cout<< ”非法刪除位置 !n ” ;return 0;p=q->next;/保存待刪點地址q->next=p->next;/ 修改前趨的后繼指針delete p;/釋放結(jié)點即 C 語言中的 free(p);return 1;/刪除成1. 不帶頭結(jié)點的單鏈表 head 為空的判定條件是 (A )A

13、. head=NULLB.head->next=NULLC.head->next=head D. head!=NULL2. 帶頭結(jié)點的單鏈表 head 為空的判定條件是 (B )A.head=NULLB.head->next=NULLC.head->next=headD. head!=NULL3. 在一個單鏈表中，若 p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行(B )A.s->next=p; p->next=s;B. s->next=p->next; p->next=s;C. s->next=p->next; p=s

14、;D. p->next=s; s->next=p;4. 在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行(A )A. p->next=p->next->next;B. p=p->next; p->next=p->next->next;C. p->next=p->nextD. p=p->next->next5. 從一個具有 n 個結(jié)點的有序單鏈表中查找其值等于 x 結(jié)點時， 在查找成功的情況下， 需 平均比較( B )個結(jié)點。A. n B. n/2 C. (n-1)/2D. O(n log 2n)6. 給定有 n 個

15、元素的向量，建立一個有序單鏈表的時間復(fù)雜度(B)A.O(1)B.O(n)C.O(n2)D.O(n g 2n)7. 在一個具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是(B)A.O(1)B.O(n)C.O(n2)D.O(n g 2n)8. 在一個單鏈表中刪除 q 所指結(jié)點時，應(yīng)執(zhí)行如下操作： q=p->next;p->next=( p->next->next );free(q);/這種題目靠一根指針是沒有辦法完成的，必須要借助第二根指針。9. 在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點時，應(yīng)執(zhí)行：s->next=( p->next )

16、p->next=(s) 操作。10. 對于一個具有 n 個節(jié)點的單鏈表 ,在已知所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是（O（1）；在給定值為 x 的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是（O（n） ）。11. 問答題 線性表可用順序表或鏈表存儲。試問：（1） 兩種存儲表示各有哪些主要優(yōu)缺點 ?順序表的存儲效率高， 存取速度快。 但它的空間大小一經(jīng)定義， 在程序整個運行期間不會發(fā) 生改變，因此，不易擴(kuò)充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一 半（ 或近一半 ）元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運行過程中動態(tài)分配和釋放， 且只要存儲器中還有空 間，就不會產(chǎn)

17、生存儲溢出的問題。 同時在插入和刪除時不需要保持?jǐn)?shù)據(jù)元素原來的物理順序， 只需要保持原來的邏輯順序， 因此不必移動數(shù)據(jù)， 只需修改它們的鏈接指針， 修改效率較高。 但存取表中的數(shù)據(jù)元素時，只能循鏈順序訪問，因此存取效率不高。（2）若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素， 這時，應(yīng)采用哪種存儲表示？為什么？應(yīng)采用順序存儲表示。 因為順序存儲表示的存取速度快， 但修改效率低。 若表的總數(shù)基本穩(wěn) 定，且很少進(jìn)行插入和刪除， 但要求以最快的速度存取表中的元素， 這時采用順序存儲表示 較好。第三章 棧和隊列1. 棧（1）棧的結(jié)構(gòu)與定義 定義：限定僅在表尾進(jìn)行插入或刪除

18、操作的線性表。 結(jié)構(gòu)：/棧的容量 /棧頂指針 /棧底指針typedef struct list int listsize; struct list *head; struct list *base;（2） 順序棧操作算法：入棧、出棧、判斷?？盏龋ㄟ@個是使用數(shù)組進(jìn)行操作的，具體內(nèi) 容參照書本 P46-47 ）（3）鏈棧的結(jié)構(gòu)與定義2. 隊列（1） 隊列的定義 定義：只允許在表的一端進(jìn)行插入，而在另一端刪除元素。補充內(nèi)容：1、一個棧的入棧序列為“ ABCDE ”，則以下不可能的出棧序列是（ B）A. BCDAEB. EDACBC. BCADED. AEDCB2、棧的順序表示中，用 TOP 表示棧頂

19、元素，那么?？盏臈l件是（D）A. TOP=STACKSIZEB. TOP=1C. TOP=0D. TOP=-13、允許在一端插入，在另一端刪除的線性表稱為隊列。插入的一端為表頭，刪除的一端為 表尾。4、棧的特點是先進(jìn)后出，隊列的特點是先進(jìn)先出。5、對于棧和隊列，無論他們采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，進(jìn)行插入和刪除操作的 時間復(fù)雜度都是 O(1) (即與已有元素 N 無關(guān))。要求判6. 已知鏈棧Q,編寫函數(shù)判斷?？眨绻麠？談t進(jìn)行入棧操作，否則出棧并輸出。 斷?？?、出棧、入棧用函數(shù)實現(xiàn)) (詳看考點 2)7. 出隊與取隊頭元素的區(qū)別：出隊就是刪除對頭的數(shù)據(jù)元素，取隊頭元素是獲取對頭的數(shù)據(jù) 元

20、素值，不需要刪除。8. 鏈棧與順序棧相比，比較明顯的優(yōu)點是：( D)A.插入操作比較容易B.刪除操作比較容易C.不會出現(xiàn)棧空的情況D.不會出現(xiàn)棧滿的情況考點 1：隊列的編程：結(jié)構(gòu)：typedef struct QNodeint date;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;創(chuàng)建：LinkQueue InitQueue(LinkQueue Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); Q.front-&g

21、t;next=NULL;return (Q);入隊：LinkQueue EnQueue(LinkQueue Q,int e)QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode);p->date=e;p->next=NULL; Q.rear->next=p;Q.rear=p;return (Q);出隊：LinkQueue DeQueue(LinkQueue Q) int e; QueuePtr p;p=Q.front->next; e=p->date;Q.front=p->next; printf("%d"

22、;,e); if(Q.rear=p)Q.rear=Q.front=NULL; free(p);return (Q);考點 2：棧的編程：創(chuàng)建：struct list *creat()struct list *p;p=(struct list *)malloc(LEN); p->next=NULL;return(p);入棧：struct list *push(struct list *head,int a)struct list *p;p=(struct list *)malloc(LEN);p->num=a;p->next=head;return(p);出棧：struct l

23、ist *pop(struct list *head)struct list *p; p=head->next; free(head); return(p);判斷?？眨篿nt listempty(struct list *head) if(head->next)return 0; else return 1;第四章 串 （不是重點內(nèi)容）1.串是由零個或多個字符組成的有限序列2. 串的賦值： x= 'abc' 或 x = 'abc'第五章 數(shù)組和廣義表 （不是重點內(nèi)容）1. 多維數(shù)組中某數(shù)組元素的 position 求解。一般是給出數(shù)組元素的首元素地址

24、和每個元素占 用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置。2. 明確 按行存儲 和 按列存儲 的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲方式求解1 中類型的題。3. 將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角矩 陣，具有某種特點的稀疏矩陣等。 熟悉稀疏矩陣的三種不同存儲方式： 三元組 ，帶輔助行向 量的二元組， 十字鏈表 存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。補充內(nèi)容：三元組： 結(jié)構(gòu)：typedef structint i,j;int e;Triple;/元素行下標(biāo)及列下標(biāo)/元素值typedef stru

25、ctint mu,nu,tu;/矩陣的行數(shù)、列數(shù)、非零元素個數(shù)Triple dataMAXSIZE+1; /矩陣包含的三元組表， data0 未用 TSMatrix;十字鏈表：typedef struct OLNodeint i,j;/元素行下標(biāo)及列下標(biāo)int e;/ 元素值struct OLNode *right,*down; OLNode ， *OLink;typedef structint mu,nu,tu;OLink *rhead,*chead; CrossList;/行的后繼以及列的后繼/矩陣的行數(shù)、列數(shù)、非零元素個數(shù)/行和列的表頭指針組的首地址CrossList Creat ( C

26、rossList M)int m,n,t;scanf(“%d%d%d ”,&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;M.rhead=( OLink *)malloc(m+1)*sizeof(OLink);/開辟行表頭指針組M.chead=( OLink *)malloc(n+1)*sizeof(OLink);/ 開辟行列頭指針組M.rhead=M.chead=NULL;/初始化接下來就是賦值和入鏈第六章 樹和二叉樹1 樹(1) 樹的概念及術(shù)語樹：n (n>0)個結(jié)點的有限集合。當(dāng) n = 0時，稱為空樹；任意一棵非空樹滿足以下條件： 有且僅有一

27、個特定的稱為根的結(jié)點； 當(dāng)n > 1時，除根結(jié)點之外的其余結(jié)點被分成m ( m>0 )個互不相交的有限集合T1,T2,，Tm，其中每個集合又是一棵樹，并稱為這個根結(jié)點的子樹。(2) 結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)。 樹的度：樹中所有結(jié)點的度的最大值。(3) 葉子結(jié)點：度為 0 的結(jié)點，也稱為終端結(jié)點。分支結(jié)點：度不為 0 的結(jié)點，也稱為非終端結(jié)點。(4) 孩子、雙親：樹中某結(jié)點的子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點，這個結(jié)點稱為它 孩子結(jié)點的雙親結(jié)點；兄弟：具有同一個雙親的孩子結(jié)點互稱為兄弟。(5) 路徑：如果樹的結(jié)點序列 n 1, n2,，nk有如下關(guān)系：結(jié)點ni是ni+1的雙親

28、(1<=i<k ), 則把 n1, n2, , nk 稱為一條由 n1 至 nk 的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。(6) 祖先、子孫：在樹中，如果有一條路徑從結(jié)點x到結(jié)點y，那么x就稱為y的祖先， 而 y 稱為 x 的子孫。(7) 結(jié)點所在層數(shù)：根結(jié)點的層數(shù)為1；對其余任何結(jié)點，若某結(jié)點在第 k 層，則其孩子 結(jié)點在第 k+1 層。樹的深度：樹中所有結(jié)點的最大層數(shù)，也稱高度。(8) 層序編號：將樹中結(jié)點按照從上層到下層、同層從左到右的次序依次給他們編以從1 開始的連續(xù)自然數(shù)。(9) 有序樹、無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的，稱這棵樹為有序 樹；反之，稱為

29、無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹( 10 )樹通常有前序(根)遍歷、后序(根)遍歷和層序(次)遍歷三種方式(樹， 不是二叉樹，沒中序遍歷。 )2 二叉樹(1) 二叉樹的定義：二叉樹是n (n > 0)個結(jié)點的有限集合，該集合或者為空集(稱為空二叉樹)，或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉 樹組成。滿二叉樹： 在一棵二叉樹中， 如果所有分支結(jié)點都存在左子樹和右子樹， 并且所有葉子都在 同一層上。(滿二叉樹的特點：葉子只能出現(xiàn)在最下一層；只有度為 0和度為 2 的結(jié)點。)完全二叉樹：對一棵具有n個結(jié)點的二叉樹按層序編號，如果編號為i (1 < i

30、 w n)的結(jié)點與同樣深度的滿二叉樹中編號為 i 的結(jié)點在二叉樹中的位置完全相同。完全二叉樹的特點：1. 在滿二叉樹中，從最后一個結(jié)點開始，連續(xù)去掉任意個結(jié)點，即是一棵完全二叉樹。2. 葉子結(jié)點只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點都集中在二叉樹的左部；3. 完全二叉樹中如果有度為 1 的結(jié)點，只可能有一個，且該結(jié)點只有左孩子。4. 深度為 k 的完全二叉樹在 k-1 層上一定是滿二叉樹。(3) 二叉樹的性質(zhì)：性質(zhì)1: 二叉樹的第i層上最多有2i-1個結(jié)點(i > 1)。性質(zhì)2: 一棵深度為k的二叉樹中，最多有 2k-1個結(jié)點，最少有 k個結(jié)點。深度為k 且具有 2k-1 個結(jié)點的二叉樹

31、一定是滿二叉樹性質(zhì)3:在一棵二叉樹中，如果葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2,則有：nO= n21。(一個結(jié)點的度就是指它放出的射線)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為Iog2n +1。性質(zhì) 5: 對一棵具有 n 個結(jié)點的完全二叉樹中從 1 開始按層序編號，則對于任意的序 號為i (1w i w n)的結(jié)點(簡稱為結(jié)點i),有：(1) 如果i > 1,則結(jié)點i的雙親結(jié)點的序號為i/2 ;如果i = 1，則結(jié)點i是根結(jié)點，無雙 親結(jié)點。(2) 如果2i w n,則結(jié)點i的左孩子的序號為 2i;如果2i > n,則結(jié)點i無左孩子。(3) 如果2i + 1 w n,則結(jié)點i的右

32、孩子的序號為 2i + 1;如果2i + 1 > n,則結(jié)點i無右孩子。3 二叉樹的遍歷(遞歸調(diào)用與訪問的順序不同而產(chǎn)生不同的遍歷方法)( 1 ) 先序遍歷void XianXu(BiTree T)if(T)printf("%c",T->data);/先訪問XianXu(T->IchiId);/再繼續(xù)遍歷XianXu(T->rchiId);( 2 )中序遍歷( 3)后序遍歷4. 森林與二叉樹的轉(zhuǎn)換( 1)同級以左為親,即左一結(jié)點的右孩子是與它同級的右一結(jié)點(2) 只認(rèn)最左路線為親子路線,即結(jié)點的左孩子是它下一級結(jié)點的最左的元素5. 哈夫曼樹( 1 )

33、哈夫曼樹的基本概念：哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點，帶權(quán)路徑長度最小的二叉樹。（2）哈夫曼樹的特點：1. 權(quán)值越大的葉子結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉子結(jié)點越遠(yuǎn)離根結(jié)點。2. 只有度為0 （葉子結(jié)點）和度為 2 （分支結(jié)點）的結(jié)點，不存在度為1的結(jié)點.（3 ）哈夫曼樹的構(gòu)造算法思想及構(gòu)造過程（森林與哈夫曼編碼）就是求各權(quán)值和路徑相乘之后疊加的最小值。1、已知一棵完全二二叉樹有47個結(jié)點，則該二叉樹有（C）個葉子結(jié)點。A. 6B. 12C. 24D.48解法如下：1+2+4+8+16=31計算從第一層到n-1層的結(jié)點個數(shù)47-31=16計算第n層的葉子結(jié)點個數(shù)16-16/2=8計算第n-1層的葉子結(jié)點個數(shù)所以，葉子結(jié)點數(shù)=16+8=24 計算第n層和第n-1層的總?cè)~子結(jié)點數(shù)2、已知遍歷一棵二叉樹的前序序列ABCDEFG和中序序列 CBEDAFG，那