數(shù)據(jù)結(jié)構(gòu) 知識點(diǎn)梳理匯總

第一章 數(shù)據(jù)結(jié)構(gòu)概述基本概念與術(shù)語1．?dāng)?shù)據(jù)：數(shù)據(jù)是對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序所處理的符號的總稱。2.數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個集合中的個體，也稱之為元素，結(jié)點(diǎn)，頂點(diǎn)記錄。（補(bǔ)充：一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。）3．?dāng)?shù)據(jù)對象：數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。（有時候也叫做屬性。）4．?dāng)?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ù)的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計(jì)算機(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ù)元素存在“多對多”的關(guān)系。若結(jié)構(gòu)為非空集，折每個數(shù)據(jù)可有多個（或零個）直接后繼。（2）數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。想要計(jì)算機(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.線性階：算法的時間復(fù)雜度與問題規(guī)模n成線性關(guān)系T(n)=O(n)3.平方階和立方階：一般為循環(huán)的嵌套，循環(huán)體最后條件為i++時間復(fù)雜度的大小比較：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)6.算法與程序：（1）算法的5個特性1、輸入：有零個或多個輸入2、輸出：有一個或多個輸出3、有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個指令序列的執(zhí)行在有限的時間內(nèi)結(jié)束。（程序與算法的區(qū)別在于，程序不需要有有窮性）4、確定性：算法中的每一個步驟都必須是確定的，而不應(yīng)當(dāng)含糊、模棱兩可。沒有歧義。5、可行性：算法中的每一個步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。（2）.算法設(shè)計(jì)的要求：1、正確性（達(dá)到預(yù)期效果，滿足問題需求）2、健壯性（能處理合法數(shù)據(jù)，也能對不合法的數(shù)據(jù)作出反應(yīng)，不會產(chǎn)生不可預(yù)期的后果）3、可讀性（要求算法易于理解，便于分析）4、可修改可擴(kuò)展性5、高效率（較好的時空性能）補(bǔ)充內(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ù)的邏輯結(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ù)階O（1）、線性階O（n）、對數(shù)階O（log2n）、平方階O(n^2)、指數(shù)階O(2^n)。通常認(rèn)為，具有常數(shù)階量級的算法是好算法，而具有指數(shù)階量級的算法是差算法。第二章 線性表定義：線性表是n個數(shù)據(jù)元素的有限序列。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)組成。1. 順序表結(jié)構(gòu)線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱為順序表。2. 單鏈表（1） 鏈表結(jié)點(diǎn)結(jié)構(gòu)線性表中的數(shù)據(jù)元素可以用任意的一組存儲單元來存儲，用指針表示邏輯關(guān)系邏輯相鄰的兩元素的存儲空間可以是不連續(xù)的。（2） 鏈表操作算法：初始化、插入、輸出、刪除、遍歷初始化：p=(structstudent*)malloc(sizeof(structstudent));插入：p->next=head->next;head->next=p;輸出：printf(“%d”,p->data);刪除：q=p->next;p->next=q->next;free(q);結(jié)點(diǎn)遍歷：for(p=head;p;p=p->next);補(bǔ)充內(nèi)容：1、線性表中，第一個元素沒有直接前驅(qū)，最后一個元素沒有直接后驅(qū)。2、在一個單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除結(jié)點(diǎn)q的操作語句為P->next=q->next;free(q);3、在長度為N的順序表中，插入一個新元素平均需要移動表中N/2個元素，刪除一個元素平均需要移動（N-1）/2個元素。4、若線性表的主要操作是在最后一個元素之后插入一個元素或刪除最后一個元素，則采用順序表存儲結(jié)構(gòu)最節(jié)省運(yùn)算時間。5、已知順序表中每個元素占用3個存儲單元，第13個元素的存儲地址為336，則順序表的首地址為300。（第n個元素的地址即首地址+(n-1)*每個元素的存儲空間，如a[12]（第13個元素）的地址=a[0]+12*3）6、設(shè)有一帶頭結(jié)點(diǎn)單鏈表L，請編寫該單鏈表的初始化，插入、輸出和刪除函數(shù)。（函數(shù)名自定義）結(jié)點(diǎn)定義：typedefintdatatype; //結(jié)點(diǎn)數(shù)據(jù)類型，假設(shè)為inttypedefstructnode{ //結(jié)點(diǎn)結(jié)構(gòu)datatypedata;structnode*next;//雙向鏈表還應(yīng)加上*previous}Lnode,*pointer;//結(jié)點(diǎn)類型,結(jié)點(diǎn)指針類型typedefpointerlklist; //單鏈表類型，即頭指針類型1.初始化：lklistinitlist(){pointerhead;head=newnode;//這是C++做法//head=(pointer)malloc(sizeof(Lnode));這是C語言做法head->next=NULL;//循環(huán)鏈表則是head->next=head;//雙向鏈表應(yīng)加上head->previos=NULL;returnhead;}2.插入：（C語言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）intinsert(lklisthead,datatypex,inti){pointerq,s;q=get(head,i-1); //找第i-1個點(diǎn)if(q==NULL) //無第i-1點(diǎn)，即i<1或i>n+1時{cout<<”非法插入位置!\n”;//這是C++做法，即C語言中的printf(“非法插入位置!\n”);return0;}s=newnode;//生成新結(jié)點(diǎn)即C語言中的s=(pointer)malloc(sizeof(Lnode));s->data=x;s->next=q->next;//新點(diǎn)的后繼是原第i個點(diǎn)q->next=s; //原第i-1個點(diǎn)的后繼是新點(diǎn)return1; //插入成功}3.刪除：（C語言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）intdelete(lklisthead,inti){pointerp,q;q=get(head,i-1); //找待刪點(diǎn)的直接前趨if(q==NULL||q->next==NULL) //即i<1或i>n時{cout<<”非法刪除位置!\n”;return0;}p=q->next; //保存待刪點(diǎn)地址q->next=p->next; //修改前趨的后繼指針deletep; //釋放結(jié)點(diǎn)即C語言中的free(p);return1; //刪除成1. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(A)A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL2. 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(B)A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL3. 在一個單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行(B)A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;4. 在一個單鏈表中，若刪除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. 從一個具有n個結(jié)點(diǎn)的有序單鏈表中查找其值等于x結(jié)點(diǎn)時，在查找成功的情況下，需平均比較（B）個結(jié)點(diǎn)。A.nB.n/2C.(n-1)/2D.O(n㏒2n)6. 給定有n個元素的向量，建立一個有序單鏈表的時間復(fù)雜度（B）A.O(1)B.O(n)C.O(n2)D.O(n㏒2n)7.在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然有序的時間復(fù)雜度是(B)A.O(1)B.O(n)C.O(n2)D.O(n㏒2n)8.在一個單鏈表中刪除q所指結(jié)點(diǎn)時，應(yīng)執(zhí)行如下操作：q=p->next;p->next=(p->next->next);free(q);//這種題目靠一根指針是沒有辦法完成的，必須要借助第二根指針。9.在一個單鏈表中p所指結(jié)點(diǎn)之后插入一個s所指結(jié)點(diǎn)時，應(yīng)執(zhí)行：s->next=(p->next)p->next=(s)操作。10.對于一個具有n個節(jié)點(diǎn)的單鏈表,在已知所指結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度是(O（1）)；在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度是（O(n)）。11.問答題線性表可用順序表或鏈表存儲。試問：(1)兩種存儲表示各有哪些主要優(yōu)缺點(diǎn)?順序表的存儲效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個運(yùn)行期間不會發(fā)生改變，因此，不易擴(kuò)充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一半(或近一半)元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運(yùn)行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產(chǎn)生存儲溢出的問題。同時在插入和刪除時不需要保持?jǐn)?shù)據(jù)元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時，只能循鏈順序訪問，因此存取效率不高。(2)若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時，應(yīng)采用哪種存儲表示？為什么？應(yīng)采用順序存儲表示。因?yàn)轫樞虼鎯Ρ硎镜拇嫒∷俣瓤?，但修改效率低。若表的總?shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時采用順序存儲表示較好。第三章 棧和隊(duì)列1. 棧（1） 棧的結(jié)構(gòu)與定義定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。結(jié)構(gòu)：typedefstructlist{intlistsize;//棧的容量structlist*head;//棧頂指針structlist*base;//棧底指針}（2） 順序棧操作算法：入棧、出棧、判斷棧空等（這個是使用數(shù)組進(jìn)行操作的，具體內(nèi)容參照書本P46-47）（3） 鏈棧的結(jié)構(gòu)與定義2. 隊(duì)列（1） 隊(duì)列的定義定義：只允許在表的一端進(jìn)行插入，而在另一端刪除元素。----------------------------------------------------------------------------------------------------------------補(bǔ)充內(nèi)容：1、一個棧的入棧序列為“ABCDE”，則以下不可能的出棧序列是（B）A.BCDAE B.EDACB C.BCADE D.AEDCB2、棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是（D）A.TOP==STACKSIZE B.TOP==1 C.TOP==0 D.TOP==-13、允許在一端插入，在另一端刪除的線性表稱為隊(duì)列。插入的一端為表頭，刪除的一端為表尾。4、棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。5、對于棧和隊(duì)列，無論他們采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，進(jìn)行插入和刪除操作的時間復(fù)雜度都是O(1)（即與已有元素N無關(guān)）。6、已知鏈棧Q，編寫函數(shù)判斷?？?，如果?？談t進(jìn)行入棧操作，否則出棧并輸出。（要求判斷?？铡⒊鰲?、入棧用函數(shù)實(shí)現(xiàn)）（詳看考點(diǎn)2）7.出隊(duì)與取隊(duì)頭元素的區(qū)別：出隊(duì)就是刪除對頭的數(shù)據(jù)元素，取隊(duì)頭元素是獲取對頭的數(shù)據(jù)元素值，不需要刪除。8.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是：（D）A.插入操作比較容易B.刪除操作比較容易C.不會出現(xiàn)?？盏那闆rD.不會出現(xiàn)棧滿的情況考點(diǎn)1：隊(duì)列的編程：結(jié)構(gòu)：typedefstructQNode{intdate;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;創(chuàng)建：LinkQueueInitQueue(LinkQueueQ){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));Q.front->next=NULL;return(Q);}入隊(duì)：LinkQueueEnQueue(LinkQueueQ,inte){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p->date=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return(Q);}出隊(duì)：LinkQueueDeQueue(LinkQueueQ){inte;QueuePtrp;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)建：structlist*creat(){structlist*p;p=(structlist*)malloc(LEN);p->next=NULL;return(p);}入棧：structlist*push(structlist*head,inta){structlist*p;p=(structlist*)malloc(LEN);p->num=a;p->next=head;return(p);}出棧：structlist*pop(structlist*head){structlist*p;p=head->next;free(head);return(p);}判斷?？眨篿ntlistempty(structlist*head){if(head->next)return0;elsereturn1;}第四章串（不是重點(diǎn)內(nèi)容）1.串是由零個或多個字符組成的有限序列2.串的賦值：x=’abc’;或x[]=’abc’;第五章數(shù)組和廣義表（不是重點(diǎn)內(nèi)容）1.多維數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個元素所在的位置。2.明確按行存儲和按列存儲的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲方式求解1中類型的題。3.將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。補(bǔ)充內(nèi)容：三元組：結(jié)構(gòu)：typedefstruct{inti,j;//元素行下標(biāo)及列下標(biāo)inte;//元素值}Triple;typedefstruct{intmu,nu,tu;//矩陣的行數(shù)、列數(shù)、非零元素個數(shù)Tripledata[MAXSIZE+1];//矩陣包含的三元組表，data[0]未用}TSMatrix;十字鏈表：typedefstructOLNode{inti,j;//元素行下標(biāo)及列下標(biāo)inte;//元素值structOLNode*right,*down;//行的后繼以及列的后繼}OLNode，*OLink;typedefstruct{intmu,nu,tu;//矩陣的行數(shù)、列數(shù)、非零元素個數(shù)OLink*rhead,*chead;//行和列的表頭指針組的首地址}CrossList;CrossListCreat（CrossListM）{intm,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é)點(diǎn)的有限集合。當(dāng)n＝0時，稱為空樹；任意一棵非空樹滿足以下條件：⑴有且僅有一個特定的稱為根的結(jié)點(diǎn)；⑵當(dāng)n＞1時，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m>0）個互不相交的有限集合T1,T2,…,Tm，其中每個集合又是一棵樹，并稱為這個根結(jié)點(diǎn)的子樹。（2）結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個數(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）孩子、雙親：樹中某結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個雙親的孩子結(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)過的邊的個數(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層。樹的深度：樹中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。（8）層序編號：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。（9）有序樹、無序樹：如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹（10）樹通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式（樹，不是二叉樹，沒中序遍歷。)2． 二叉樹（1）二叉樹的定義：二叉樹是n（n≥0）個結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。（滿二叉樹的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。）完全二叉樹：對一棵具有n個結(jié)點(diǎn)的二叉樹按層序編號，如果編號為i（1≤i≤n）的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號為i的結(jié)點(diǎn)在二叉樹中的位置完全相同。完全二叉樹的特點(diǎn)：1.在滿二叉樹中，從最后一個結(jié)點(diǎn)開始，連續(xù)去掉任意個結(jié)點(diǎn)，即是一棵完全二叉樹。2.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左部；3.完全二叉樹中如果有度為1的結(jié)點(diǎn)，只可能有一個，且該結(jié)點(diǎn)只有左孩子。4.深度為k的完全二叉樹在k-1層上一定是滿二叉樹。（3）二叉樹的性質(zhì)：性質(zhì)1：二叉樹的第i層上最多有2i-1個結(jié)點(diǎn)（i≥1）。性質(zhì)2：一棵深度為k的二叉樹中，最多有2k-1個結(jié)點(diǎn)，最少有k個結(jié)點(diǎn)。深度為k且具有2k-1個結(jié)點(diǎn)的二叉樹一定是滿二叉樹性質(zhì)3：在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有:n0＝n2＋1。（一個結(jié)點(diǎn)的度就是指它放出的射線）性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。性質(zhì)5：對一棵具有n個結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1≤i≤n）的結(jié)點(diǎn)（簡稱為結(jié)點(diǎn)i），有：（1）如果i＞1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號為i/2；如果i＝1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。（2）如果2i≤n，則結(jié)點(diǎn)i的左孩子的序號為2i；如果2i＞n，則結(jié)點(diǎn)i無左孩子。（3）如果2i＋1≤n，則結(jié)點(diǎn)i的右孩子的序號為2i＋1；如果2i＋1＞n，則結(jié)點(diǎn)i無右孩子。3． 二叉樹的遍歷（遞歸調(diào)用與訪問的順序不同而產(chǎn)生不同的遍歷方法）（1） 先序遍歷voidXianXu(BiTreeT){if(T){printf("%c",T->data);//先訪問XianXu(T->lchild);//再繼續(xù)遍歷XianXu(T->rchild);}}（2） 中序遍歷（3） 后序遍歷4. 森林與二叉樹的轉(zhuǎn)換（1）同級以左為親，即左一結(jié)點(diǎn)的右孩子是與它同級的右一結(jié)點(diǎn)（2）只認(rèn)最左路線為親子路線，即結(jié)點(diǎn)的左孩子是它下一級結(jié)點(diǎn)的最左的元素 5. 哈夫曼樹（1）哈夫曼樹的基本概念：哈夫曼樹：給定一組具有確定權(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個結(jié)點(diǎn)，則該二叉樹有（C）個葉子結(jié)點(diǎn)。A.6 B.12 C.24 D.48解法如下：1+2+4+8+16=31計(jì)算從第一層到n-1層的結(jié)點(diǎn)個數(shù)47-31=16計(jì)算第n層的葉子結(jié)點(diǎn)個數(shù)16-16/2=8計(jì)算第n-1層的葉子結(jié)點(diǎn)個數(shù)所以，葉子結(jié)點(diǎn)數(shù)=16+8=24計(jì)算第n層和第n-1層的總?cè)~子結(jié)點(diǎn)數(shù)2、已知遍歷一棵二叉樹的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵樹（C）。C圖如下：A↙↘BF↙↘↘CDG↙