數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第1頁。《數(shù)據(jù)結(jié)構(gòu)》概念

數(shù)據(jù)結(jié)構(gòu)研究計(jì)算機(jī)非數(shù)值計(jì)算問題中的數(shù)據(jù)對象以及它們之間的關(guān)系和操作算法，具體主要包含三個方面的內(nèi)容：①數(shù)據(jù)的邏輯結(jié)構(gòu)--數(shù)據(jù)關(guān)系之間的邏輯關(guān)系②數(shù)據(jù)的存儲結(jié)構(gòu)--數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示③操作算法----插入、刪除、修改、查詢、排序等

程序=數(shù)據(jù)結(jié)構(gòu)+算法

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第2頁。其中，數(shù)據(jù)的邏輯結(jié)構(gòu)：集合線性結(jié)構(gòu)-----表、棧、隊(duì)列非線性結(jié)構(gòu)-----樹、圖數(shù)據(jù)的存儲結(jié)構(gòu)：

順序存儲結(jié)構(gòu)-----數(shù)組鏈?zhǔn)酱鎯Y(jié)構(gòu)-----指針。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)主要強(qiáng)調(diào)兩個方面的內(nèi)容：①數(shù)據(jù)之間的關(guān)系，即數(shù)據(jù)之間的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；②針對這些關(guān)系的基本操作。類與數(shù)據(jù)結(jié)構(gòu)之間的對應(yīng)關(guān)系:數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第4頁。1.棧(Stack)及其應(yīng)用1。1棧的概念只允許在一端插入和刪除的表允許插入和刪除的一端稱為棧頂

(top)，另一端稱為棧底(bottom)特點(diǎn)后進(jìn)先出(LIFO)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第5頁。進(jìn)棧示例

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第6頁。出棧示例數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第7頁。棧的基本操作1、初始化2、進(jìn)棧PUSH3、出棧POP4、取棧頂元素GetTop5、判棧是否非空數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第8頁。1。2棧的應(yīng)用NOIP2005試題：《等價(jià)表達(dá)式》問題描述明明進(jìn)了中學(xué)之后，學(xué)到了代數(shù)表達(dá)式。有一天，他碰到一個很麻煩的選擇題。這個題目的題干中首先給出了一個代數(shù)表達(dá)式，然后列出了若干選項(xiàng)，每個選項(xiàng)也是一個代數(shù)表達(dá)式，題目的要求是判斷選項(xiàng)中哪些代數(shù)表達(dá)式是和題干中的表達(dá)式等價(jià)的。這個題目手算很麻煩，因?yàn)槊髅鲗τ?jì)算機(jī)編程很感興趣，所以他想是不是可以用計(jì)算機(jī)來解決這個問題。假設(shè)你是明明，能完成這個任務(wù)嗎？這個選擇題中的每個表達(dá)式都滿足下面的性質(zhì)：

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第9頁。

表達(dá)式只可能包含一個變量‘a(chǎn)’。表達(dá)式中出現(xiàn)的數(shù)都是正整數(shù)，而且都小于10000。表達(dá)式中可以包括四種運(yùn)算‘+’（加），‘-’（減），‘*’（乘），‘^’（乘冪），以及小括號‘(’，‘)’。小括號的優(yōu)先級最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’?！?’和‘-’的優(yōu)先級是相同的。相同優(yōu)先級的運(yùn)算從左到右進(jìn)行。（注意：運(yùn)算符‘+’，‘-’，‘*’，‘^’以及小括號‘(’，‘)’都是英文字符）冪指數(shù)只可能是1到10之間的正整數(shù)（包括1和10）。表達(dá)式內(nèi)部，頭部或者尾部都可能有一些多余的空格。下面是一些合理的表達(dá)式的例子：((a^1)^2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1+(a-1)^3，1^10^9……數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第10頁。輸入文件輸入文件equal.in的第一行給出的是題干中的表達(dá)式。第二行是一個整數(shù)n（2<=n<=26），表示選項(xiàng)的個數(shù)。后面n行，每行包括一個選項(xiàng)中的表達(dá)式。這n個選項(xiàng)的標(biāo)號分別是A，B，C，D……

輸入中的表達(dá)式的長度都不超過50個字符，而且保證選項(xiàng)中總有表達(dá)式和題干中的表達(dá)式是等價(jià)的。輸出文件輸出文件equal.out包括一行，這一行包括一系列選項(xiàng)的標(biāo)號，表示哪些選項(xiàng)是和題干中的表達(dá)式等價(jià)的。選項(xiàng)的標(biāo)號按照字母順序排列，而且之間沒有空格。樣例輸入(a+1)^23(a-1)^2+4*aa+1+aa^2+2*a*1+1^2+10-10+a-a樣例輸出AC數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第11頁。關(guān)鍵：如何判斷表達(dá)式等價(jià)？方法1：展開表達(dá)式直接比對，顯然不可取。方法2：求表達(dá)式的值，比對表達(dá)式的值。但對于個體值有可能出現(xiàn)等價(jià)的表達(dá)式其值相等。引入隨機(jī)化思想，隨機(jī)產(chǎn)生幾個a的值，當(dāng)對每個隨機(jī)產(chǎn)生的a值表達(dá)式值都相等時視為表達(dá)式等價(jià)。問題轉(zhuǎn)換：如何求表達(dá)式的值。利用棧實(shí)現(xiàn)表達(dá)式計(jì)算。對表達(dá)式運(yùn)算符定義運(yùn)算優(yōu)先級。算法描述：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第12頁。設(shè)立運(yùn)算符棧和操作數(shù)棧，逐詞讀入表達(dá)式，并處理：1、若讀入為操作數(shù)，則入棧；2、若讀入為運(yùn)算符，則與棧頂運(yùn)算符相比較：（1）若棧頂運(yùn)算符優(yōu)先級高于或等讀入運(yùn)算符，反復(fù)執(zhí)行下列操作，直到棧頂運(yùn)算符優(yōu)先級不高于讀入運(yùn)算符：彈出運(yùn)算符，彈出兩個操作數(shù)，計(jì)算并將結(jié)果入操作數(shù)棧；（2）若棧頂運(yùn)算符優(yōu)先級低于讀入運(yùn)算符，則將讀入運(yùn)算符入棧；

3、若遇到結(jié)束運(yùn)算符，則計(jì)算結(jié)束。4、檢查棧狀態(tài)，得到計(jì)算結(jié)果。程序表達(dá)：閱讀equal.pas數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第13頁。2.1隊(duì)列(

Queue)的概念定義隊(duì)列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)2.隊(duì)(Queue)及其應(yīng)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第14頁。隊(duì)列的基本操作1、構(gòu)造一個隊(duì)列2、進(jìn)隊(duì)操作-----將新元素插入隊(duì)尾3、出隊(duì)操作------隊(duì)列頭元素出隊(duì)4、取隊(duì)列頭元素5、判定隊(duì)列是否為空數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第15頁。隊(duì)列的存儲結(jié)構(gòu)順序存儲------循環(huán)隊(duì)列鏈?zhǔn)酱鎯?-----鏈隊(duì)思考:為什么要構(gòu)造循環(huán)隊(duì)列?

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第16頁。

進(jìn)隊(duì)時隊(duì)尾指針rear=rear+1，將新元素按

rear

指示位置加入。出隊(duì)時隊(duì)頭指針front=front+1，再將下標(biāo)為front的元素取出。

思考：上圖中，元素再進(jìn)隊(duì)，將如何？數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第17頁。出現(xiàn)“假上溢”現(xiàn)象

解決辦法:將存儲數(shù)據(jù)元素的一維數(shù)組看成是頭尾相接的循環(huán)結(jié)構(gòu)即循環(huán)隊(duì)列

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第18頁。循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì)隊(duì)頭指針:front=(front+1)%maxSize;隊(duì)尾指針:rear=(rear+1)%maxSize;隊(duì)列初始化：front=rear=0;數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第19頁。循環(huán)隊(duì)列的隊(duì)空隊(duì)滿問題為了方便起見，約定：初始化建空隊(duì)時，令front=rear=0,

當(dāng)隊(duì)空時：front==rear

當(dāng)隊(duì)滿時：front==rear亦成立

因此，只憑等式front=rear

無法判斷隊(duì)空還是隊(duì)滿。

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第20頁。有三種方法處理上述問題：

①浪費(fèi)一個單元。當(dāng)使用MaxSize-1個單元時即認(rèn)為是隊(duì)滿,此時

(rear+1)%MaxSize==front②設(shè)置一個布爾變量flag。當(dāng)flag==flase時為空，當(dāng)flag==true時為滿。③使用一個計(jì)數(shù)器記錄隊(duì)列中元素的個數(shù)。如num，當(dāng)num==0時隊(duì)空，當(dāng)num==MaxSize時隊(duì)滿。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第21頁。隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第22頁。2.2隊(duì)列的應(yīng)用WINDOWS選自PKU2823問題描述：給你一個長度為N的數(shù)組，一個長為K的滑動的窗體從最左移至最右端，你只能見到窗口的K個數(shù)，每次窗體向右移動一位，如下表：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第23頁。你的任務(wù)是找出窗口在各位置時的maxvalue,minvalue.輸入格式：第1行n,k,第2行為長度為n的數(shù)組輸出格式：2行，第1行每個位置的minvalue,第2行每個位置的maxvalue數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第24頁。樣例：window.in8313-1-35367window.out-1-3-3-333335567數(shù)據(jù)范圍：20%：n<=500;50%:n<=100000;100%:n<=1000000;數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第25頁。分析：方法1：樸素算法枚舉WINDOWS左端位置，求得每個區(qū)間長度為K的數(shù)中的最大值和最小值。效率為O(n*k)。顯然，在n次的k次中有許多的重復(fù)工作。分析數(shù)據(jù)：以求區(qū)間最小值為例。[13-1]-35367q:{-1},最小值為-11[3-1-3]5367q:{-3}新加入數(shù)小于-1,顯然-1無用了，最小數(shù)為-313[-1-35]367q:{-3，5}新加入數(shù)大于-3，保留，最小數(shù)為-313-1[-353]67q:{-3，3}新加入數(shù)小于5,顯然5無用了，最小數(shù)為-313-1-3[536]7q:{3，6}新加入數(shù)大于3，保留，但-3已移出區(qū)間，刪除，最小數(shù)為313-1-35[367]q:{3，6，7}新加入數(shù)大于6，保留，最小數(shù)為-3

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第26頁。總結(jié)操作過程：把q序列看成一個隊(duì)列，每次從尾部加入一個新的數(shù)，如果它比隊(duì)尾還小，則隊(duì)尾的這個數(shù)不可能成為之后任何一個區(qū)間的最小值，刪除隊(duì)尾元素后入隊(duì)，如果它比隊(duì)尾元素大，入隊(duì)。同時，當(dāng)隊(duì)頭留在隊(duì)中的次數(shù)超過k時隊(duì)頭數(shù)據(jù)出隊(duì)，因?yàn)樗辉谙乱粋€區(qū)間內(nèi)了。這樣，區(qū)間的最小值總是當(dāng)前隊(duì)列的隊(duì)頭。依此類推，即可得解。

q序列為單調(diào)隊(duì)列。它首先是一個隊(duì)列，每一個時刻，隊(duì)列元素值是單調(diào)的，同時支持入隊(duì)和出隊(duì)，但是出隊(duì)有從隊(duì)頭出和隊(duì)尾出兩種。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第27頁。方法2：單調(diào)隊(duì)列，每個數(shù)都進(jìn)隊(duì)、出隊(duì)一次，算法效率為O(N)。

procedurework; {設(shè)原始數(shù)據(jù)存入q[i]中}Vari,top,tail:longint;

begin top:=1;tail:=1; queue[top]:=1;//隊(duì)頭指向q[i]中第一個數(shù)

fori:=2tokdo//前k個數(shù)的初始隊(duì)列

begin while(top<=tail)and(q[queue[tail]]>=q[i])dodec(tail);//隊(duì)尾元素大于當(dāng)前元素，出隊(duì)

inc(tail); //當(dāng)前元素入隊(duì)

queue[tail]:=i; end;

單調(diào)隊(duì)列程序框架（以最小值為例）數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第28頁。min[1]:=q[queue[top]];//第1窗口最小值

fori:=2ton-k+1do//窗口左端位置

beginifqueue[top]<itheninc(top);//如果隊(duì)頭指向位置滑出窗口左端，隊(duì)頭出隊(duì)

while(top<=tail)and(q[queue[tail]]>=q[i+k-1])dodec(tail); );//隊(duì)尾元素大于當(dāng)前窗口右端元素，出隊(duì)

inc(tail); queue[tail]:=i+k-1;//當(dāng)前窗口右端元素入隊(duì)

min[i]:=q[queue[top]];//取當(dāng)前窗口最小值

end; end;

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第29頁。

3.二叉樹

3.1二叉樹的定義

二叉樹是一類特殊的樹.(1)二叉樹中的每個結(jié)點(diǎn)至多只有兩棵子樹,即二叉樹中不存在度大于二的結(jié)點(diǎn).(2)二叉樹的由三個基本單元構(gòu)成:根結(jié)點(diǎn),左子樹,右子樹.(3)二叉樹的左右子樹有次序之分,順序不能顛倒.二叉樹的基本形態(tài):數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第30頁。3.2二叉樹的遍歷

問題的提出：在二叉樹的一些應(yīng)用中，為了在樹中查找具有某種特征的結(jié)點(diǎn)，或者對樹中的全部結(jié)點(diǎn)逐一進(jìn)行處理。這樣就提出了一個遍歷二叉樹的問題，即如何按某條搜索路徑尋訪樹中的每個結(jié)點(diǎn)，使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次?！霸L問”的含義很廣，可以是對結(jié)點(diǎn)進(jìn)行處理，如輸出結(jié)點(diǎn)的信息等等。因此對二叉樹而言：可以有三條搜索路徑：（1）先上后下的按層次搜索（2）先左子樹，后右子樹的遍歷（3）先右子樹，后左子樹的遍歷數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第31頁。遍歷二叉樹二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：L：遍歷左子樹

D：訪問根結(jié)點(diǎn)

R：遍歷右子樹

有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD

約定先左后右,有三種遍歷方法：DLR、LDR、LRD

，分別稱為

先序遍歷（先根遍歷）、中序遍歷（中根遍歷）、后序遍歷（后根遍歷）

A

F

G

E

D

C

B數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第32頁。

先序遍歷（DLR）若二叉樹非空

（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；

（3）先序遍歷右子樹；

先序遍歷序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B例：先序遍歷右圖所示的二叉樹（1）訪問根結(jié)點(diǎn)A

（2）先序遍歷左子樹：即按DLR的順序遍歷左子樹（3）先序遍歷右子樹：即按DLR的順序遍歷右子樹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第33頁。中序遍歷（LDR）若二叉樹非空

（1）中序遍歷左子樹

（2）訪問根結(jié)點(diǎn)（3）中序遍歷右子樹

中序遍歷序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍歷右圖所示的二叉樹（1）中序遍歷左子樹：即按LDR的順序遍歷左子樹（2）訪問根結(jié)點(diǎn)A

（3）中序遍歷右子樹：即按LDR的順序遍歷右子樹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第34頁。后序遍歷（LRD）若二叉樹非空

（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問根結(jié)點(diǎn)

后序遍歷序列：D,G,E,B,F,C,A例：后序遍歷右圖所示的二叉樹（1）后序遍歷左子樹：即按LRD的順序遍歷左子樹（2）后序遍歷右子樹：即按LRD的順序遍歷右子樹（3）訪問根結(jié)點(diǎn)A

A

F

G

E

D

C

B數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第35頁。

e

d

c

b

f

a

+

*

/

-

-后序遍歷序列：abcd-*+ef/-表達(dá)式的逆波蘭表示（后綴表達(dá)式）中序遍歷序列：a+b*c-d-e/f中綴表達(dá)式先序遍歷序列：-+a*b-cd/ef表達(dá)式的波蘭表示（前綴表達(dá)式）例：先序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第36頁。

問題1、求先序排列給出一棵二叉樹的中序與后序排列。求出它的先序排列。(約定樹結(jié)點(diǎn)用不同的大寫字母表示，長度≤8)。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第37頁。[分析]我們知道一個后序排列的最后一個字符即為這棵樹的根結(jié)點(diǎn),而這個字符在中序排列中的位置n,n左邊即為其左子樹,n右邊即為其右子樹.并且由于中序遍歷我們是先遍歷左子樹,然后根結(jié)點(diǎn),再遍歷右子樹,而后序遍歷我們是先遍歷左子樹,再遍歷右子樹,最后根結(jié)點(diǎn).所以中序編歷和后序遍歷的第1到n-1位同為當(dāng)前根結(jié)點(diǎn)的左子樹,而中序遍歷的第n+1到length(st)和后序遍歷的第n到length(st)-1位同為當(dāng)前根結(jié)點(diǎn)的右子樹.根據(jù)先序遍歷的規(guī)則,我們就先遞歸處理左子樹,然后遞歸處理右子樹,每次輸出當(dāng)前的根結(jié)點(diǎn),即為先序排列.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第38頁。程序步驟：1、

后序最右端即為根結(jié)點(diǎn)，輸出；2、

在中序中找到根結(jié)點(diǎn)位置S，則該根結(jié)點(diǎn)的左邊即為左子樹，右邊即為右子樹，且后序中1-s為左子樹，s至串長-1為右子樹；3、

以中序與后序的1~s串，遞歸轉(zhuǎn)1，則得到左子樹的先序結(jié)果；4、

以中序的s+1~L-S,后序的S~L-S為串，遞歸轉(zhuǎn)1，則得到右子樹的先序結(jié)果5、

遞歸過程如圖。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第39頁。

procedurefind(a,b:string);{a為中序串,b為后序串}vars,l:integer;beginL:=length(b);ifL=1thenwrite(b)elsebeginwrite(b[L]);{輸出根結(jié)點(diǎn)}s:=pos(b[L],a);{尋找根結(jié)點(diǎn)在中序排列中的位置}ifs-1>0thenfind(copy(a,1,s-1),copy(b,1,s-1));{處理左子樹}ifL-s>0thenfind(copy(a,s+1,L-s),copy(b,s,L-s));{處理右子樹}end;end;

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第40頁。問題2、后綴表達(dá)式

所謂后綴表達(dá)式，是我們通常用的中綴表達(dá)式的另一種形式。中綴表達(dá)式的運(yùn)算符的位置是在它所要計(jì)算的兩個表達(dá)式之間的，而后綴表達(dá)式則是在其后面。比如有一個中綴表達(dá)式如下：

(<表達(dá)式1>)<運(yùn)算符>(<表達(dá)式2>)

要將其轉(zhuǎn)成后綴表達(dá)式，則要先遞歸地將<表達(dá)式1>和<表達(dá)式2>轉(zhuǎn)成后綴表達(dá)式，然后將其變成

<表達(dá)式1><表達(dá)式2><運(yùn)算符>

我們一般不習(xí)慣這樣的表示方式，但好在我們可以用棧輕松處理掉它。具體方法是：從左到右掃描整個表達(dá)式，當(dāng)我們掃描到數(shù)時，將其加入棧中，當(dāng)我們掃描到運(yùn)算符時，取出兩個棧頂元素，計(jì)算出結(jié)果后重新加入棧中。這樣最終棧中只會剩下一個元素，該元素就是整個表達(dá)式的計(jì)算結(jié)果。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第41頁。

現(xiàn)在假設(shè)我們有的不是棧而是隊(duì)列，我們也希望能用相同的操作方式處理一個表達(dá)式。唯一不同的是，隊(duì)列每次加入元素是在隊(duì)尾，而取出元素是在隊(duì)頭，所以就不適用在原先的后綴表達(dá)式上了。我們需要找到另一種表達(dá)式使得其適合于隊(duì)列用相同的方法處理并得出相同的結(jié)果。InputFormat

輸入文件第一行包含一個整數(shù)N，表示總共有N個后綴表達(dá)式需要處理。以下N行每行有一個后綴表達(dá)式，其中數(shù)用小寫字母表示，運(yùn)算符用大寫字母表示。OutputFormat

輸出文件共有N行，對于每個后綴表達(dá)式，輸出適合于隊(duì)列的另一種形式。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第42頁。SampleInput1xyPwzIMSampleOutputzwyxIPMDataLimit對于50%的數(shù)據(jù)，所有后綴表達(dá)式的長度不超過1000；對于100%的數(shù)據(jù)，有1≤N≤20，所有后綴表達(dá)式的長度不超過10000。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第43頁。分析：右圖表達(dá)式樹的后輟表達(dá)式為abcd-*+ef/-后輟表達(dá)式的棧處理過程：（1）abcd入棧，遇-，棧頂cd出棧運(yùn)算后入棧；(2)abc-d，遇*，b*(c-d)入棧；(3)ab*(c-d)，遇+，a+b*(c-d)入棧；ef入棧；(4)a+b*(c-d)ef，遇/，e/f入棧；(5)a+b*(c-d)e/f，遇-，a+b*(c-d)-e/f題意簡述：將適用于棧的普通后綴表達(dá)式，轉(zhuǎn)化為適用于隊(duì)列的符號置后的表達(dá)式。-+/a*efbc-d數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第44頁。如何寫成隊(duì)的處理的后輟表達(dá)式呢？隊(duì)：先進(jìn)先出對表達(dá)式a+b*(c-d)-e/f(1）cd遇-形成c-d后入隊(duì)能夠繼續(xù)下面的運(yùn)算隊(duì)后輟為cdb-bc-d遇*形成b*(c-d)后入隊(duì)能夠繼續(xù)下面的運(yùn)算隊(duì)后輟為cdb-a*efab*(c-d)ef,遇+形成a+b*(c-d)后入隊(duì)能夠繼續(xù)下面的運(yùn)算隊(duì)后輟為cdb-a*ef/efa+b*(c-d),遇/形成e/f后入隊(duì)能夠繼續(xù)下面的運(yùn)算隊(duì)后輟為cdb-a*ef/-a+b*(c-d)e/f,遇-形成a+b*(c-d)-e/f入隊(duì)得表達(dá)式值勤a+b*(c-d)-e/f故：符合隊(duì)運(yùn)算的后輟表示式為：cdb-a*ef+/-

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第45頁。算法：1、根據(jù)后輟表達(dá)式，轉(zhuǎn)化為表達(dá)式樹；2、從表達(dá)式樹的底層開始逐層向根結(jié)點(diǎn)按順序輸出結(jié)點(diǎn)值。程序?qū)崿F(xiàn)：Expression.dpr

觀察隊(duì)的處理過程與表達(dá)式樹關(guān)系，發(fā)現(xiàn)是最底層開始逐層向根結(jié)點(diǎn)按順序推進(jìn)，后輟表達(dá)式順序?yàn)楸磉_(dá)式樹的從下至上從左至右形式。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第46頁。3.4哈夫曼樹與哈夫曼編碼

哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度和。

哈夫曼編碼：根據(jù)哈夫曼樹進(jìn)行編碼。

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第47頁。ABCHIDEFG75249WPL(T)=7×

2+5×

2+2×

3+4×

3+9×

2=60樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和表示

WPL(T)=wklk(對所有葉子結(jié)點(diǎn))nk=1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第48頁。ABCHIDEFG74952WPL(T)=7×4+9×

4+5×

3+4×

2+2×

1=89

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第49頁。構(gòu)造哈夫曼樹1.根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個帶權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹為空樹;數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第50頁。2.在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和;3.從F中刪去這兩棵樹，同時將剛生成的新樹加入到F中;4.重復(fù)(2)和(3)兩步，直至F中只含一棵樹為止。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第51頁。練習(xí):已知權(quán)值W={5,6,2,7,8}75628767713852761)2)3)528數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第52頁。4)5)6713852715671328852715WPL=2×3+5×3+6×2+7×2+8×2=63次序數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第53頁。特點(diǎn)：1、有n個葉子結(jié)點(diǎn)2、沒有度為1的結(jié)點(diǎn)3、總的結(jié)點(diǎn)數(shù)為2n-14、形態(tài)不唯一數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第54頁。哈夫曼編碼

利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第55頁。A B C D E6 7 2 5 9例：假設(shè)有5個符號以及它們的頻率：求前綴編碼。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第56頁。95271667132901010011000110010111前綴編碼1、依據(jù)頻率建立哈夫曼樹2、對邊編號3、求出葉子結(jié)點(diǎn)的路徑4、得到字符編碼A B C D E6 7 2 5 900 01 100 101 11數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第57頁。3.4二叉堆

以最小堆為例：堆是一個序列{k1,k2,…,kn}，采用順序方式存儲這個序列它滿足下面的條件：

ki≤k2i并且ki≤k2i+1，當(dāng)i=1,2,…,n/2

將這個序列的每一個元素ki看成是一顆有n個結(jié)點(diǎn)的完全二叉樹的第i個結(jié)點(diǎn)，其中k1是該二叉樹的根結(jié)點(diǎn)。

二叉堆是一種特殊的堆，二叉堆是完全二元樹或者是近似完全二元樹。二叉堆滿足堆特性：父結(jié)點(diǎn)的鍵值總是大于或等于任何一個子節(jié)點(diǎn)的鍵值稱為最大堆，或父結(jié)點(diǎn)的鍵值總是小于或等于任何一個子節(jié)點(diǎn)的鍵值稱為最小堆。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第58頁。

堆的基本運(yùn)算：插入：要在堆中插入一個元素，只要將它放置在堆的末尾（即一個葉子節(jié)點(diǎn)下），調(diào)整堆。刪除根：把最后一個元素放到根位置，這樣就變成了把一個大元素向下放的過程。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第59頁。數(shù)據(jù)插入堆：procedureTHeap.Push(constKey:TData);var i:TIndex;begin Inc(Size); Data[Size]:=Key; i:=Size; whilei>1do begin ifCompare(Data[ishr1],Data[i])<=0thenBreak;//如果結(jié)點(diǎn)值大于父結(jié)點(diǎn)值，退出

Swap(Data[ishr1],Data[i]);//否則，交換結(jié)點(diǎn)值

i:=ishr1;//位置上移一層

end;end;數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第60頁。刪除堆結(jié)點(diǎn)：functionTHeap.Pop:TData;var i,j:TIndex;begin Swap(Data[1],Data[Size]);//根結(jié)點(diǎn)和尾結(jié)點(diǎn)交換

Result:=Data[Size];//獲取根結(jié)點(diǎn)值

Dec(Size);//刪除結(jié)點(diǎn)

i:=1;//根結(jié)點(diǎn)下沉

whileishl1<=Sizedo begin j:=ishl1; if(j<Size)and(Compare(Data[j+1],Data[j])<0)thenInc(j);//選擇左右兒子中小的位置

ifCompare(Data[i],Data[j])<=0thenBreak;//如果當(dāng)前結(jié)點(diǎn)已經(jīng)小等于兒子結(jié)點(diǎn)，結(jié)束

Swap(Data[i],Data[j]); i:=j; end;end;數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第61頁。程序中的比較函數(shù)和交換過程functionTHeap.Compare(constA,B:TData):TData;begin Result:=A-B;end;procedureTHeap.Swap(varA,B:TData);var T:TData;begin T:=A; A:=B; B:=T;end;數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第62頁。堆排序方法就是利用這一點(diǎn)來選擇最小元素。

一個序列和相應(yīng)的完全二叉樹：

這個序列不是一個堆。堆排序的關(guān)鍵問題是如何將待排序記錄的排序碼建成一個堆。

調(diào)整：使父節(jié)點(diǎn)小等于兒子。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第63頁。從圖可以看到，在n=9個元素組成的序列和它相對應(yīng)的完全二叉樹中，序號為9，8，7，6，5的結(jié)點(diǎn)沒有兒子，以它們?yōu)楦淖訕滹@然滿足堆的條件。因?yàn)樵谟衝=9個結(jié)點(diǎn)的完全二叉樹中，第4=n/2，3,2,1個結(jié)點(diǎn)都有兒子，一般情況下，以它們?yōu)楦Y(jié)點(diǎn)的子樹不會滿足堆的條件，所以，要使該序列變換成一個堆，必須從這些結(jié)點(diǎn)處進(jìn)行調(diào)整。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第64頁。

調(diào)整是從序號為4(=n/2),的結(jié)點(diǎn)開始，然后對序號為3，2，1的結(jié)點(diǎn)依次進(jìn)行。依次使以第4個結(jié)點(diǎn)為根的子樹變成堆，直到以第1個結(jié)點(diǎn)為根的整個完全二叉樹具有堆的性質(zhì)，則建堆完成。建堆過程如下圖所示數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第65頁。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第66頁。算法效率為：O(log(N))數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第67頁。堆的應(yīng)用問題1:合并果子(NOIP2004提高組)【問題描述】

在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個最小的體力耗費(fèi)值。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第68頁。

例如有3種果子，數(shù)目依次為1，2，9。可以先將1、2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15?？梢宰C明15為最小的體力耗費(fèi)值。【輸入格式】

輸入包括兩行，第一行是一個整數(shù)n(1<＝n<=10000)，表示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai(1<＝ai<=20000)是第i種果子的數(shù)目。【輸出格式】

輸出包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個值小于2^31。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第69頁?！据斎霕永?129【輸出樣例】15數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第70頁。分析：很明顯，這道題是一道貪心的題目，可以證明，每次取最小的兩堆合并會使得最后的體力值最小。那么，這道題的問題就在于怎么找最小的兩堆果子了。樸素方法：排序，合并，插入。

我們注意到，每次合并完果子會刪掉兩堆，并添加一堆新的，如果采用線性表，時間復(fù)雜度將高達(dá)O（N^2），對于N<=20000是不夠的。所以，我們考慮使用最小堆優(yōu)化。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第71頁。算法：建立空堆；讀入數(shù)據(jù)，建立最小堆；每次取兩個堆頂元素合并，并插入合并后的數(shù)，總共合并n-1次。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第72頁。方法2：隊(duì)列樸素方法問題是時間浪費(fèi)在每次的排序中，能否根據(jù)本題特點(diǎn)進(jìn)行改進(jìn)呢？構(gòu)造兩個隊(duì)列old和new，old用來存儲原有的果子堆數(shù)，new用來存儲每次合并得到的新果子堆數(shù)，每次合并后累加耗費(fèi)的體力即可。要想得到最小的體力耗費(fèi)值，則old要按增序排列，很明顯每次合并時候是在old和new的首部，取兩個最小值，合并之后插入到new尾部。此種方法的好處是只需對old進(jìn)行一次排序，之后就不再需要排序，而是直接在old和new的首部取值就好了。由于old的元素是從a[]中復(fù)制過來的，所以我們可以對其進(jìn)行插入排序，這樣排序的時間復(fù)雜度是O(N*logN)；但如果我們注意觀察的話，可以發(fā)現(xiàn)輸入數(shù)據(jù)1<＝ai<=20000，我們完全可以使用基數(shù)排序，以空間換時間，使得時間復(fù)雜度降低到O(N)。（fruit1.pas）數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第73頁。問題2：芒果(mango)【題目描述】

有n個牛頭人，他們很無聊，決定玩游戲。他們排成了一隊(duì)，然后順序來到一堆準(zhǔn)備好的芒果前面，首先從中取出Ai個，然后將剩下的芒果恰好平均分成Bi堆，從中取出一堆，剩余合并成一堆給后來人??；如果當(dāng)前已經(jīng)沒有芒果了，牛頭人會當(dāng)他已經(jīng)取過了。當(dāng)n個牛頭人都取一次之后，他們驚奇地發(fā)現(xiàn)芒果恰好被分光啦。因?yàn)槟撤N關(guān)系，對于每只牛頭人都有m種決策，他會隨機(jī)從中取出一種可行的決策?，F(xiàn)在他們想知道一開始的時候可能有多少芒果，于是他們找到了你，你能告訴他們嗎？這個數(shù)字可能很大，所以你只需要告訴他們第k小的可能的芒果數(shù)。如果出現(xiàn)數(shù)芒果過程不同但答案相同，我們認(rèn)為它僅僅是一組解。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第74頁。【輸入格式】輸入數(shù)據(jù)的第一行包括3個正整數(shù)n,m,k，分別如題目中所描述。接下來有m行，每行有2個正整數(shù)，表示Ai和Bi。其中Bi一定大于1?！据敵龈袷健枯敵鲆粋€數(shù)表示第k小的芒果數(shù)。如果不存在則輸出“-1”?！緲永斎搿?241322【樣例輸出】 6【樣例說明】

前4小的可能芒果數(shù)是1，2，4，6?！緮?shù)據(jù)規(guī)模】

對于30%的數(shù)據(jù)，答案不超過10000； 對于100%的數(shù)據(jù)，n不超過100，m不超過10，A和B不超過100，k不超過10000。對于所有的n超過10的數(shù)據(jù)，Bi的值至少為5。數(shù)據(jù)保證答案一定在10^16之內(nèi)！數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第75頁。分析：由于最后的狀態(tài)比較明確為芒果取完，因此，從最后的狀態(tài)倒推到初始狀態(tài)比較容易解決問題。

1、設(shè)X表示取到第K個牛頭人的芒果數(shù)，Y表示取到第K+1個牛頭人的芒果數(shù)，按題意，順推得：y=((x-a[k])divb[k])*(b[k]-1),如果倒推，則X=(Y*B[K])DIV(B[K]-1)+a[k]；

2、按題意，最后狀態(tài)是芒果取完，則從0開始倒推選擇芒果數(shù)，每次枚舉所有可行的選擇，設(shè)F[X]表示倒推了多少層的芒果數(shù)為X值，則

F[J]+1當(dāng)F[X]=0，則由F[J]層推得

F[X]=min(F[X],F[J]+1)當(dāng)F[X]<>0，表示有多種方案，選最小的

3、從芒果值為0開始逐層倒推每層可行的芒果值，輸出第K小的可行的芒果值。讀mango.pas數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第76頁。

上述算法問題，答案值限制在1000000內(nèi)。方法2：因?yàn)槿绻芽談t可不取，該狀態(tài)等同于只有第一個人用了同樣的決策取并將堆取空的狀態(tài)，這樣該狀態(tài)也就是答案之一，擴(kuò)展k次，枚舉所有答案，將答案Qsort一遍，輸出第k小值。這就是該題的樸素算法。

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第77頁。方法3：每次只要從已知答案中選出最小的且已擴(kuò)展次數(shù)最少的答案，若它還可以繼續(xù)擴(kuò)展就計(jì)算出新答案，這樣只要擴(kuò)展k次即可。這就需要動態(tài)對數(shù)據(jù)進(jìn)行維護(hù)，顯然使用堆，可以提高算法的效率。讀mango1.pas

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第78頁。3.5二叉查找樹

二叉查找樹（BinarySearchTree），或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

它的左、右子樹也分別為二叉查找樹。

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第79頁。圖例如，由關(guān)鍵字值序列（62,15,68,46,65,12,57,79,35）構(gòu)成的一棵二叉排序樹如圖所示。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第80頁。

如果對上述二叉排序樹進(jìn)行中根遍歷可以得到一個關(guān)鍵字有序序列（12,15,35,46,57,62,65,68,79），這是二叉排序樹的一個重要特征，也正是由此將其稱為“二叉排序樹”。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第81頁。二叉查找樹基本操作1、插入2、查找3、刪除數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第82頁。插入從根節(jié)點(diǎn)開始如果添加元素的關(guān)鍵字比當(dāng)前節(jié)點(diǎn)大就到右兒子，否則到左兒子重復(fù)，直到到達(dá)一個葉子節(jié)點(diǎn)這樣我們就找到了所要添加元素的父親節(jié)點(diǎn)，只要根據(jù)新節(jié)點(diǎn)與父親節(jié)點(diǎn)關(guān)鍵字的大小，插為父節(jié)點(diǎn)的左（右）兒子，這樣就完成了插入。二叉搜索樹的插入運(yùn)算(X.Key=43)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第83頁。二叉搜索樹的構(gòu)造過程

(a)空樹；(b)插入28；(c)插入21；(d)插入25；(e)插入36；(f)插入33；(g)插入43數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第84頁。查找從根節(jié)點(diǎn)開始，如果查找元素的關(guān)鍵字比當(dāng)前節(jié)點(diǎn)大就到右兒子，否則到左兒子重復(fù)，直到找到所需的節(jié)點(diǎn)。查找最小值從根節(jié)點(diǎn)開始不斷找該節(jié)點(diǎn)的左兒子，直到一個點(diǎn)沒有左兒子為止。該點(diǎn)即為樹中最小值。（查找最大值相反）數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第85頁。刪除分四種情況討論，確保從二叉樹中刪除一個結(jié)點(diǎn)后，不會影響二叉排序樹的性質(zhì)：（1）若要刪除的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，可以直接進(jìn)行刪除。（2）若要刪除結(jié)點(diǎn)有右子樹，但無左子樹，可用其右子樹的根結(jié)點(diǎn)取代要刪除結(jié)點(diǎn)的位置。（3）若要刪除結(jié)點(diǎn)有左子樹，但無右子樹，可用其左子樹的根結(jié)點(diǎn)取代要刪除結(jié)點(diǎn)的位置，與步驟⑵類似。（4）若要刪除結(jié)點(diǎn)的左右子樹均非空，則首先找到要刪除結(jié)點(diǎn)的右子樹中關(guān)鍵字值最小的結(jié)點(diǎn)（即子樹中最左結(jié)點(diǎn)），利用上面的方法將該結(jié)點(diǎn)從右子樹中刪除，并用它取代要刪除結(jié)點(diǎn)的位置，這樣處理的結(jié)果一定能夠保證刪除結(jié)點(diǎn)后二叉樹的性質(zhì)不變。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第86頁。查找樹的應(yīng)用問題：郁悶的出納員（Cashier）NOI2003？DescriptionOIER公司是一家大型專業(yè)化軟件公司，有著數(shù)以萬計(jì)的員工。作為一名出納員，我的任務(wù)之一便是統(tǒng)計(jì)每位員工的工資。這本來是一份不錯的工作，但是令人郁悶的是，我們的老板反復(fù)無常，經(jīng)常調(diào)整員工的工資。如果他心情好，就可能把每位員工的工資加上一個相同的量。反之，如果心情不好，就可能把他們的工資扣除一個相同的量。我真不知道除了調(diào)工資他還做什么其它事情。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第87頁。

工資的頻繁調(diào)整很讓員工反感，尤其是集體扣除工資的時候，一旦某位員工發(fā)現(xiàn)自己的工資已經(jīng)低于了合同規(guī)定的工資下界，他就會立刻氣憤地離開公司，并且再也不會回來了。每位員工的工資下界都是統(tǒng)一規(guī)定的。每當(dāng)一個人離開公司，我就要從電腦中把他的工資檔案刪去，同樣，每當(dāng)公司招聘了一位新員工，我就得為他新建一個工資檔案。老板經(jīng)常到我這邊來詢問工資情況，他并不問具體某位員工的工資情況，而是問現(xiàn)在工資第k多的員工拿多少工資。每當(dāng)這時，我就不得不對數(shù)萬個員工進(jìn)行一次漫長的排序，然后告訴他答案。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第88頁。

好了，現(xiàn)在你已經(jīng)對我的工作了解不少了。正如你猜的那樣，我想請你編一個工資統(tǒng)計(jì)程序。怎么樣，不是很困難吧？InputFormat

第一行有兩個非負(fù)整數(shù)n和min。n表示下面有多少條命令，min表示工資下界。接下來的n行，每行表示一條命令。命令可以是以下四種之一：名稱格式作用I命令I(lǐng)_k新建一個工資檔案，初始工資為k。如果某員工的初始工資低于工資下界，他將立刻離開公司。A命令A(yù)_k把每位員工的工資加上kS命令S_k把每位員工的工資扣除kF命令F_k查詢第k多的工資

_（下劃線）表示一個空格，I命令、A命令、S命令中的k是一個非負(fù)整數(shù)，F(xiàn)命令中的k是一個正整數(shù)。在初始時，可以認(rèn)為公司里一個員工也沒有。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第89頁。OutputFormat

輸出文件的行數(shù)為F命令的條數(shù)加一。 對于每條F命令，你的程序要輸出一行，僅包含一個整數(shù)，為當(dāng)前工資第k多的員工所拿的工資數(shù)，如果k大于目前員工的數(shù)目，則輸出-1。 輸出文件的最后一行包含一個整數(shù)，為離開公司的員工的總數(shù)。SampleInput910I60I70S50F2I30S15A5F1F2數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第90頁。SampleOutput1020-12DataLimitI命令的條數(shù)不超過100000

A命令和S命令的總條數(shù)不超過100

F命令的條數(shù)不超過100000

每次工資調(diào)整的調(diào)整量不超過1000

新員工的工資不超過100000數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第91頁。分析：

顯而易見，這是一道模擬題，若單純用線性表進(jìn)行處理，易超時，所以自然聯(lián)想到此題的關(guān)鍵在于數(shù)據(jù)結(jié)構(gòu)的選擇和設(shè)計(jì)。二叉排序樹支持插入、查找、刪除操作。創(chuàng)建一棵帶權(quán)二叉排序樹，滿足對于每個節(jié)點(diǎn)，它的權(quán)值大于左子樹中任意節(jié)點(diǎn)的權(quán)值，且小于右子樹中任意節(jié)點(diǎn)的權(quán)值。本題需要解決以下幾個問題：

1、刪除：每次只要把最小值和工資下限比較，故每次刪除的是樹中的最小值，刪除操作比較簡單；

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)全文共101頁，當(dāng)前為第92頁。2、所有的數(shù)加上或減去一個數(shù):

假如每次對于A，S命令都給整棵樹重新賦值，顯然是不行的，因?yàn)闃涞墓?jié)點(diǎn)最多有1000000個且有200個A，S命令所以極易超時，所以我們不得不另辟蹊徑。這題的主要問題在于不斷有數(shù)據(jù)被插入，假如一開始給定的數(shù)是固定的，且不會有數(shù)插入，那么我們就可很容易地想出一種解決同加同減的辦法。設(shè)變量sum記錄加減的變化，不論加還是減，都在