數(shù)據(jù)結(jié)構(gòu)線性表、棧、隊(duì)列、二叉樹、圖

常見數(shù)據(jù)結(jié)構(gòu)線性表、棧、隊(duì)列、二叉樹、圖（一）、線性表線性表是n個(gè)類型相同的數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間是一對(duì)一的關(guān)系，即每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼，如圖2.1所示。例如：英文字母表(A,B,…,Z)就是一個(gè)簡單的線性表，表中的每一個(gè)英文字母是一個(gè)數(shù)據(jù)元素，每個(gè)元素之間存在唯一的順序關(guān)系，如在英文字母表字母B的前面是字母A，而字母B后面是字母C。（二）、棧棧是允許在一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。棧結(jié)構(gòu)也稱為后進(jìn)先出表（LIFO）。

a1a2……an棧底棧頂MAXSIZETOP（四）、二叉樹類型與定義

二叉樹或?yàn)榭諛?；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹EF二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹

性質(zhì)1：

在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時(shí)，只有一個(gè)根結(jié)點(diǎn)，

2i-1=20=1；假設(shè)對(duì)所有的j，1≤j

i，命題成立;二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1

。性質(zhì)2：

深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)（k≥1）證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為

20+21+

+2k-1=2k-1

性質(zhì)3：

對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1證明：設(shè)二叉樹上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1

性質(zhì)4：

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

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

+1滿二叉樹的葉節(jié)點(diǎn)為N，則它的節(jié)點(diǎn)總數(shù)（）A、NB、2NC、2N-1D、2N+1E、2^N-1

高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0，如果某個(gè)均衡的二叉樹共有2381個(gè)結(jié)點(diǎn)，則該樹的樹高為（）。

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

二叉樹的遍歷對(duì)“二叉樹”而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法根左子樹右子樹根根根根根

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。后（根）序的遍歷算法：ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDCA

EHGKFDCBHKGFE

A前綴、后綴表達(dá)式二叉樹的應(yīng)用。中綴表達(dá)式轉(zhuǎ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)為止。有些題目要求寫出前綴、中綴和后綴表達(dá)式，做這類題目時(shí)，可以先通過優(yōu)先級(jí)畫出一棵二叉樹再分別利用先根、中根和后根遍歷寫出對(duì)應(yīng)的序列，就是它們的前綴、中綴和后綴表達(dá)式。

數(shù)據(jù)結(jié)構(gòu)之——圖什么是圖

什么是計(jì)算機(jī)中所說的圖?請先看下面的“柯尼斯堡橋問題”。傳說在東普魯士境內(nèi)，有一座柯尼斯堡城，希雷格爾河流經(jīng)這個(gè)城市的克奈霍福島后，就將這個(gè)城市一分為二，形成如圖1—1（左）的A、B、C、D4個(gè)地區(qū)。人們建造了7座橋?qū)⑦@4個(gè)地區(qū)連起來。在游覽中有人提出，是否可以從A地出發(fā)，各座橋恰好通過一次，最后又回到原來出發(fā)地呢?

這個(gè)問題在18世紀(jì)被數(shù)學(xué)家歐拉解決了。他把這個(gè)問題轉(zhuǎn)化為圖1—1右邊所示的圖。圖上用A、B、C、D4個(gè)頂點(diǎn)分別表示4個(gè)地區(qū)，用兩點(diǎn)間的線段表示連接各地的橋。這樣原來的問題就轉(zhuǎn)化為：從A頂點(diǎn)出發(fā)經(jīng)過其中每一條線段一次，而且僅一次，再回到A點(diǎn)的“一筆畫”問題。

歐拉對(duì)柯尼斯堡問題作出了否定的結(jié)論。因?yàn)閷?duì)于每一個(gè)頂點(diǎn)，不論如何經(jīng)過，必須有一條進(jìn)路和一條出路，所以對(duì)每一個(gè)頂點(diǎn)(除起點(diǎn)和終點(diǎn))來說與它有關(guān)的線段(稱為邊)必須是偶數(shù)條。而圖1-1(右)的頂點(diǎn)有關(guān)的線段都是奇數(shù)條，因此不可能一筆畫出。從上面兩個(gè)例子可看出，我們這里所說的圖(graph)，與人們通常所熟悉的圖，如圓、四邊形、函數(shù)圖象等是很不相同的。是指某些具體事物和這些事物之間的聯(lián)系。如果我們用點(diǎn)來表示事物(如地點(diǎn)、隊(duì))，用線段來表示兩事物之間的聯(lián)系，那么一個(gè)圖就是表示事物的點(diǎn)集和表示事物之間聯(lián)系的線段集合所構(gòu)成。其中線段僅表示兩點(diǎn)的關(guān)系，它的長短與曲直是無關(guān)緊要的。例如圖1-4中3個(gè)圖，被認(rèn)為是同一個(gè)圖。圖的基本概念定義：圖G定義為一個(gè)偶對(duì)(V，E)，記作G：(V，E)。其中

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

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

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

或者定義：圖G（Graph）是由頂點(diǎn)的集合V和邊的集合E所組成的二元組，記作：G=（V，E）其中V是頂點(diǎn)的集合，E是邊的集合。無向圖與有向圖：邊的表示方式是用該邊的兩個(gè)頂點(diǎn)來表示的，如果邊的表示無方向，那么，對(duì)應(yīng)的圖就是無向圖，否則稱為有向圖，如下圖所示：

在無向圖中，邊的兩個(gè)頂點(diǎn)在邊的表示中可以互換，如邊（V1,V4）與邊（V4,V1）是等價(jià)的，表示的是同一條邊。（無向圖中邊的表示用圓括號(hào)）

在有向圖中，邊的走向不同就認(rèn)為是不同的邊。如在邊的集合E={<1,4>,<3,4>,<5,2>,<5,3>,<2,1>,<5,5>}(見右上圖)中，其中<1,4>表示該邊是由頂點(diǎn)1出發(fā)，到頂點(diǎn)4結(jié)束，即邊<1,4>表明了該邊的方向性，且兩個(gè)頂點(diǎn)的順序不能顛倒。（有向圖中邊的表示用尖括號(hào)）頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目，有向圖頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。

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

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

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

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

連通：如果圖中結(jié)點(diǎn)U，V之間存在一條從U通過若干條邊、點(diǎn)到達(dá)V的通路，稱U、V是連通的。連通圖：如果一個(gè)無向圖中,任一對(duì)不同頂點(diǎn)U、V，都有一條（U，V）通路，則稱圖G是連通的。強(qiáng)連通圖：在有向圖G中，每一對(duì)結(jié)點(diǎn)之間都有路徑的圖。網(wǎng)絡(luò)：帶權(quán)的連通圖。BACDFE連通：如果頂點(diǎn)u，v屬于G，u，v之間有一條從u通過若干條邊到達(dá)v的通路，則認(rèn)為頂點(diǎn)u和v是連通的。

連通圖：如果對(duì)于圖G中每一對(duì)不同頂點(diǎn)u，v都有一條(u，v)通路，則稱G是連通圖。

通路指u-->邊1-->頂點(diǎn)1-->邊2-->頂點(diǎn)2-->……-->v，點(diǎn)和邊交替相接，且互不相同。

圖的遍歷1、概念：從圖中某一結(jié)點(diǎn)出發(fā)系統(tǒng)地訪問圖中所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被訪問一次，這種運(yùn)算稱圖的遍歷。為了避免重復(fù)訪問某個(gè)結(jié)點(diǎn)，可以設(shè)一個(gè)標(biāo)志數(shù)組visited[I]，未訪問時(shí)值為FALSE，訪問一次后就改為TRUE。2、分類：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

深度優(yōu)先遍歷：類似于樹的先序遍歷，從圖中某個(gè)結(jié)點(diǎn)V0出發(fā)，訪問此結(jié)點(diǎn)，然后依次訪問從V0的未被訪問的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷，直到圖中所有和V0有路徑相通的結(jié)點(diǎn)均被訪問到。若此時(shí)圖中尚有結(jié)點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的結(jié)點(diǎn)V1作為起點(diǎn)，重復(fù)上述過程，直至圖中所有結(jié)點(diǎn)都被訪問到為止。廣