《數(shù)據(jù)結(jié)構(gòu)》考前沖刺大綱講義總結(jié)（考研資料）

《數(shù)據(jù)結(jié)構(gòu)》考前沖刺大綱講義總結(jié)

緒論

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念

1.1.1基本概念和術(shù)語

1.數(shù)據(jù)

2.數(shù)據(jù)元素:可由若干數(shù)據(jù)項組成,數(shù)據(jù)項是不可分割的最小單位

3.數(shù)據(jù)對象:具有相同性質(zhì)的數(shù)據(jù)元素的集合

4.數(shù)據(jù)類型:是一個值的集合和定義在此集合上一組操作的總稱

5.抽象數(shù)據(jù)類型(ADT):包括數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作集

6.數(shù)據(jù)結(jié)構(gòu):邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算

1.1.2數(shù)據(jù)結(jié)構(gòu)的三要素

1.邏輯結(jié)構(gòu):分為線性和非線性結(jié)構(gòu)

2.存儲結(jié)構(gòu)(物理結(jié)構(gòu))：包括順序、鏈?zhǔn)?、索引和散列存?/p>

3.數(shù)據(jù)的運(yùn)算:運(yùn)算的定義和實(shí)現(xiàn)

1.2算法和算法評價

1.2.1算法的基本概念

1.五個重要特性:有窮、確定、可行、輸入和輸出

2.好的算法目標(biāo):正確性、可讀性、健壯性、高效率與低存儲量

1.2.2算法效率的度量

1.時間復(fù)雜度：T(〃)=O(/(〃))，通常指最壞情況下時間復(fù)雜度

2.空間復(fù)雜度:原地工作指算法所需的輔助空間是常量

第2章線性表

2.1線性表的定義及基本操作

2.1.1線性表的定義

1.線性表是具有n個相同類型數(shù)據(jù)元素的有限序列,n為表長,n=0是空表

2.1.2線性表的基本操作

1.InitList(&L)

2.Length(L)

3.LocateElem(L,e)

i

-1-

4.GetElem(L,i)

5.Listinsert(&L,i,e)

6.ListDelete(&L,i,&e)

7.Empty(L)

8.DestroyList(&L)

2.2線性表的順序表示

2.2.1順序表的定義

1.元素邏輯位置與物理位置相同,線性表的順序從1開始

2.線性表的順序存儲類型

(1)一位數(shù)組靜態(tài)分配

idefineMaxSize50〃定義線性表的最大長度

typedefstruct{

ElemTypedata[MaxSize];〃順序表的元素

intlength;〃順序表的當(dāng)前長度

}SqList;〃順序表的類型定義

(2)動態(tài)分配

#defineInitSize100〃表長度的初始定義

typedefstruct(

ElemType*data;?指示動態(tài)分曝組的殿

intMaxSize,length;//毅組蔚晟大容凝居前個數(shù)

}SeqList;〃動態(tài)分配數(shù)組順序表的類型定義

C的初始動態(tài)分配語句L.data=(ElemType*)malloc(sizeof(ElemType)

*InitSize);

3.順序表特點(diǎn):隨機(jī)訪問,存儲密度高,插入和刪除需要移動大量元素

2.2.2順序表上基本操作的實(shí)現(xiàn)

(1)插入:在第i個位置插入e(1</<Llength+1),i不合法則返回false;否

則,將第i個元素及其后所有元素右移一個位置;插入e,表長加1,返回true(從

后往前依次后移一個)

boolListinsert(SqList&LZinti,ElemTypee){

//本算法實(shí)現(xiàn)將元素e插入到順序表L中第個位置

if<i<l||i>L.length+l)//判斷i的范圍是否有效

returnfalse;

if(L.length>=MaxSize)〃當(dāng)前存儲空間已滿，不能插入

returnfalse;

for(intj=L.length;j--)〃將第i個元惠及之后的元素后移

L.data[j]=L,data,Li，-1],<?

L.datafi-11?e；〃在位置i會放入e

L.length++;//線性表長度加1

returntrue;

}

平均移動n/2個元素,則時間復(fù)雜度為0(n)

2

-2-

(2)刪除:刪除第i個元素,成功返回true,并將元素用e返回，否則返回

false(從前往后依次前移一個)

boolListDelete(SqList&L,inti,int&e){

〃本算法實(shí)現(xiàn)刪除順序表L中第i個位置的元素

if(i<llIi>L.length)〃判斷i的范圍是否有效

returnfalse;

e-L.data[i-l];〃將被刪除的元素賦值給e

for(intj=?i;j<L.length;j++)//將第i個位置之后的元素前移

L.data(j-1]-L.data[j];

L.length—;〃線性表長度減1

returntrue;

1

平均移動(nT)/2個元素，則時間復(fù)雜度為0(n)

(3)按值查找(順序查找)：若成功返回元素位序,若失敗返回0

intLocateElem(SqListL,ElemTypee){

〃本算法實(shí)現(xiàn)查找順序表中值為e的元素，如果查找成功，返回元素位序，否則返回O

inti;

for.(i-0;i<L.length;i++)

if(L.data[i]

returni+1;〃下標(biāo)為i的元素值等fe,返回其位序i+l

return0;〃退出循環(huán)，說明查找失敗

平均比較次數(shù)(n+l)/2,時間復(fù)雜度為0(n)

2.3線性表的鏈?zhǔn)奖硎?/p>

2.3.1單鏈表的定義:每個鏈表結(jié)點(diǎn)除了存放自身信息，還存放指向其后繼

結(jié)點(diǎn)的指針;順序存取,從表頭開始查找

typedefstructLNode{//定義單鏈表結(jié)點(diǎn)類型

ElemTypedata;〃數(shù)據(jù)域

structLNode*hext;//指針域

}LNode,*LinkList;

1.通常用頭指針標(biāo)識一個單鏈表,如單鏈表L,頭指針為“NULL”表示一個

空表;通常在單鏈表前面附加一個頭結(jié)點(diǎn)(不設(shè)數(shù)據(jù),指針域指向線性表第一個結(jié)

點(diǎn))

2.引入頭結(jié)點(diǎn)優(yōu)點(diǎn)：⑴由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)指針域中，所以

在鏈表第一個位置上的操作和其他位置上一樣(2)無論鏈表是否為空,其頭指針

是指向頭結(jié)點(diǎn)的非空指針，因此空表和非空表同樣處理

2.3.2單鏈表上基本操作實(shí)現(xiàn)

1.頭插法建立單鏈表:每次插入結(jié)點(diǎn)插到表頭之后

每次將S所指結(jié)點(diǎn)插在最前端

...>

K5—niB-rVTA—

圖2-5頭插法建立單鏈表

3

-3-

LinkListCreatListl(LinkList&L)(

//從表尾到表頭逆向建立單鏈表L,每次均在頭結(jié)點(diǎn)之后插入元素

LNode*s;intx;

L-(LinkList)malloc(sizeof(LNode));〃創(chuàng)建頭結(jié)點(diǎn)

L->next-NULL;〃初始為空鏈表

scanf(/z%d/z,&x);〃輸入結(jié)點(diǎn)的值

while(x!-99991(〃輸入9999表示結(jié)束

s=(LNode*}malloc(sizeof(LNode));〃創(chuàng)建新結(jié)點(diǎn)

s->data-x;

s->next=L->next;

L->next-s;〃將新結(jié)點(diǎn)插入表中，L為頭指針

scanf&x);

)//While結(jié)束

returnL;

時間復(fù)雜度0(n)

2.采用尾插法建立單鏈表:需增加一個尾指針,使其始終指向尾結(jié)點(diǎn)

每次將s所指結(jié)點(diǎn)描在末端1

圖2-6尾插法建立單鏈表

LinkListCreatList2(LinkList&L){

//從表頭到表尾正向建立單鏈表L，每次均在表尾插入元素

intx;//設(shè)元素類型為整型

L=(LinkList)malloc(sizeof(LNode));

LNode*s,*r=L;〃r為表尾指針

Z/

scanf(%d^z&x);//輸入結(jié)點(diǎn)的值

while(x!=9999){〃輸入9999表示結(jié)束

s=(LNode*)malloc(sizecf(LNode));

s->data=x;

r->next=s;

r?s;/〃指向新的表尾結(jié)點(diǎn)

scanf("%d",&x);

)

r->next=NULL;〃尾結(jié)點(diǎn)指針置空

returnL;

)

3.按序號查找結(jié)點(diǎn)值:從第一個結(jié)點(diǎn)出發(fā)，順next往下查找,0(n)

LNode*GetElem(LinkListL,inti)(

〃本算法取出單鏈表，(帶頭結(jié)點(diǎn))中第i個位置的結(jié)點(diǎn)指針

intj-1;〃計數(shù),初始為1

LNode*p-L->next;//頭結(jié)點(diǎn)指價賦給P

if(i-0)

returnL;〃若i等于0,則返回頭結(jié)點(diǎn)

if(i<D

returnNULL;〃若i無效，則返回NULL

while(p4&j<i)(//從第1個結(jié)點(diǎn)開始找，查找第i個結(jié)點(diǎn)

p?p->next;

*+；

)

returnp;〃返回第i個結(jié)點(diǎn)的指針，如果i大于表長，P-NULL,

直接返回P即可

4.按值查找元素:0(n)

LNode*LocateElem(LinkListL,ElemTypee)(〃本算法查找單鏈表L(帶頭結(jié)點(diǎn))

中數(shù)據(jù)域值等于e的結(jié)點(diǎn)指針，否

則返回NULL

LNode*p=L->next;

while(p!?NULLs&p->dataI-e)〃從第1個結(jié)點(diǎn)開始查找data域為

e的結(jié)點(diǎn)

p-p->next;

returnp;〃找到后返回該結(jié)點(diǎn)指針,否則返回NULL

5.插入結(jié)點(diǎn):插入到第i個位置,先檢查插入位置合法性,然后找到第i-1個

4

-4-

結(jié)點(diǎn),在其后插入

p=GetElem(L.i-l);

s->next=p->next;

p->next=s;

(1)時間復(fù)雜度為0(n),若在給定序號后插入時間復(fù)雜度為0(1)

(2)擴(kuò)展:對某一結(jié)點(diǎn)進(jìn)行前插操作:仍將*s插入到*p后面,然后將p->data

與s->data換位置

6.刪除結(jié)點(diǎn)操作:先檢查位置合法性,找到i-l個位置,即被刪除結(jié)點(diǎn)的前驅(qū)

結(jié)點(diǎn)位置

p=GetElem(L,i-l);

q=p->next;

p->next=q->next;

free(q);

2.3.3雙鏈表

兩個指針prior(指針前驅(qū))和next(指向后繼)

typedefstructDNode{

ElemTypedata;

structDNode*prior,*next;

}DNode*DLinkList;

L雙鏈表的插入

p

斗I：I---------*

③!---|x|評-----!①

圖2-10雙鏈表描入結(jié)點(diǎn)過程

①s->next=p->next;〃將結(jié)點(diǎn)*s插入到結(jié)點(diǎn)*p之后

②p->next->prior5=s;

③s->prior=p;

④p->next=s;

2.雙鏈表的刪除

5

-5-

圖2-11雙鏈表刪除結(jié)點(diǎn)過程

p->next=q->next;//圖2-10中步驟①

q->next->prior=p;//圖2-10中步驟②

free(q);//釋放結(jié)點(diǎn)空間

2.3.4循環(huán)鏈表

1.循環(huán)單鏈表:表中最后一個元素不是指向NULL,而是指向頭結(jié)點(diǎn);判斷是

否為空是頭結(jié)點(diǎn)是否等于頭指針;若操作經(jīng)常在表頭和表尾進(jìn)行，可設(shè)置尾指針,

這樣效率為0(1)

2.循環(huán)雙鏈表:空表時頭結(jié)點(diǎn)的prior和next都是L

3.靜態(tài)鏈表:指針是數(shù)組下標(biāo)

812-14靜態(tài)鏈表存儲示意圖

第3章棧和隊列

3.1棧

3.1.1棧的基本概念

1.棧的定義:只允許在一端進(jìn)行插入和刪除操作的線性表.棧頂(允許插入和

刪除的一端)、棧底、空棧，后進(jìn)先出

2.棧的基本操作

(1)InitStack(&S)

(2)StackEmpty(S)

(3)Push(&S,x)

(4)Pop(&S,&x)

(5)GetTop(S,&.x)

(6)ClearStack(&S)

3.1.2棧的順序存儲結(jié)構(gòu)

6

-6-

1.順序棧的實(shí)現(xiàn):用一維數(shù)組存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)一個

指針(top)指示當(dāng)前棧頂位置

#defineMaxSize50〃定義棧中元素的最大個數(shù)

typedefstruct{

Elemtypedata(MaxSizeJ;〃存放棧中元素

inttop;〃棧頂指針

}SqStack;

(1)棧頂指針s.top初始為T,棧頂元素S.data[S.top]

⑵進(jìn)棧:棧不滿,棧頂指針先加1,再送值到棧頂元素

(3)出棧:棧非空,先取棧頂元素值,再講棧頂指針減1

(4)?？?S.top==-l,棧滿S.top==MaxSize-l,棧長S.top+1

top-

(a)空枝(b)l個元素(c)5個元素(d)2個元素

2.順序棧的基本運(yùn)算

(1)初始化

voidInitStack(&S){

s.top=-l;〃初始化棧頂指針

}

(2)判?？?/p>

boolStackEmpty(S){

if(s.top==-l)〃?？?/p>

returntrue;

else//不空

returnfalse;

}

(3)進(jìn)棧

boolPush(SqStack&S,ElemTypex){

if(S.top==MaxSize-l)〃棧滿，報錯

returnfalse;

S.data[++S.top]=x;〃指針先加1,再入棧

returntrue;

)

(4)出棧

boolPop(SqStackiS,ElemType&X){

if(S.top==-l)//?？?，報錯

returnfalse;

x=S.data[S.top-];〃先出棧，指針再減1

returntrue;

(5)讀棧頂元素

7

-7-

boolGetTop(SqStackS,ElemType&x){

if(S.top-1)//?？?，報錯

returnfalse;

x=S,data[S.top];//X記錄棧頂元素

returntrue;

)

3.共享棧:棧滿topl-top=l

3.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)

所有操作都是在單鏈表表頭進(jìn)行，第一個插入的結(jié)點(diǎn)在尾結(jié)點(diǎn),之后依次往

前插入,生成表頭

注:n個不同的元素入棧，有占0個出棧序列

3.2隊列

3.2.1隊列的定義

1.隊列的定義:只允許在表的一端插入在另一端刪除,入隊和出隊,先進(jìn)先出

2.隊列常見的基本操作

(1)InitQueue(&Q)

(2)QueueEmpty(Q)

(3)EnQueue(&Q,x)

(4)DeQueue(&Q,&x)

(5)GetHead(Q,&x)

3.2.2隊列的順序存儲結(jié)構(gòu)

L隊列的順序存儲：附設(shè)兩個指針front和rear分別指示隊頭元素和隊尾

元素的下一個位置

?defineMaxSize50〃定義隊列中元素的最大個數(shù)

typedefstruct(

ElemTypedata[MaxSize];〃存放隊列元素

intfront,rear;〃隊頭指針和隊尾指針

}SqQueue;

初始狀態(tài)(隊空)：Q.front==Q.rear==0

進(jìn)隊操作(隊不滿)：先送值到隊尾,再將隊尾指針加1

出隊操作(隊不空)：先取隊頭值,再講隊頭指針加1

8

-8-

2.循環(huán)隊列

(1)初始時:Q.front=Q.rear=O

(2)隊首指針進(jìn)1:Q.front=(Q.front+l)%MaxSize

(3)隊尾指針進(jìn)1:Q.rear=(Q.rear+l)%MaxSize

(4)隊列長度：(Q.rear+MaxSize-Q.front)%MaxSize

隊空條件：Q.front==Q.rear

Q.frontQ.front

(dl)d?c、f、g入隊(0)d、e、f入隊

為了區(qū)分隊滿還是隊空:犧牲一個單元,隊頭指針在隊尾指針的下一個位置

作為隊滿標(biāo)志；隊滿條件為(Q.rear+l)%MaxSize==Q.front

3.循環(huán)隊列的操作

(1)初始化

voidInitQueue(aQ){

Q.rear?Q.front=0;//初始化隊首、隊尾指針

)

(2)判斷空

boolisEmpty(Q){

if(Q.rear==Q.front)returntrue;//隊空條件

elsereturnfalse;

}：

(3)入隊

boolEnQueue(SqQueue&QZElemType：x){

if((Q.rear+1)%MaxSize==Q.front)returnfalse;〃隊滿

Q.data[Q,rear]=x;

Q.rear=-(Q.rear+1)%MaxSize;〃隊尾指針加1取模

returntrue;

|

(4)出隊

boolDeQueue(SqQueue&Q,ElemType&x){

if(Q.rear==Q.front)returnfalse;//隊空，報錯

x=Q.data[Q.front];

Q.front=(Q.front+1)%MaxSize;〃隊頭指針加1取模

returntrue;

}

3.2.3隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1.隊列的鏈?zhǔn)酱鎯?是一個同時帶有隊頭指針和隊尾指針的單鏈表,頭指針

9

-9-

指向隊頭結(jié)點(diǎn),尾指針指向隊尾結(jié)點(diǎn)

typedefstruct{//鏈?zhǔn)疥犃薪Y(jié)點(diǎn)

ElemTypedata;

structLinkNode*next;

JLinkNode;

typedefstruct{〃鏈?zhǔn)疥犃?/p>

LinkNode*frontz*rear;.//隊列的隊頭和隊尾指針

}LinkQueue;

當(dāng)Q.front==Q.rear==NULL時鏈隊列為空,通常將鏈隊列設(shè)id--個頭結(jié)點(diǎn)

2.鏈隊列的基本操作

(1)初始化

voidInitQueue(LinkQueue&Q){

Q.front?Q.rear=(LinkNode*)malloc(sizeof(LinkNode))”/建立頭結(jié)點(diǎn)

Q.front->next=NULL;〃初始為空

)

(2)判斷空

voidEnQueue(LinkQueue&Q/EleniTypex){

s=(LinkNode*)malloc(sizeof(LinkNode));

s->data=x;s->next==NULL;//創(chuàng)建新結(jié)點(diǎn)，插入到鏈尾

Q.rear->next=s;

Q.rear=s;

}

⑶入隊

boolIsEmpty(LinkQueueQ){

if(Q.front==Q.rear)returntrue;

elsereturnfalse;

(4)出隊

boolDeQueue(LinkQueue&Q,ElemType&x){

if(Q.front==Q.rear)returnfalse;//空隊

p-Q.front->next;

x=p->data;

Q.front->next=p->next;

if(Q.rear==p)

Q.rear=Q.front;//若原隊列中只有一個結(jié)點(diǎn)，刪除后變空

free(p);

3.2.4雙端隊列

兩端均允許進(jìn)隊和出隊的隊列:重點(diǎn)是受限制的雙端隊列，即進(jìn)隊只有一端

出隊有兩端或相反

3.3棧和隊列的應(yīng)用

3.3.1棧在括號匹配中的應(yīng)用

10

-10-

3.3.2棧在表達(dá)式求值中的應(yīng)用：中綴表達(dá)式與后綴表達(dá)式相互轉(zhuǎn)換

1.中綴表達(dá)式A+Bx(C-D)-E/F轉(zhuǎn)化為后綴表達(dá)式為ABCD-x+EF/-

2.操作：如果該項是操作數(shù),則將其壓入棧中；如果該項是操作符,則連續(xù)從

棧中彈出操作數(shù)Y和X,做Y<op>X操作，并將其重新壓入棧

3.3.3棧在遞歸中的應(yīng)用：效率并不高

3.3.4隊列在層次遍歷中的應(yīng)用

表3-2層次遍歷二又樹的過程

序說明隊內(nèi)隊外

1A入A

2Atb，BC入BCA

3B出，D入CDAB

4C出.EF入DEFABC

5DIB.G入EFGABCD

6E出，HI入FGHIABCDE

7F出GHIABCDEF

8GHI出ABCDEFGH1

3.3.5隊列在計算機(jī)系統(tǒng)中的應(yīng)用：緩沖區(qū)隊列

3.4特殊矩陣的壓縮存儲

3.4.1數(shù)組的定義

3.4.2數(shù)組的存儲結(jié)構(gòu)

對于多維數(shù)組,可以分為按行優(yōu)先存儲和按列優(yōu)先存儲，但都是按順序存放

在一個連續(xù)的空間中

3.4.3矩陣的壓縮存儲

壓縮存儲:為多個值相同的元素只分配一個存儲空間,對0不分配存儲空間

特殊矩陣:具有許多相同元素或0元素，分布有一定規(guī)律的矩陣(對稱矩陣、

上下三角矩陣、對角矩陣)

1.對稱矩陣:n階方陣中，按主對角線對稱，只存放主對角線和下三角元素

(或上三角元素,又或按行或者按列存儲)(共n(n+l)/2)

2.三角矩陣:上或下三角矩陣,其另外一角都為同一常數(shù),存儲完對角線和下

三角元素后，緊接著存儲上三角元素一次(共n(n+l)/2+l)

3.三對角矩陣:所有元素集中在三條主對角線上,其余均為0;(i,j)元素在

數(shù)組中的下標(biāo)為k=2i+j-3,反之,若元素在數(shù)組中第k個位置,則

/=1（左+l）/3+l_J/=Z:—2i+3i取下限

3.4.4稀疏矩陣

11

-11-

元素的個數(shù)遠(yuǎn)大于非0元素的個數(shù),此時需要一個三元數(shù)組，同時存放非0

元素的行、列和值

第4章樹與二叉樹

4.1樹的基本概念

4.1.1樹的定義：只有一個根結(jié)點(diǎn)，其他結(jié)點(diǎn)稱為根結(jié)點(diǎn)的子樹

1.樹的根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)外所有結(jié)點(diǎn)只有一個前驅(qū)結(jié)點(diǎn),所有

結(jié)點(diǎn)可以有0或多個后繼結(jié)點(diǎn);n個結(jié)點(diǎn)的樹有nT個邊

4.1.2基本術(shù)語

（1）根往下走過的路徑直到尾結(jié)點(diǎn)K,前面所有結(jié)點(diǎn)都是K的祖先結(jié)點(diǎn),K

是前面所有結(jié)點(diǎn)的子孫結(jié)點(diǎn),路徑上最接近K的結(jié)點(diǎn)叫K的雙親結(jié)點(diǎn),K是其孩

子結(jié)點(diǎn),有相同雙親結(jié)點(diǎn)的叫兄弟結(jié)點(diǎn)

（2）樹中一個結(jié)點(diǎn)的子結(jié)點(diǎn)（直接孩子結(jié)點(diǎn)）個數(shù)叫稱為該結(jié)點(diǎn)的度，樹中

結(jié)點(diǎn)最大的度叫樹的度

（3）度大于0的叫分支結(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)最大的層數(shù)

（5）路徑和路徑長度:路徑長度是所經(jīng)過邊的個數(shù)

（6）森林:是m>=0棵互不相交樹的集合

4.1.3樹的性質(zhì)

（1）樹中結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)度數(shù)加1

（2）度為m的樹中第i層上至多有加一個結(jié)點(diǎn)

（3）高度為h的m叉樹至多有（川_i）/（,"-1）個結(jié)點(diǎn)

（4）具有n個結(jié)點(diǎn)的m叉樹最小高度為「log,”（〃⑺-1）+1）］

注意:設(shè)樹中度為i的結(jié)點(diǎn)個數(shù)為M（1）總結(jié)點(diǎn)數(shù)：

N=N0+N\+N2+...+Nm⑵總分支數(shù)：V=1XN1+2XN2+..+加xNm（3）

N=M+i

4.2二叉樹的概念

4.2.1二叉樹的定義及主要特性

12

-12-

1.二叉樹的定義:不存在度大于2的結(jié)點(diǎn),左右順序不能顛倒

（1）二叉樹與度為2的樹的區(qū)別:度為2的樹至少有3個結(jié)點(diǎn),而二叉樹可

以為空;二叉樹有左右子樹之分,不能顛倒

2.幾個特殊的二叉樹

（1）滿二叉樹:所有層都含最多個結(jié)點(diǎn);對于滿二叉樹，對于編號為i的結(jié)

點(diǎn)，若有雙親，則其雙親為若有左孩子為萬，右孩子為21+1

（2）完全二叉樹:每個結(jié)點(diǎn)的編號都與滿二叉樹一一對應(yīng);①若三］〃/2」則

結(jié)點(diǎn)i為分支結(jié)點(diǎn),否則為葉子結(jié)點(diǎn)②葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)

③如果有度為1的結(jié)點(diǎn),則只能有1個,且該結(jié)點(diǎn)只有左孩子沒有右孩子④按層

序編號后,一旦出現(xiàn)某結(jié)點(diǎn)（編號為i）為葉子結(jié)點(diǎn)或只有左孩子,則編號大于i

的結(jié)點(diǎn)均為葉子結(jié)點(diǎn)⑤若n為奇數(shù),則每個結(jié)點(diǎn)都有左孩子和右孩子;若為偶數(shù),

則編號最大的只有左孩子,無右孩子

（3）二叉排序樹:左子樹上所有結(jié)點(diǎn)關(guān)鍵字小于根結(jié)點(diǎn),右子樹上所有關(guān)鍵

字大于根結(jié)點(diǎn),左子樹和右子樹又是一個二叉排序樹

（4）平衡二叉樹:樹上任意結(jié)點(diǎn)的左子樹和右子樹深度之差不超過1

3.二叉樹的性質(zhì)

（1）非空二叉樹葉子結(jié)點(diǎn)數(shù)等于度為2的結(jié)點(diǎn)數(shù)+1,即NON2+1

（2）非空二叉樹第k層上至多有2一結(jié)點(diǎn)

（3）高度為H的二叉樹至多有2"-1個結(jié)點(diǎn)

（4）當(dāng)i>l時,結(jié)點(diǎn)i的雙親編號為上/2」，即當(dāng)n為偶數(shù),雙親編號為i/2,它

是雙親的左孩子；i為奇數(shù),雙親編號為（iT）/2,它是雙親結(jié)點(diǎn)的右孩子

（5）2i<=N,結(jié)點(diǎn)的左孩子編號為2i,否則無左孩子

（6）2i+l<=N,結(jié)點(diǎn)i的右孩子編號為2i+l,否則無右孩子

⑺結(jié)點(diǎn)i所在層次為］log2，」+l

13

-13-

(8)具有N個結(jié)點(diǎn)的完全二叉樹高度為|_log2N」+l

4.2.2二叉樹的存儲結(jié)構(gòu)

1.順序存儲結(jié)構(gòu):按編號順序存放,完全二叉樹和滿二叉樹比較合適;要從數(shù)

組下標(biāo)為1開始存儲

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)

Ichilddatarchild

(1)二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)表示

typedefstructBiTNode{

ElemTypedata;〃數(shù)據(jù)域

structBiTNode*lchild,*rchild;I〃左、右孩子指針

)BiTNode,*BiTree;

在含有n個結(jié)點(diǎn)的二叉鏈表中含有n+1個空鏈域

4.3二叉樹的遍歷與線索二叉樹

4.3.1二叉樹的遍歷

1.先序遍歷(NLR根左右)

voidPreOrder(BiTreeT){

if(T!=NULL){

visit(T);〃訪問根結(jié)點(diǎn)

PreOrder(T->lchild);〃遞歸遍歷左子樹

PreOrder(T->rchild);〃遞歸遍歷右子樹

}

}.....

2.中序遍歷(LNR左根右)

voidInOrder(BiTreeT){

if(T!=NULL){

InOrder(T->lchild);〃遞歸遍歷左子樹

visit(T);〃訪問根結(jié)點(diǎn)

InOrder(T->rchild);〃遞歸遍歷右子樹

)

3.后序遍歷(LRN左右根)

voidPostOrder(BiTree:T){

if(T!=NULL){

PostOrder(T->lchild);〃遞歸遍歷左子樹

PostOrder(T->rchild);〃遞歸遍歷右子樹

visit(T);//訪問根結(jié)點(diǎn)

：

}

}

時間與空間復(fù)雜度都是0(n)

4.遞歸算法與非遞歸算法的轉(zhuǎn)換(借助棧)

中序遍歷:先掃描根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并將它們一一進(jìn)棧，然后出棧一個結(jié)

14

-14-

點(diǎn)*p(p沒有左孩子結(jié)點(diǎn)或者左孩子結(jié)點(diǎn)被訪問過)，則訪問他;然后掃描右孩子

結(jié)點(diǎn)，將其進(jìn)棧,再掃描右孩子結(jié)點(diǎn)所有左結(jié)點(diǎn)并一一進(jìn)棧,直到?？?/p>

voidIn0rder2(BiTreeT){

InitStack(S);

BiTreep=T;

while(p||lisEnpty(S)){

if(p){

Push(S.p);

p=p->lchild;

Jelse{

Pop(S.p);

visit(p);

p=p->rchild;

)

)

)

5.層次遍歷:先將二叉樹根結(jié)點(diǎn)入隊,然后出隊訪問該結(jié)點(diǎn),若它由左子樹,

將左子樹入隊,若有右子樹將右子樹入隊.然后出隊,對出隊結(jié)點(diǎn)進(jìn)行訪問，如此

反復(fù)

voidLevelOrder(BiTreeT)I

InnitQueue(Q);

BiTreep;

EnQueue(Q,T);

whiledisEinpty(Q)){

DeQueue(Q,p);

visit(p);

if(p->lchildl=NULL){

EnQueue(Q,p->lchi1d),

)

if(p->rchildl=NULL){.

EnQueue(Q,p->rchild);

)

)

6.由遍歷序列構(gòu)造二叉樹:先序序列和中序序列可以唯一確定一棵二叉樹，

先序遍歷中第一個結(jié)點(diǎn)必定是根結(jié)點(diǎn)，中序遍歷中根結(jié)點(diǎn)必然將序列分為兩個子

序列；同理,二叉樹后序序列和中序序列也能唯一確定一個二叉樹;注意,如果知

道二叉樹先序序列和后序序列，不能唯一確定一個二叉樹

例如，求先序序列(ABCDEFGHI)和中序序列(Bd止DGHFD所確定的二叉樹。

首先，由先序序列可瘋A,為二叉樹的根結(jié)點(diǎn).中序序列中A之前的BC為左子樹的中序序列，

EDGHF1為右子樹的中序序列.然后由先序序列可知B是左子樹的根結(jié)點(diǎn)，D是右子樹的根結(jié)點(diǎn)?

依此類推，就能將剩下的結(jié)點(diǎn)繼續(xù)分解下去，最后得到的二叉樹如圖4-8(c).

4.3.2線索二叉樹

1.基本概念:利用二叉樹中大量空鏈域(N個結(jié)點(diǎn)中有N+1個空指針)存放直

接前驅(qū)或后繼的指針;線索化時規(guī)定,若無左子樹,令I(lǐng)child指向其前驅(qū)結(jié)點(diǎn),若

無右子樹,rchild指向其后繼結(jié)點(diǎn)

15

-15-

lugIchilddatarchildrtag

Ha.J。Ichild域指示結(jié)點(diǎn)的左孩子

la8[lIchild域指示結(jié)點(diǎn)的前驅(qū)

JOrchild域指示結(jié)點(diǎn)的右孩子

jlrchild域指示結(jié)點(diǎn)的后繼

線索二叉樹存儲結(jié)構(gòu)為：

typedefstructThreadNode（

ElemTypedata;

structThreadNode*1chi1ii+rchiId;

intItag,rtag,//S右線索標(biāo)志

}ThreadNode,*ThreadTree;

這叫線索鏈表,其中指向其前驅(qū)和后繼的指針叫線索,線索二叉樹

2.線索二叉樹的構(gòu)造:遍歷一次二叉樹,遍歷過程中,檢查當(dāng)前結(jié)點(diǎn)左右指針

域是否為空,若為空,將他們改為指向前驅(qū)或后繼的線索（標(biāo)識tag有孩子則為0,無

則為1）

圖4-10中序線索二叉樹及其二叉鏈表示

注:有時為方便,在二叉樹線索鏈表上添加一個頭結(jié)點(diǎn),并令其Ichild域指

針指向二叉樹根結(jié)點(diǎn),其rchild指向中序遍歷的最后一個結(jié)點(diǎn);反之,令二叉樹

第一個結(jié)點(diǎn)的Ichild和最后一個結(jié)點(diǎn)的rchild指向頭結(jié)點(diǎn),變成一個雙向循環(huán)

鏈表

注:先序序列為n個順序的樹,不同二叉樹個數(shù)為，

4.4樹森林

4.4.1樹的存儲結(jié)構(gòu)

1.雙親表示法:一組連續(xù)空間存儲每個結(jié)點(diǎn),每個結(jié)點(diǎn)增設(shè)一個偽指針,指示

其雙親在數(shù)組中位置（例下圖:根結(jié)點(diǎn)為下標(biāo)0,尾指針為-1）；適合求雙親結(jié)點(diǎn)，

16

-16-

不適合求孩子結(jié)點(diǎn)

圖4-13樹的雙親表示法

2.孩子表示法:將每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表連接起來;適合查找孩子結(jié)

點(diǎn),不適合雙親結(jié)點(diǎn)

圖444樹的孩子表示法和孩子兄弟表示法

3.孩子兄弟表示法：以二叉鏈表作為樹的存儲結(jié)構(gòu),包括結(jié)點(diǎn)值、指向結(jié)點(diǎn)

第一個孩子結(jié)點(diǎn)和指向結(jié)點(diǎn)下一個兄弟結(jié)點(diǎn)的指針,方便實(shí)現(xiàn)樹轉(zhuǎn)化為二叉樹,

易于查找結(jié)點(diǎn)的孩子（上圖）

4.4.2樹、森林和二叉樹的轉(zhuǎn)換

1.樹轉(zhuǎn)化為二叉樹規(guī)則:每個結(jié)點(diǎn)左指針指向它第一個孩子結(jié)點(diǎn),右指針指

向它在樹中的相鄰兄弟結(jié)點(diǎn)，表示為“左孩子右兄弟”，由于根沒有右兄弟，所以

樹轉(zhuǎn)化為二叉樹沒有右子樹

圖4-15樹轉(zhuǎn)換為二叉樹

2.森林轉(zhuǎn)化為二叉樹:先將森林中每一棵樹轉(zhuǎn)化為二叉樹,再將第一棵樹的

根作為轉(zhuǎn)化為二叉樹的根,第一棵樹的左子樹作為轉(zhuǎn)化后二叉樹根的左子樹,第

17

-17-

二棵樹作為轉(zhuǎn)化后二叉樹的右子樹,第三棵樹作為轉(zhuǎn)化后二叉樹根的右子樹的右

子樹，依次類推

3.二叉樹轉(zhuǎn)化為森林:二叉樹根及其左子樹為第一棵樹的二叉樹形式,二叉

樹根的右子樹又可以看做是一個由除第一棵樹外的森林轉(zhuǎn)化后的二叉樹,應(yīng)用同

樣的方法,直到最后產(chǎn)生一棵沒有右子樹的二叉樹為止,就得到了原森林

注：(1)樹轉(zhuǎn)化為二叉樹:在兄弟結(jié)點(diǎn)間加一條線;對每一個結(jié)點(diǎn)，只保留它與

第一個子結(jié)點(diǎn)的連線,與其他子結(jié)點(diǎn)的連線全部抹掉；以樹軸為軸心，順時針旋轉(zhuǎn)

45°

(2)森林轉(zhuǎn)化為二叉樹:將每棵樹根相連,將森林中每棵樹轉(zhuǎn)化為相應(yīng)的二叉

樹；以第一棵樹根軸心順時針旋轉(zhuǎn)45°

4.4.3樹和森林的遍歷

1.樹的遍歷

(1)先根遍歷：與相應(yīng)的二叉樹的先序遍歷相同

(2)后根遍歷:與相應(yīng)的二叉樹的中序遍歷相同

(3)層次遍歷:與二叉樹一樣

2.森林的遍歷

(1)先序遍歷森林:訪問森林每一棵樹根結(jié)點(diǎn);先序遍歷第一棵樹中根結(jié)點(diǎn)子

樹森林;先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林

(2)中序遍歷森林：中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林;訪問第一

棵樹根結(jié)點(diǎn)；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林

4.5樹與二叉樹的應(yīng)用

4.5.1二叉排序樹

1.定義:簡稱BST,也稱二叉查找樹;左子樹值全部小于根結(jié)點(diǎn)值,右子樹值

全部大于根結(jié)點(diǎn)值,左右子樹本身也是二叉排序樹,所以二叉排序樹中序遍歷可

以得到一個遞增序列

18

-18-

2.二叉排序樹查找:從根結(jié)點(diǎn)開始,沿某一條分支逐層向下進(jìn)行比較的過程,

將給定值與根結(jié)點(diǎn)進(jìn)行比較,若相等,則查找成功;若根結(jié)點(diǎn)關(guān)鍵字大于關(guān)鍵字，

在根結(jié)點(diǎn)左子樹中查找,否則在右子樹中查找,是一個遞歸的過程

3.二叉排序樹的插入:若關(guān)鍵字k小于根結(jié)點(diǎn)關(guān)鍵字,則插入左子樹中,相反

插入右子樹中；一定插入了葉結(jié)點(diǎn)中

SI4-2I向二叉排序樹中插入結(jié)點(diǎn)

4.二叉排序樹的構(gòu)造:按二叉排序樹性質(zhì)進(jìn)行構(gòu)造

5.二叉排序樹的刪除:將單個元素刪除,其他因為此刪除的鏈再重新組合,確

保性質(zhì)不變

（1）若刪除是葉結(jié)點(diǎn)，則直接刪除

（2）若結(jié)點(diǎn)z只有一棵左子樹或右子樹,則讓z的子樹成為z父結(jié)點(diǎn)的子

樹,替代z位置

（3）若結(jié)點(diǎn)z有左右兩棵子樹,則令z的直接后繼（或直接前驅(qū)）代替z,然

后從二叉排序樹中刪除這個直接后繼（或直接前驅(qū)）

6.二叉排序樹的查找效率分析

（1）對于高度為H的二又排序樹,其插入和刪除操作的運(yùn)行時間都是0（n）.

19

-19-

但在最壞的情況下,構(gòu)造二叉排序樹的輸入序列是有序的，則會形成一個傾斜的

單支樹，此時二叉排序樹的性能顯變壞,樹的高度也增加為元素個數(shù)N,如下圖所

示：

在等概率情況下，圖4-23(a)的查找成功的平均查找長度為

ASL=(l+2X2+3X4+4X3)/10=2.9

而圖4-23(b)的查找成功的平均查找長度為

由上可知,二叉排序樹查找算法的平均查找長度,主要取決于樹的高度，即與

二叉樹的形態(tài)

有關(guān).如果二叉排序樹是一個只有右(左)孩子的單支樹(類似于有序的單鍵

表)，其平均查找長度和單鏈表相同,為0(n).如果二義排序樹的左、右子樹的高

度之差的絕對值不超過1,這樣的二叉排序樹稱為平衡二叉樹.它的平均查找長

度達(dá)到O(log2n)

(2)二叉排序樹與二分查找:從查找過程看，二叉排序樹與二分查找相似.就

平均時間性能而言,二叉排序樹上的查找和二分查找差不多.但二分查找的判定

樹唯一,而二叉排序樹不唯一,相同的關(guān)鍵字其插入順序不同可能生成不同的二

叉排序樹,如上圖所示;就維護(hù)表的有序性而言,二叉排序樹無須移動結(jié)點(diǎn)，只需

修改指針即可完成插入和刪除操作，平均執(zhí)行時間為0(1嗝〃).二分查找的對象是

有序順序表,若有插入和刪除結(jié)點(diǎn)的操作,所花的代價是0(n).當(dāng)有序表是靜態(tài)