數(shù)據(jù)結(jié)構(gòu)總結(jié)課件

封面1.什么是數(shù)據(jù)結(jié)構(gòu)

2.數(shù)據(jù)結(jié)構(gòu)研究什么內(nèi)容

3.數(shù)據(jù)結(jié)構(gòu)處理軟件開(kāi)發(fā)過(guò)程中的什么問(wèn)題

4.《數(shù)據(jù)結(jié)構(gòu)與算法》在軟件技術(shù)專業(yè)課程體系中占有什么地位本學(xué)期的任務(wù)1學(xué)習(xí)圖狀結(jié)構(gòu)及其應(yīng)用2學(xué)習(xí)集合結(jié)構(gòu)及其應(yīng)用3學(xué)習(xí)常用算法，并選用常用算法解決問(wèn)題窮舉法分治法動(dòng)態(tài)規(guī)劃貪心法回溯法分枝限界法線性表例2人機(jī)對(duì)奕問(wèn)題樹……..……..…...…...…...…...競(jìng)賽項(xiàng)目的時(shí)間安排問(wèn)題圖數(shù)據(jù)結(jié)構(gòu)定義:數(shù)據(jù)的集合，以一定的邏輯關(guān)系組織在一起，以某種方式存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了某些相應(yīng)運(yùn)算。這種結(jié)構(gòu)成為數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

h數(shù)據(jù)類型—高級(jí)語(yǔ)言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱例C語(yǔ)言中，提供int,char,float,double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類型等。用戶也可用typedef自己定義數(shù)據(jù)類型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;算法描述算法的時(shí)間復(fù)雜度:以算法中基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。例:(a)x=x+1; O(1)(b)for(i=0;i<n;i++)x=x+1; O(n)(c)for(i=1;i<n;i++)for(j=1;j<i;j++)x=x+1; O(n2)1.2線性表和數(shù)組

1.2.1線性表及其順序存儲(chǔ)結(jié)構(gòu)一、線性表的邏輯結(jié)構(gòu)線性表由n(n≥0)個(gè)數(shù)據(jù)元素a1,a2,...,an構(gòu)成的有限序列記作:L＝(a1,a2,...,an)其中，a1稱為首元素，an稱為尾元素。表的長(zhǎng)度(表長(zhǎng))

線性表中數(shù)據(jù)元素的數(shù)目?？毡?/p>

不含數(shù)據(jù)元素的線性表(n=0)。一、線性表的邏輯結(jié)構(gòu)線性表(a1,a2,...,an)的特征:直接前驅(qū)

ai－1在ai之前，稱ai－1是ai的直接前驅(qū)(1＜i≤n)直接后繼

ai＋1在ai之后，稱ai＋1是ai的直接后繼(1≤i＜n)a1沒(méi)有前驅(qū)an沒(méi)有后繼。ai(1＜i＜n)有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼一、線性表的邏輯結(jié)構(gòu)線性表L＝(a1,a2,...,an)的運(yùn)算1)initiate(L)初始化L為空表2)length(L)求長(zhǎng)度3)get(L,i)取元素ai4)prior(L,elm)求前驅(qū)函數(shù)5）next(L,elm)求后繼函數(shù)6）locate(L,x)定位函數(shù)7）insert(L,i,x)在元素ai之前插入新元素ｘ8)delete(L,i)刪除第i個(gè)數(shù)據(jù)元素9)empty(L)判空表函數(shù)10)clear(L)表置空函數(shù)二、線性表的順序存儲(chǔ)結(jié)構(gòu)插入一個(gè)元素┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4│17│20│25│35│40│││└─┴─┴─┴─┴─┴─┴─┴─┴─┘123456789||

插入8n┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4││17│20│25│35│40││└─┴─┴─┴─┴─┴─┴─┴─┴─┘123456789||

插入8n┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4│8│17│20│25│35│40││└─┴─┴─┴─┴─┴─┴─┴─┴─┘123456789||

插入8之后n二、線性表的順序存儲(chǔ)結(jié)構(gòu)算法分析假設(shè)在線性表的第ｊ個(gè)位置插入一個(gè)元素的概率為Pj，ｎ是線性表的長(zhǎng)度,1≤ｊ≤n,那么每插入一個(gè)元素所需移動(dòng)元素?cái)?shù)目的期望值(平均數(shù)目)是：

其中，n-j+1表示在第ｊ個(gè)元素之前插入一個(gè)新元素必須移動(dòng)n-j+1個(gè)元素。假定在表的任意位置ｊ(1≤j≤n)插入元素的概率相等,即Ｐｊ＝1/n,那么移動(dòng)元素的期望值為：二、線性表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的評(píng)價(jià)(1)優(yōu)點(diǎn)

a)存取結(jié)構(gòu)簡(jiǎn)單，存取任意元素的時(shí)間是一個(gè)常數(shù)，存取速度快

b)不使用指針，存儲(chǔ)密度大。(2)缺點(diǎn)

a)需請(qǐng)求分配一個(gè)連續(xù)存儲(chǔ)塊；

b)插入可能發(fā)生溢出；

c)為了防止溢出，需保留一個(gè)較大的連續(xù)存儲(chǔ)塊，造成浪費(fèi)；

d)插入和刪除需移動(dòng)大量數(shù)據(jù)元素。1.2.2線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

一、單鏈表單鏈表的結(jié)點(diǎn)結(jié)構(gòu)

data結(jié)點(diǎn)類型說(shuō)明:

structnode{element；

structnode*next;}1.2.2線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

一、單鏈表思考：若刪除尾結(jié)點(diǎn)C情況如何？1.2.2線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

一、單鏈表1.2.2線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

一、單鏈表1.2.2線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

一、單鏈表帶表頭結(jié)點(diǎn)的單鏈表的一般形式

若head->next≠NULL，則為非空單鏈表；

若head->next＝NULL，則為空單鏈表。

1.2.2線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

一、單鏈表帶表頭結(jié)點(diǎn)的循環(huán)單鏈表的一般形式若head->next≠head，則為非空循環(huán)單鏈表；

若head->next＝head，則為空循環(huán)單鏈表。

二、雙向鏈表雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)

結(jié)點(diǎn)類型說(shuō)明:

structnodedou{elementdata；

structnodedou*llink;structnodedou*rlink;}二、雙向鏈表帶表頭結(jié)點(diǎn)的雙向鏈表

(1)非空表(首結(jié)點(diǎn)的左指針為空，尾結(jié)點(diǎn)的右指針為空)

h┌──────────────────────────┐┌──┐┌┼┬─┬─┐┌─┬─┬─┐┌─┬─┬─┐││─┼→┤│││─┼→┤∧│a1│─┼→....→┤│an│∧├←┘│││││││││├←←┼─│││└──┘└─┴─┴─┘└─┴─┴─┘└─┴─┴─┘

頭指針表頭結(jié)點(diǎn)首結(jié)點(diǎn)尾結(jié)點(diǎn)

(2)空表

h┌──┐┌─┬─┬─┐│─┼→┤∧││∧│││││││└──┘└─┴─┴─┘

頭指針表頭結(jié)點(diǎn)1.2.3數(shù)組及其順序存儲(chǔ)

一、組和數(shù)組的運(yùn)算對(duì)數(shù)組的運(yùn)算:

(1)給定一個(gè)有定義的下標(biāo)組，訪問(wèn)與其對(duì)應(yīng)的數(shù)組元素。(2)給定一個(gè)有定義的下標(biāo)組，存取或修改與其對(duì)應(yīng)的數(shù)組元素。

1.2.3數(shù)組及其順序存儲(chǔ)

一、組和數(shù)組的運(yùn)算

例二維數(shù)組:┌┐│ａ11ａ12││ａ21ａ22││ａ31ａ32││ａ41ａ42│└┘(1)以行序?yàn)橹餍虻捻樞虼鎯?chǔ)方式:┌──┬──┬──┬──┬──┬──┬──┬──┐│ａ11│ａ12│ａ21│ａ22│ａ31│ａ32│ａ41│ａ42│└──┴──┴──┴──┴──┴──┴──┴──┘

序號(hào):12345678(2)以列序?yàn)橹餍虻捻樞虼鎯?chǔ)方式:┌──┬──┬──┬──┬──┬──┬──┬──┐│ａ11│ａ21│ａ31│ａ41│ａ12│ａ22│ａ32│ａ42│└──┴──┴──┴──┴──┴──┴──┴──┘

序號(hào):123456781.3棧和隊(duì)列

1.3.1棧定義和術(shù)語(yǔ)(1)棧(stack):只允許在表的一端插入和刪除元素的線性表。(2)棧頂(top):線性表中允許進(jìn)行插入和刪除的一端。(3)棧底(bottom):線性表中不允許進(jìn)行插入和刪除的一端。(4)棧頂元素:位于棧頂?shù)脑亍?5)棧底元素:位于棧底的元素。(6)空棧:不含元素的棧。(7)進(jìn)棧(push,下推,壓入):插入一個(gè)新元素到棧中。(8)退棧(POP,彈出):刪除棧頂元素。(9)棧中元素的進(jìn)出原則:后進(jìn)先出(LastInFirstOut)。(10)棧的別名:“后進(jìn)先出表”或“LIFO”表

<───┐┌───

退棧│↑↓│進(jìn)棧││├──┤││4├──┤top→│Ｃ│3棧頂元素Ｃ├──┤│Ｂ│2├──┤bottom│Ａ│1棧底元素Ａ└──┘棧的圖示1.3.1棧

一、棧的定義棧的基本操作(1)init(s)初始化，將棧ｓ設(shè)置為空棧(2)empty(s)判斷棧ｓ是否為空棧(3)push(s,x)將元素ｘ壓入棧ｓ中(4)pop(s)彈出棧ｓ的頂元素(5)gettop(s)讀取棧頂元素(6)clear(s)棧置空操作(7)length(s)求當(dāng)前棧中元素的個(gè)數(shù)

一、棧的定義例由輸入(A,B,C),得輸出(C,B,A)的操作

A,B,CC,B,A<───┐┌───<───┐┌───<───┐┌───

退棧│↑↓│進(jìn)棧│↑↓││↑↓│├──┤├──┤├──┤

3││top→3│C│3││├──┤├──┤├──┤2││2│B│2││├──┤├──┤├──┤1││1│A│1││└──┘└──┘└──┘top→0top→0

空棧A,B,C進(jìn)棧后C,B,A退棧后

push(s,A);pop(s);push(s,B);pop(s);push(s,C);pop(s);二、棧的存儲(chǔ)結(jié)構(gòu)s[1..n]s[1..n]s[1..n]┌──┐┌──┐┌──┐n││n││top→n│an│├──┤├──┤├──┤n-1││n-1││n-1││.├──┤.├──┤.├──┤.││.││.││.├──┤.├──┤.├──┤3││3││3│a3│├──┤├──┤├──┤2││top→2│a2│2│a2│├──┤├──┤├──┤1││1│a1│1│a1│└──┘└──┘└──┘top→0空棧0非空棧滿棧（下溢）（上溢）二、棧的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)綏ＴO(shè)鏈?zhǔn)綏５臈ｍ斨羔槥閠op，指向位于棧頂?shù)慕Y(jié)點(diǎn)：

datanext┌─┬─┐top─→│B│││棧頂└─┴┼┘

datanext↓┌─┬─┐┌─┬─┐top＝NULLtop─→│A│∧│棧頂│A│∧│棧底└─┴─┘(棧底)└─┴─┘

(1)置為空棧(2)壓入元素A之后(3)壓入元素B之后

1.3.2隊(duì)列

一、定義和術(shù)語(yǔ)(1)隊(duì)列:只允許在表的一端刪除元素，在另一端插入元素的線性表(2)空隊(duì)列:不含元素的隊(duì)列(3)隊(duì)首:隊(duì)列中只允許進(jìn)行刪除元素的一端(4)隊(duì)尾:隊(duì)列中只允許進(jìn)行插入的一端(5)隊(duì)首元素:處于隊(duì)首的元素(6)隊(duì)尾元素:處于隊(duì)尾的元素(7)進(jìn)隊(duì):插入一個(gè)元素(8)出隊(duì):刪除一個(gè)元素(9)隊(duì)列中元素的進(jìn)出原則:先進(jìn)先出(FirstInFirstOut)。(10)隊(duì)列的別名:先進(jìn)先出表，F(xiàn)IFO表

隊(duì)列示例─┬─┬─┬─┬─┬─┬─││││││出隊(duì)←││A│B│C││←進(jìn)隊(duì)││││││─┴─┴─┴─┴─┴─┴─↑↑

headtail(隊(duì)首指針)(隊(duì)尾指針)

1.3.2隊(duì)列

一、定義和術(shù)語(yǔ)隊(duì)列的的基本操作(1)init(q)初始化，將隊(duì)列q設(shè)置為空隊(duì)列(2)empty(q)判斷隊(duì)列q是否為空隊(duì)列(3)insert(q,x)入隊(duì)操作，將ｘ插入隊(duì)列q尾部(4)delete(q)出隊(duì)操作，取隊(duì)列q首元素(5)gethead(q)讀取隊(duì)列q首元素(6)clear(q)隊(duì)列q置空操作(7)length(q)求當(dāng)前隊(duì)列q中元素的個(gè)數(shù)二、鏈隊(duì)列如果采用單向鏈，設(shè)兩個(gè)指針

head指向隊(duì)首

tail指向隊(duì)尾空隊(duì)列

head=tail=NULL;有一個(gè)元素的隊(duì)列

datanext┌─┬─┐head→│A│∧│首(尾)結(jié)點(diǎn)

tail→└─┴─┘一般隊(duì)列

datanext┌─┬─┐head─→│A│││首結(jié)點(diǎn)└─┴┼┘↓┌─┬─┐│B│││└─┴┼┘↓┌─┬─┐tail─→│C│∧│尾結(jié)點(diǎn)└─┴─┘二、鏈隊(duì)列

head┌──┐│^│p─┐└──┘↓┌──┐┌─┬─┐│^││A│^│└──┘└─┴─┘tail

┌─┬─┐head─→│A│││首結(jié)點(diǎn)└─┴┼┘↓┌─┬─┐

tail─→│B│∧│尾結(jié)點(diǎn)└─┴─┘

┌─┬─┐

p─→│C││└─┴─┘

入隊(duì)算法if(head==NULL){head=p;}else{tail->next=p;}tail=p;二、鏈隊(duì)列

head┌──┐│┼───┐└──┘↓┌──┐┌─┬─┐│┼→│A│^│└──┘└─┴─┘tail

┌─┬─┐head─→│A│││首結(jié)點(diǎn)└─┴┼┘↓┌─┬─┐│B│││└─┴┼┘↓┌─┬─┐tail─→│C│∧│尾結(jié)點(diǎn)└─┴─┘

出隊(duì)算法if(head==NULL){/*空隊(duì)列*/}else{p=head;head=head->next;if(head==NULL)tail==NULL;}三、循環(huán)隊(duì)列

如果采用數(shù)組q[6],設(shè)兩個(gè)指針

head指向隊(duì)首

tail指向隊(duì)尾空隊(duì)列head=tail┌-┬-┬-┬-┬-┬-┐←│││││││←└-┴-┴-┴-┴-┴-┘012345↑↑HT(帶頭結(jié)點(diǎn)鏈表？）

插入A,B,C,D,E之后┌-┬-┬-┬-┬-┬-┐←││A│B│C│D│E│←└-┴-┴-┴-┴-┴-┘012345↑↑HT刪除A,B,C之后┌-┬-┬-┬-┬-┬-┐←│││││D│E│←└-┴-┴-┴-┴-┴-┘012345↑↑HT插入F發(fā)生假“溢出”.┌-┬-┬-┬-┬-┬-┐←│││││D│E│←F└-┴-┴-┴-┴-┴-┘012345↑↑HT三、循環(huán)隊(duì)列

循環(huán)隊(duì)列插入Ftail=(tail+1)%6↓↑┌-┬-┬-┬-┬-┬-┐│F││││D│E│└-┴-┴-┴-┴-┴-┘012345↑↑TH插入G,H,隊(duì)列滿(tail+1)%6=head↓↑┌-┬-┬-┬-┬-┬-┐│F│G│H││D│E│└-┴-┴-┴-┴-┴-┘012345↑↑THtail→0

5F1E

4D2

3←head0

5F1EG

4DH2←tail

3←head1.4樹

1.4.1樹及存儲(chǔ)結(jié)構(gòu)一、樹的基本概念定義樹是一個(gè)或多個(gè)結(jié)點(diǎn)的有窮集合T，其中有且僅有一個(gè)指定的稱為樹根(root)的結(jié)點(diǎn)，除樹根之外的其余結(jié)點(diǎn)被分為m(m≥0)個(gè)互不相交的集合T1，T2，...，Tm，每一個(gè)Ti(i=1，2，...，m)又都是樹，并且稱為根的子樹。

例1.一個(gè)結(jié)點(diǎn)的樹

T＝{A}

1.4.1樹及存儲(chǔ)結(jié)構(gòu)

一、樹的基本概念例2.12個(gè)結(jié)點(diǎn)的樹

1T＝{A,B,C,D,E,F,G,H,I,J,K,L}2T1＝{B,E,F,J}Ａ...........第1層

3T11＝{E}／│＼

4T12＝{F,J}／│＼

5T121＝{J}ＢＣＤ......第2層

6T2＝{C}／＼／│＼

7T3＝{D,G,H,I,K,L}／＼／│＼

8T31＝{G,K,L}ＥＦＧＨＩ...第3層

9T311＝{K}││＼

10T312＝{L}││＼

11T32＝{H}ＪＫＬ.......第4層

12T33＝{I}一棵樹的圖示

1.4.1樹及存儲(chǔ)結(jié)構(gòu)

一、樹的基本概念(1)結(jié)點(diǎn)的度：結(jié)點(diǎn)X的子樹數(shù)稱為結(jié)點(diǎn)X的度(degree)(2)樹的度：樹T中各結(jié)點(diǎn)的度的最大值稱為樹T的度。度為d的樹稱為d度樹(3)葉子：樹中度為0的結(jié)點(diǎn)稱為葉子(leaf)或終端結(jié)點(diǎn)(4)分枝結(jié)點(diǎn)(非終端結(jié)點(diǎn)、非葉子)：樹中度不為0的結(jié)點(diǎn)(5)雙親和孩子：若樹中結(jié)點(diǎn)P的一棵子樹的根是結(jié)點(diǎn)C，則稱結(jié)點(diǎn)P是結(jié)點(diǎn)C的雙親或父母(parent)；反之，稱結(jié)點(diǎn)C是結(jié)點(diǎn)P的孩子(child)(6)結(jié)點(diǎn)的層：規(guī)定樹的根結(jié)點(diǎn)的層(level)為1，其余任一結(jié)點(diǎn)的層等于它的雙親的層加1(7)樹的深度：樹T中各結(jié)點(diǎn)的層的最大值稱為樹T的深度或高度(8)兄弟和堂兄弟：同一個(gè)雙親的孩子之間互稱為兄弟(sibling)，其雙親在同一層的結(jié)點(diǎn)互為堂兄弟(9)祖先和子孫：一個(gè)結(jié)點(diǎn)的祖先是指從樹的根到該結(jié)點(diǎn)所經(jīng)分枝上的所有結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)的子樹的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫(10)有序樹和無(wú)序樹：如果樹T中任一結(jié)點(diǎn)的各棵子樹規(guī)定從左至右是有次序的，即不能互換位置，則稱樹T為有序樹；否則樹T為無(wú)序樹(11)森林：n(n>=0)棵互不相交的樹的集合稱為森林1.4.1樹及存儲(chǔ)結(jié)構(gòu)

一、樹的基本概念

例3.有序樹和無(wú)序樹ＡＡＡＡ／＼／＼／＼／＼／＼／＼／＼／＼ＢＣＣＢＢＣＣＢ││││││││ＤＤＤＤ兩棵不同的有序樹兩棵相同的無(wú)序樹

例4.森林F＝{T1,T2,T3}

ＢＣＤ／＼／│＼／＼／│＼ＥＦＧＨＩ││＼││＼ＪＫＬ

T1T2T31.4.2二叉樹及其存儲(chǔ)結(jié)構(gòu)

一、二叉樹的基本概念二叉樹的遞歸定義二叉樹是有限個(gè)結(jié)點(diǎn)的集合，它或者為空集，或者是由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的且分別稱為根的左子樹和右子樹的二叉樹所組成。若二叉樹為空集，則稱之為空二叉樹。

二叉樹的5種基本形態(tài)

ΦＡＡＡＡ／＼／＼／＼／＼ＢＢＢＣ

(1)(2)(3)(4)(5)

空二叉樹只有根結(jié)點(diǎn)有根結(jié)點(diǎn)有根結(jié)點(diǎn)有根結(jié)點(diǎn)左、右子樹左子樹非空左子樹為空左子樹非空為空二叉樹右子樹為空右子樹非空右子樹非空一、二叉樹的基本概念二叉樹和2度樹的區(qū)別

(1)二叉樹的度小于等于2；而2度樹的度等于2。

(2)二叉樹的左子樹和右子樹是有序的；而2度樹可以不規(guī)定各子樹之間的次序，即可以是有序樹，也可以是無(wú)序樹。

例.

ＡＡＡＡ／＼／＼／＼／≠＼／＼／＼ＢＢＢＣＣＢ

T1T2T4T5

T1、T2是兩棵不同的二叉樹，但不是2度樹。

T4、T5是兩棵不同的二叉樹；是相同的無(wú)序2度樹。一、二叉樹的基本概念具有3個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹

○○○○○／＼／／＼＼／＼／／＼＼○○○○○○／＼／／＼／○○○

T1T2T3T4T5

一、二叉樹的基本概念性質(zhì)1：在任意二叉樹的第ｉ層上，最多有２i-1個(gè)結(jié)點(diǎn)(ｉ≥1)。例.○.............第1層２1-1

＝1

／＼／＼／＼○○.........第2層２2-1

＝2

／＼／＼／＼／＼○○○○......第3層２3-1

＝4

／＼／＼／＼／＼○○○○○○○○.....第4層２4-1

＝8

二、二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹最多有2k

－1(k≥1)個(gè)結(jié)點(diǎn)。由性質(zhì)1知，深度為ｋ的二叉樹的結(jié)點(diǎn)總數(shù)最多為：

kki－1∑(第ｉ層上結(jié)點(diǎn)的最多數(shù)目）＝∑2i=1i=1

例.T4T1T2T3○○○○／＼／＼／＼／＼／＼／＼／＼○○○○○○／＼／＼／＼／＼○○○○／＼／＼○○○○／＼／＼／＼／＼○○○○○○○○21－1＝122－1＝323－1＝724－1＝15二、二叉樹的性質(zhì)性質(zhì)3：對(duì)于任一非空二叉樹，如果它的葉子數(shù)目為ｎ0，度為2的結(jié)點(diǎn)數(shù)目為ｎ2，則有：ｎ0＝ｎ2＋１(2n2+1=n0+n2)

例

T1T2T3T4

○○○○

／／＼／＼／／＼／＼○○○○○＼／＼／＼／＼＼／＼／＼／＼○○○○○○○／＼／＼＼／＼／＼／＼＼／＼○○○○○○○

ｎ0＝1ｎ0＝2ｎ0＝4ｎ0＝5

ｎ2＝0ｎ2＝1ｎ2＝3ｎ2＝4三、特殊二叉樹特殊二叉樹滿二叉樹、完全二叉樹(1)滿二叉樹:深度為k的具有2k

－1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹(k≥1).

例：

T1T2T3T4○○○○／＼／＼／＼／＼／＼／＼／＼○○○○○○／＼／＼／＼／＼○○○○／＼／＼○○○○／＼／＼／＼／＼○○○○○○○○

k＝1k＝2k＝3k＝421

－1＝122

－1＝323

－1＝724

－1＝15三、特殊二叉樹

順序編號(hào)的滿二叉樹:從根結(jié)點(diǎn)開(kāi)始，從上至下；同層的結(jié)點(diǎn)從左至右；n個(gè)結(jié)點(diǎn)的滿二叉樹，依次用1，2，…，n順序編號(hào)。

例.順序編號(hào)的滿二叉樹

T1T2T3①①①

／＼／＼／＼／＼②③②③／＼／＼／＼／＼④⑤⑥⑦

n＝1n＝3n＝7

滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)與樹的深度之間的關(guān)系：具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度為log2（n＋1）。依定義,一棵深度為k的滿二叉樹有2k

－1個(gè)結(jié)點(diǎn)），有：

2k

－1＝n三、特殊二叉樹(2)完全二叉樹若二叉樹的任一結(jié)點(diǎn)深度為k,有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)

，則稱該二叉樹為完全二叉樹。例.完全二叉樹

T1