數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)隊(duì)列棧二叉樹(shù)圖第一頁(yè)，共40頁(yè)?！惨弧场⒕€性表線性表是n個(gè)類型(lèixíng)相同的數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間是一對(duì)一的關(guān)系，即每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼，如圖2.1所示。例如：英文字母表(A,B,…,Z)就是一個(gè)簡(jiǎn)單的線性表，表中的每一個(gè)英文字母是一個(gè)數(shù)據(jù)元素，每個(gè)元素之間存在唯一的順序關(guān)系，如在英文字母(zìmǔ)表字母(zìmǔ)B的前面是字母(zìmǔ)A，而字母(zìmǔ)B后面是字母(zìmǔ)C。第二頁(yè)，共40頁(yè)?！捕场Ｊ窃试S在一端(yīduān)進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端(yīduān)稱為棧頂(top)，另一端(yīduān)為棧底(bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。棧結(jié)構(gòu)也稱為后進(jìn)先出表〔LIFO〕。a1a2……an棧底棧頂MAXSIZETOP第三頁(yè)，共40頁(yè)。隊(duì)列(Queue)的定義隊(duì)列是限定僅在表的一端進(jìn)行插入，在另一端進(jìn)行刪除操作的線性表。允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端稱為隊(duì)首(front)。隊(duì)列的插入操作，稱為入隊(duì)；隊(duì)列的刪除操作，稱為出隊(duì)。當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。設(shè)隊(duì)列q=(a0，a1，a2，…，an-1)，那么a0稱為隊(duì)頭元素，an-1稱為隊(duì)尾元素。元素按a0，a1，a2，…，an-1的次序入隊(duì)，出隊(duì)也只能按照(ànzhào)這個(gè)次序。隊(duì)列和棧相反，隊(duì)列的操作是按先進(jìn)先出〔FirstInFirstOut〕的原那么進(jìn)行的，又稱為先進(jìn)先出的線性表〔簡(jiǎn)稱FIFO表〕。三、隊(duì)列(duìliè)第四頁(yè)，共40頁(yè)。〔四〕、二叉樹(shù)類型(lèixíng)與定義第五頁(yè)，共40頁(yè)。二叉樹(shù)或?yàn)榭諛?shù)；或是由一個(gè)(yīɡè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不交的二叉樹(shù)組成。ABCDEFGHK根結(jié)點(diǎn)(jiédiǎn)左子樹(shù)右子樹(shù)EF第六頁(yè)，共40頁(yè)。二叉樹(shù)的五種(wǔzhǒnɡ)根本形態(tài)：N空樹(shù)只含根結(jié)點(diǎn)(jiédiǎn)NNNLRR右子樹(shù)為空樹(shù)L左子樹(shù)為空樹(shù)左右(zuǒyòu)子樹(shù)均不為空樹(shù)第七頁(yè)，共40頁(yè)。介紹根本(gēnběn)術(shù)語(yǔ)葉子結(jié)點(diǎn)(jiédiǎn)結(jié)點(diǎn)(jiédiǎn)結(jié)點(diǎn)(jiédiǎn)總數(shù)深度層abcdefghij結(jié)點(diǎn)的層次從根開(kāi)始定義起，根為第一層，根的孩子為第二層，依次累計(jì)。樹(shù)中結(jié)點(diǎn)的最大層次稱為(chēnɡwéi)樹(shù)的深度或高度。第八頁(yè)，共40頁(yè)。性質(zhì)(xìngzhì)1：

在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)用歸納法證明(zhèngmíng)：歸納基：歸納假設(shè)：歸納證明(zhèngmíng)：i=1層時(shí)，只有(zhǐyǒu)一個(gè)根結(jié)點(diǎn)，2i-1=20=1；假設(shè)對(duì)所有的j，1≤j

i，命題成立;二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，那么第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1。第九頁(yè)，共40頁(yè)。性質(zhì)(xìngzhì)2：

深度為k的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)〔k≥1〕證明(zhèngmíng)：基于上一條性質(zhì)，深度(shēndù)為k的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為20+21++2k-1=2k-1第十頁(yè)，共40頁(yè)。性質(zhì)3：

對(duì)任何一棵二叉樹(shù)，假設(shè)它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，那么(nàme)必存在關(guān)系式：n0=n2+1證明(zhèngmíng)：設(shè)二叉樹(shù)上結(jié)點(diǎn)(jiédiǎn)總數(shù)n=n0+n1+n2又二叉樹(shù)上分支總數(shù)b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1第十一頁(yè)，共40頁(yè)。兩類特殊(tèshū)的二叉樹(shù)：滿二叉樹(shù)：指的是深度為k且含有(hányǒu)2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)：樹(shù)中所含的n個(gè)結(jié)點(diǎn)(jiédiǎn)和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)(jiédiǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij第十二頁(yè)，共40頁(yè)。性質(zhì)(xìngzhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1證明(zhèngmíng)：設(shè)完全(wánquán)二叉樹(shù)的深度為k那么根據(jù)第二條性質(zhì)得2k-1≤n<2k即k-1≤log2n<k

因?yàn)閗只能是整數(shù)，因此，k=log2n

+1第十三頁(yè)，共40頁(yè)。滿二叉樹(shù)的葉節(jié)點(diǎn)(jiédiǎn)為N，那么它的節(jié)點(diǎn)(jiédiǎn)總數(shù)〔〕A、NB、2NC、2N-1D、2N+1E、2^N-1高度為n的均衡的二叉樹(shù)是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹(shù)枝，它應(yīng)該是高度為n-1的滿二叉樹(shù)。在這里，樹(shù)高等于葉結(jié)點(diǎn)的最大深度(shēndù)，根結(jié)點(diǎn)的深度(shēndù)為0，如果某個(gè)均衡的二叉樹(shù)共有2381個(gè)結(jié)點(diǎn)，那么該樹(shù)的樹(shù)高為〔〕。

A.10B.11C.12D.13

第十四頁(yè)，共40頁(yè)。二叉樹(shù)的遍歷(biànlì)第十五頁(yè)，共40頁(yè)。順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)(fǎngwèn)一次，而且僅被訪問(wèn)(fǎngwèn)一次。一、問(wèn)題(wèntí)的提出“訪問(wèn)〞的含義可以(kěyǐ)很廣，如：輸出結(jié)點(diǎn)的信息等。第十六頁(yè)，共40頁(yè)。對(duì)“二叉樹(shù)〞而言，可以有三條搜索(sōusuǒ)路徑：1．先上后下的按層次(céngcì)遍歷；2．先左〔子樹(shù)〕后右〔子樹(shù)〕的遍歷；3．先右〔子樹(shù)〕后左〔子樹(shù)〕的遍歷。第十七頁(yè)，共40頁(yè)。二、先左后右的遍歷(biànlì)算法先〔根〕序的遍歷(biànlì)算法中〔根〕序的遍歷(biànlì)算法后〔根〕序的遍歷算法根左子樹(shù)右子樹(shù)根根根根根第十八頁(yè)，共40頁(yè)。假設(shè)二叉樹(shù)為空樹(shù)，那么空操作；否那么，〔1〕訪問(wèn)根結(jié)點(diǎn)(jiédiǎn)；〔2〕先序遍歷左子樹(shù)；〔3〕先序遍歷右子樹(shù)。先〔根〕序的遍歷(biànlì)算法：第十九頁(yè)，共40頁(yè)。假設(shè)二叉樹(shù)為空樹(shù)，那么(nàme)空操作；否那么(nàme)，〔1〕中序遍歷左子樹(shù)；〔2〕訪問(wèn)根結(jié)點(diǎn)；〔3〕中序遍歷右子樹(shù)。中〔根〕序的遍歷(biànlì)算法：第二十頁(yè)，共40頁(yè)。假設(shè)二叉樹(shù)為空樹(shù)，那么空操作；否那么，〔1〕后序(hòuxù)遍歷左子樹(shù)；〔2〕后序(hòuxù)遍歷右子樹(shù)；〔3〕訪問(wèn)根結(jié)點(diǎn)。后〔根〕序的遍歷(biànlì)算法：第二十一頁(yè)，共40頁(yè)。ABCDEFGHK例如(lìrú)：先序序列(xùliè)：中序序列(xùliè)：后序序列：A

BCD

EFGHKBDCA

EHGKFDCBHKGFE

A第二十二頁(yè)，共40頁(yè)。第二十九頁(yè)，共40頁(yè)。只含根結(jié)點(diǎn)(jiédiǎn)對(duì)“二叉樹(shù)〞而言，可以有三條搜索(sōusuǒ)路徑：結(jié)點(diǎn)的層次從根開(kāi)始定義起，根為第一層，根的孩子為第二層，依次累計(jì)。第二十三頁(yè)，共40頁(yè)。第二十七頁(yè)，共40頁(yè)。第二十六頁(yè)，共40頁(yè)。通路指u-->邊1-->頂點(diǎn)1-->邊2-->頂點(diǎn)2-->……-->v，點(diǎn)和邊交替(jiāotì)相接，且互不相同。人們建造了7座橋?qū)⑦@4個(gè)地區(qū)連起來(lái)。人們建造了7座橋?qū)⑦@4個(gè)地區(qū)連起來(lái)。無(wú)向圖與有向圖：邊的表示方式是用該邊的兩個(gè)頂點(diǎn)來(lái)表示的，如果邊的表示無(wú)方向，那么(nàme)，對(duì)應(yīng)的圖就是無(wú)向圖，否那么(nàme)稱為有向圖，如以下圖所示：或是由一個(gè)(yīɡè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不交的二叉樹(shù)組成?；蚴怯梢粋€(gè)(yīɡè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不交的二叉樹(shù)組成?！灿邢驁D中邊的表示用尖括號(hào)〕〔無(wú)向圖中邊的表示用圓括號(hào)〕

在有向圖中，邊的走向不同就認(rèn)為是不同的邊。前綴(qiánzhuì)、后綴表達(dá)式二叉樹(shù)的應(yīng)用。中綴表達(dá)式轉(zhuǎn)換(zhuǎnhuàn)后綴表達(dá)式從左向右掃描表達(dá)式、運(yùn)算數(shù)送到輸出隊(duì)列、運(yùn)算符進(jìn)棧、如果運(yùn)算優(yōu)先級(jí)大于棧頂元素直接進(jìn)棧，如果運(yùn)算優(yōu)先級(jí)小于或等于棧頂元素，那么先彈出棧頂元素，再進(jìn)棧、左括號(hào)直接進(jìn)棧、右括號(hào)那么依次彈出棧中的元素，直到遇到第一個(gè)左括號(hào)為止。有些題目要求寫(xiě)出前綴、中綴和后綴表達(dá)式，做這類題目時(shí)，可以先通過(guò)優(yōu)先級(jí)畫(huà)出一棵二叉樹(shù)再分別利用先根、中根和后根遍歷寫(xiě)出對(duì)應(yīng)的序列，就是它們的前綴、中綴和后綴表達(dá)式。第二十三頁(yè)，共40頁(yè)。表達(dá)式a*(b+c)-d的后綴表達(dá)式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd假設(shè)一棵二叉樹(shù)的后序(hòuxù)遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，那么其前序遍歷序列為。一棵二叉樹(shù)的中序遍歷序列為：DGBAECHF，后序(hòuxù)遍歷序列為：GDBEHFCA，那么前序列遍歷序列是__。第二十四頁(yè)，共40頁(yè)。數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)之——圖什么(shénme)是圖

什么是計(jì)算機(jī)中所說(shuō)(suǒshuō)的圖?請(qǐng)先看下面的“柯尼斯堡橋問(wèn)題〞。傳說(shuō)在東普魯士境內(nèi)，有一座柯尼斯堡城，希雷格爾河流經(jīng)這個(gè)城市的克奈霍福島后，就將這個(gè)城市一分為二，形成如圖1—1〔左〕的A、B、C、D4個(gè)地區(qū)。人們建造了7座橋?qū)⑦@4個(gè)地區(qū)連起來(lái)。在游覽中有人提出，是否可以從A地出發(fā)，各座橋恰好通過(guò)一次，最后又回到原來(lái)出發(fā)地呢?第二十五頁(yè)，共40頁(yè)。這個(gè)問(wèn)題在18世紀(jì)被數(shù)學(xué)家歐拉解決了。他把這個(gè)問(wèn)題轉(zhuǎn)化為圖1—1右邊所示的圖。圖上用A、B、C、D4個(gè)頂點(diǎn)分別表示4個(gè)地區(qū)(dìqū)，用兩點(diǎn)間的線段表示連接各地的橋。這樣原來(lái)的問(wèn)題就轉(zhuǎn)化為：從A頂點(diǎn)出發(fā)經(jīng)過(guò)其中每一條線段一次，而且僅一次，再回到A點(diǎn)的“一筆畫(huà)〞問(wèn)題。

歐拉對(duì)柯尼斯堡問(wèn)題作出了否認(rèn)的結(jié)論。因?yàn)閷?duì)于每一個(gè)頂點(diǎn)，不管如何經(jīng)過(guò)，必須有一條進(jìn)路和一條出路，所以對(duì)每一個(gè)頂點(diǎn)(除起點(diǎn)和終點(diǎn))來(lái)說(shuō)與它有關(guān)的線段(稱為邊)必須是偶數(shù)條。而圖1-1(右)的頂點(diǎn)有關(guān)的線段都是奇數(shù)條，因此不可能一筆畫(huà)出。第二十六頁(yè)，共40頁(yè)。歐拉通過(guò)對(duì)柯尼斯堡橋問(wèn)題(wèntí)的研究，于1736年發(fā)表了著名的關(guān)于圖論的論文，從而創(chuàng)立了圖論的學(xué)說(shuō)。圖1—2一類的問(wèn)題(wèntí)就是圖論中所指的圖。

第二十七頁(yè)，共40頁(yè)。第二十七頁(yè)，共40頁(yè)。在這里，樹(shù)高等于葉結(jié)點(diǎn)的最大深度(shēndù)，根結(jié)點(diǎn)的深度(shēndù)為0，如果某個(gè)均衡的二叉樹(shù)共有2381個(gè)結(jié)點(diǎn)，那么該樹(shù)的樹(shù)高為〔〕。性質(zhì)(xìngzhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1左右(zuǒyòu)子樹(shù)均不為空樹(shù)或者(huòzhě)定義：圖G〔Graph〕是由頂點(diǎn)的集合V和邊的集合E所組成的二元組，記作：G=〔V，E〕人們建造了7座橋?qū)⑦@4個(gè)地區(qū)連起來(lái)?！霸L問(wèn)〞的含義可以(kěyǐ)很廣，如：輸出結(jié)2．先左〔子樹(shù)〕后右〔子樹(shù)〕的遍歷；數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)隊(duì)列棧二叉樹(shù)圖假設(shè)二叉樹(shù)為空樹(shù)，那么(nàme)空操作；二叉樹(shù)或?yàn)榭諛?shù)；二叉樹(shù)的遍歷(biànlì)在無(wú)向圖中，邊的兩個(gè)頂點(diǎn)在邊的表示中可以互換，如邊〔V1,V4〕與邊〔V4,V1〕是等價(jià)的，表示的是同一條邊。棧是允許在一端(yīduān)進(jìn)行插入和刪除操作的特殊線性表。二、先左后右的遍歷(biànlì)算法例如圖1—3中分別是6和3。左右(zuǒyòu)子樹(shù)均不為空樹(shù)又如，有6個(gè)足球隊(duì)之間進(jìn)行循環(huán)賽，他們比賽的場(chǎng)次可以用圖1-3(1)來(lái)表示。有3個(gè)人(gèrén)相互寫(xiě)信，可以用圖1—3(2)來(lái)表示。第二十八頁(yè)，共40頁(yè)。從上面兩個(gè)例子可看出(kànchū)，我們這里所說(shuō)的圖(graph)，與人們通常所熟悉的圖，如圓、四邊形、函數(shù)圖象等是很不相同的。是指某些具體事物和這些事物之間的聯(lián)系。如果我們用點(diǎn)來(lái)表示事物(如地點(diǎn)、隊(duì))，用線段來(lái)表示兩事物之間的聯(lián)系，那么一個(gè)圖就是表示事物的點(diǎn)集和表示事物之間聯(lián)系的線段集合所構(gòu)成。其中線段僅表示兩點(diǎn)的關(guān)系，它的長(zhǎng)短與曲直是無(wú)關(guān)緊要的。例如圖1-4中3個(gè)圖，被認(rèn)為是同一個(gè)圖。第二十九頁(yè)，共40頁(yè)。圖的根本(gēnběn)概念定義：圖G定義為一個(gè)偶對(duì)(V，E)，記作G：(V，E)。其中

1)V是一個(gè)非空有限集合，它的元素稱為頂點(diǎn)；

2)E也是一個(gè)集合，它的元素稱為邊

例如圖1-4中的圖有4個(gè)頂點(diǎn)，4條邊。

或者(huòzhě)定義：圖G〔Graph〕是由頂點(diǎn)的集合V和邊的集合E所組成的二元組，記作：G=〔V，E〕其中V是頂點(diǎn)的集合，E是邊的集合。第三十頁(yè)，共40頁(yè)。無(wú)向圖與有向圖：邊的表示方式是用該邊的兩個(gè)頂點(diǎn)來(lái)表示的，如果邊的表示無(wú)方向，那么(nàme)，對(duì)應(yīng)的圖就是無(wú)向圖，否那么(nàme)稱為有向圖，如以下圖所示：在無(wú)向圖中，邊的兩個(gè)頂點(diǎn)在邊的表示中可以互換，如邊〔V1,V4〕與邊〔V4,V1〕是等價(jià)的，表示的是同一條邊。〔無(wú)向圖中邊的表示用圓括號(hào)〕

在有向圖中，邊的走向不同就認(rèn)為是不同的邊。如在邊的集合E={<1,4>,<3,4>,<5,2>,<5,3>,<2,1>,<5,5>}(見(jiàn)右上圖)中，其中(qízhōng)<1,4>表示該邊是由頂點(diǎn)1出發(fā)，到頂點(diǎn)4結(jié)束，即邊<1,4>說(shuō)明了該邊的方向性，且兩個(gè)頂點(diǎn)的順序不能顛倒?！灿邢驁D中邊的表示用尖括號(hào)〕第三十一頁(yè)，共40頁(yè)。頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目(shùmù)，有向圖頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。

入度——以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目(shùmù)和出度——以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目(shùmù)和圖的階：圖中頂點(diǎn)的個(gè)數(shù)。例如圖1—3中分別是6和3。

度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。

第三十二頁(yè)，共40頁(yè)。[定理1]圖G中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。因?yàn)橛?jì)算頂點(diǎn)的度數(shù)時(shí)。每條邊均用到2次。

[定理2]任意一個(gè)(yīɡè)圖一定有偶數(shù)個(gè)奇點(diǎn)。

第三十三頁(yè)，共40頁(yè)。連通：如果圖中結(jié)點(diǎn)U，V之間存在一條從U通過(guò)假設(shè)干條邊、點(diǎn)到達(dá)(dàodá)V的通路，稱U、V是連通的。連通圖：如果一個(gè)無(wú)向圖中,任一對(duì)不同頂點(diǎn)U、V，都有一條〔U，V〕通路，那么稱圖G是連通的。強(qiáng)連通圖：在有向圖G中，每一對(duì)結(jié)點(diǎn)之間都有路徑的圖。網(wǎng)絡(luò)：帶權(quán)的連通圖。BACDFE第三十四頁(yè)，共40頁(yè)。連通：如果頂點(diǎn)u，v屬于G，u，v之間有一