數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)要點(diǎn)(整理版)講課講稿

1、資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除第一章數(shù)據(jù)結(jié)構(gòu)概述基本概念與術(shù)語1 數(shù)據(jù) ：數(shù)據(jù)是對客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序所處理的符號(hào)的總稱。2.數(shù)據(jù)元素 ：數(shù)據(jù)元素是數(shù)據(jù)的基本單位， 是數(shù)據(jù)這個(gè)集合中的個(gè)體， 也稱之為元素， 結(jié)點(diǎn)，頂點(diǎn)記錄。（補(bǔ)充：一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng) 組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。）3數(shù)據(jù)對象：數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。（有時(shí)候也叫做屬性。）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)

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

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

4、算法的時(shí)間復(fù)雜度與問題規(guī)模n 成線性關(guān)系T(n)=O(n)3.平方階和立方階：一般為 循環(huán)的嵌套 ，循環(huán)體最后條件為 i+ 時(shí)間復(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)word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除6.算法與程序：（1）算法的5 個(gè)特性1、 輸入：有零個(gè)或多個(gè)輸入2、 輸出：有一個(gè)或多個(gè)輸出3、有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個(gè)指令序列的執(zhí)行在有限的時(shí)間內(nèi)結(jié)束。 （

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

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

7、線性表的各元素， 用這種存儲(chǔ)形式存儲(chǔ)的線性表稱為順序表。2. 單鏈表（1）鏈表結(jié)點(diǎn)結(jié)構(gòu)線性表中的數(shù)據(jù)元素可以 用任意的一組存儲(chǔ)單元 來存儲(chǔ)，用指針表示邏輯關(guān)系邏輯相鄰的兩元素的存儲(chǔ)空間可以是不連續(xù)的。（ 2） 鏈表操作算法：初始化、插入、輸出、刪除、遍歷初始化： p=(struct student *)malloc(sizeof(struct student);word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除插入：p->next=head->next;head->next=p;輸出： printf( “%d”,p->data);刪除： q=p->next;p

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

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

10、類型 ,結(jié)點(diǎn)指針類型typedef pointer 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)化為全局變量才能實(shí)現(xiàn)此程序）int insert(lklist head,da

11、tatype x,int i)pointer q,s;q=get(head,i-1);/找第 i-1 個(gè)點(diǎn)if(q=NULL)/無第 i-1 點(diǎn)，即 i<1 或 i>n+1 時(shí)cout<< ”非法插入位置 !n”; /這是 C+ 做法，即 C 語言中的 printf( “非法插入位置 !n”); return 0;word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除s=new node;/ 生成新結(jié)點(diǎn)即 C 語言中的s=( pointer)malloc(sizeof(Lnode);s->data=x;s->next=q->next;/新點(diǎn)的后繼是原第

12、i 個(gè)點(diǎn)q->next=s;/原第 i-1 個(gè)點(diǎn)的后繼是新點(diǎn)return 1;/插入成功3.刪除：（C 語言中需要把head 轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）int delete(lklist head,int i) pointer p,q;q=get(head,i-1);/找待刪點(diǎn)的直接前趨if(q=NULL | q->next=NULL)/即 i<1 或 i>n 時(shí)cout<< ”非法刪除位置!n ” ;return 0;p=q->next;/保存待刪點(diǎn)地址q->next=p->next;/ 修改前趨的后繼指針delete p;/釋放結(jié)點(diǎn)

13、即 C 語言中的free(p);return 1;/刪除成1. 不帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是 (A )A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL2. 帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是 (B )A.head=NULL B.head->next=NULL C. head->next=head D. head!=NULL3.在一個(gè)單鏈表中，若p 所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p 之后插入 s 所指結(jié)點(diǎn)，則執(zhí)行 (B )A.s->next=p; p->next=s;B.s

14、->next=p->next;p->next=s;C.s->next=p->next; p=s;D.p->next=s; s->next=p;4.在一個(gè)單鏈表中，若刪除p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(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. 從一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中查找其值等于x 結(jié)點(diǎn)時(shí)， 在查找成功的情況下，需

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

16、 p 所指結(jié)點(diǎn)之后插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行：s->next=( p->next )p->next=(s) 操作。word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除10. 對于一個(gè)具有n 個(gè)節(jié)點(diǎn)的單鏈表,在已知所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O（1） )；在給定值為x 的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是（O(n) ）。11.問答題線性表可用順序表或鏈表存儲(chǔ)。試問：(1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?順序表的存儲(chǔ)效率高， 存取速度快。 但它的空間大小一經(jīng)定義， 在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均

17、需要移動(dòng)一半( 或近一半 )元素，修改效率不高。鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過程中動(dòng)態(tài)分配和釋放，且只要存儲(chǔ)器中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出的問題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動(dòng)數(shù)據(jù)， 只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序訪問，因此存取效率不高。(2) 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？應(yīng)采用順序存儲(chǔ)表示。 因?yàn)轫樞虼鎯?chǔ)表示的存取速度快， 但修改效率低。 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除， 但要求以最快的

18、速度存取表中的元素， 這時(shí)采用順序存儲(chǔ)表示較好。第三章棧和隊(duì)列1. 棧（ 1）棧的結(jié)構(gòu)與定義定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。結(jié)構(gòu)：typedefstruct listint listsize;/ 棧的容量struct list *head;/棧頂指針struct list *base;/棧底指針（ 2） 順序棧操作算法：入棧、出棧、判斷?？盏龋ㄟ@個(gè)是使用數(shù)組進(jìn)行操作的，具體內(nèi)容參照書本 P46-47 ）（ 3）鏈棧的結(jié)構(gòu)與定義2. 隊(duì)列（ 1）隊(duì)列的定義定義：只允許在表的一端進(jìn)行插入，而在另一端刪除元素。-補(bǔ)充內(nèi)容：1、一個(gè)棧的入棧序列為“ABCDE ”，則以下不可能的出棧序列是

19、（B）A. BCDAEB. EDACBC. BCADED. AEDCB2、棧的順序表示中，用TOP 表示棧頂元素，那么?？盏臈l件是（D ）A. TOP=STACKSIZEB. TOP=1C. TOP=0D. TOP=-1word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除3、允許在一端插入，在另一端刪除的線性表稱為隊(duì)列。插入的一端為表頭，刪除的一端為表尾。4、棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。5、對于棧和隊(duì)列，無論他們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是 O(1) （即與已有元素 N 無關(guān)）。6、已知鏈棧 Q，編寫函數(shù)判斷?？?，如果?？談t進(jìn)行入棧操作，

20、否則出棧并輸出。 （要求判斷棧空、出棧、入棧用函數(shù)實(shí)現(xiàn)） （詳看考點(diǎn) 2）7.出隊(duì)與取隊(duì)頭元素的區(qū)別：出隊(duì)就是刪除對頭的數(shù)據(jù)元素，取隊(duì)頭元素是獲取對頭的數(shù)據(jù)元素值，不需要?jiǎng)h除。8.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是：（ D）A. 插入操作比較容易B.刪除操作比較容易C.不會(huì)出現(xiàn)?？盏那闆rD.不會(huì)出現(xiàn)棧滿的情況考點(diǎn) 1：隊(duì)列的編程：結(jié)構(gòu)：typedef struct QNodeint date;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;創(chuàng)建：LinkQueue I

21、nitQueue(LinkQueue Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);Q.front->next=NULL;return (Q);入隊(duì)：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);出隊(duì)：word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除LinkQueue DeQueue(Li

22、nkQueue Q)int e;QueuePtr p;p=Q.front->next;e=p->date;Q.front=p->next;printf("%d",e);if(Q.rear=p)Q.rear=Q.front=NULL;free(p);return (Q);考點(diǎn) 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

23、a)struct list *p;p=(struct list *)malloc(LEN);p->num=a;p->next=head;return(p);出棧：struct list *pop(struct list *head)struct list *p;p=head->next;free(head);return(p);判斷?？眨簑ord 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除int listempty(struct list *head)if(head->next)return 0;else return 1;第四章串 （不是重點(diǎn)內(nèi)容）1.串是由零個(gè)或多

24、個(gè)字符組成的有限序列2.串的賦值： x= abc;或 x = abc;第五章數(shù)組和廣義表（不是重點(diǎn)內(nèi)容）1. 多維數(shù)組中某數(shù)組元素的 position 求解。一般是給出數(shù)組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。2. 明確 按行存儲(chǔ) 和按列存儲(chǔ) 的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲(chǔ)方式求解1 中類型的題。3. 將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。 熟悉稀疏矩陣的三種不同存儲(chǔ)方式： 三元組 ，帶輔助行向量的二元組，十字鏈表 存儲(chǔ)。掌握將稀疏矩陣的三元組或二

25、元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。補(bǔ)充內(nèi)容：三元組：結(jié)構(gòu)：typedef structint i,j;/元素行下標(biāo)及列下標(biāo)int e;/ 元素值Triple;typedef structint mu,nu,tu;/ 矩陣的行數(shù)、列數(shù)、非零元素個(gè)數(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 m

26、u,nu,tu;/ 矩陣的行數(shù)、列數(shù)、非零元素個(gè)數(shù)OLink*rhead,*chead;/ 行和列的表頭指針組的首地址CrossList;word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除CrossList Creat （ CrossList 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);/ 開辟行列

27、頭指針組M.rhead=M.chead=NULL;/初始化 /接下來就是賦值和入鏈第六章樹和二叉樹1 樹（1）樹的概念及術(shù)語樹： n（ n0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n 0 時(shí)，稱為空樹；任意一棵非空樹滿足以下條件： 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；當(dāng)n 1 時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（ m>0 ）個(gè)互不相交的有限集合T1,T2,Tm ，其中每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的子樹。（ 2） 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。樹的度：樹中所有結(jié)點(diǎn)的度的最大值。（ 3） 葉子結(jié)點(diǎn)：度為 0 的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為 0 的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。（ 4）孩子、雙親：樹

28、中某結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。（ 5）路徑： 如果樹的結(jié)點(diǎn)序列 n1, n2, , nk 有如下關(guān)系： 結(jié)點(diǎn) ni 是 ni+1 的雙親（ 1<=i<k ），則把 n1, n2, , nk 稱為一條由 n1 至 nk 的路徑；路徑上經(jīng)過的邊的個(gè)數(shù)稱為路徑長度。（6）祖先、子孫：在樹中，如果有一條路徑從結(jié)點(diǎn)x 到結(jié)點(diǎn) y，那么 x 就稱為 y 的祖先，而 y 稱為 x 的子孫。（7）結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k 層，則其孩子結(jié)點(diǎn)在第 k+1層。樹的深度：樹中所

29、有結(jié)點(diǎn)的最大層數(shù)，也稱高度。（8）層序編號(hào)：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。（ 9）有序樹、無序樹：如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹（ 10）樹通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式（樹，不是二叉樹，沒中序遍歷。 )2 二叉樹（ 1）二叉樹的定義：二叉樹是 n（ n 0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)

30、站刪除滿二叉樹： 在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。（滿二叉樹的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0 和度為 2 的結(jié)點(diǎn)。）完全二叉樹：對一棵具有n 個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i（1 i n）的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i 的結(jié)點(diǎn)在二叉樹中的位置完全相同。完全二叉樹的特點(diǎn)：1.在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹。2.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左部；3. 完全二叉樹中如果有度為 1 的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。4. 深度為 k 的完全二叉樹在

31、k-1 層上一定是滿二叉樹。（ 3）二叉樹的性質(zhì)：性質(zhì) 1：二叉樹的第i 層上最多有2i-1 個(gè)結(jié)點(diǎn)（ i 1）。性質(zhì) 2： 一棵深度為k 的二叉樹中，最多有2k-1 個(gè)結(jié)點(diǎn)，最少有k 個(gè)結(jié)點(diǎn)。深度為k且具有 2k-1 個(gè)結(jié)點(diǎn)的二叉樹一定是滿二叉樹性質(zhì) 3：在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為 2 的結(jié)點(diǎn)數(shù)為n2，則有 : n0 n21。（一個(gè)結(jié)點(diǎn)的度就是指它放出的射線）性質(zhì) 4：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。性質(zhì) 5： 對一棵具有n 個(gè)結(jié)點(diǎn)的完全二叉樹中從1 開始按層序編號(hào)，則對于任意的序號(hào)為 i（ 1 i n）的結(jié)點(diǎn)（簡稱為結(jié)點(diǎn)i ），有：（1）如果 i 1，則

32、結(jié)點(diǎn) i 的雙親結(jié)點(diǎn)的序號(hào)為i/2 ；如果 i 1，則結(jié)點(diǎn) i 是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。（2）如果 2i n，則結(jié)點(diǎn) i 的左孩子的序號(hào)為2i；如果 2i n，則結(jié)點(diǎn) i 無左孩子。（3）如果 2i 1 n，則結(jié)點(diǎn) i 的右孩子的序號(hào)為2i 1；如果 2i 1 n，則結(jié)點(diǎn) i 無右孩子。3 二叉樹的遍歷（遞歸調(diào)用與訪問的順序不同而產(chǎn)生不同的遍歷方法）（1）先序遍歷void XianXu(BiTree T)if(T)printf("%c",T->data);/先訪問XianXu(T->lchild);/再繼續(xù)遍歷XianXu(T->rchild);（ 2）中序

33、遍歷（ 3）后序遍歷4. 森林與二叉樹的轉(zhuǎn)換（ 1）同級(jí)以左為親，即左一結(jié)點(diǎn)的右孩子是與它同級(jí)的右一結(jié)點(diǎn)（ 2）只認(rèn)最左路線為親子路線，即結(jié)點(diǎn)的左孩子是它下一級(jí)結(jié)點(diǎn)的最左的元素5. 哈夫曼樹（1）哈夫曼樹的基本概念：word 可編輯資料收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長度最小的二叉樹。（2）哈夫曼樹的特點(diǎn)：1. 權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2. 只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1 的結(jié)點(diǎn) .（3）哈夫曼樹的構(gòu)造算法思想及構(gòu)造過程（森林與哈夫曼編碼 ）就是求各權(quán)值和路徑相乘之后疊加的最小值。-1、已知一棵完全二叉樹有47 個(gè)結(jié)點(diǎn)，則該二叉樹有（C）個(gè)葉子結(jié)點(diǎn)。A. 6B. 12C. 24D.48解法如下：1+2+4+8+16=31計(jì)算從第一層到n-1 層的結(jié)點(diǎn)個(gè)數(shù)47-31=16計(jì)算第 n 層的葉子結(jié)點(diǎn)個(gè)數(shù)16-16/2=8計(jì)算第 n-1 層的葉子結(jié)點(diǎn)個(gè)數(shù)所以，葉子結(jié)點(diǎn)數(shù)=16+8=24計(jì)算第 n 層和第 n-1 層的總?cè)~子結(jié)點(diǎn)數(shù)2、已知遍歷一棵二叉樹的前序序列ABCDEFG和中序序列CBEDAFG ，那么是下面哪棵樹（C ）。C 圖如下：ABFCDGE4、完全二叉樹必須滿足的條件為 : ：一棵具