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

ACM/ICPC程序設(shè)計(jì)基本數(shù)據(jù)結(jié)構(gòu)及其在程序設(shè)計(jì)中的應(yīng)用張淑平非線性結(jié)構(gòu)樹、二叉樹圖非線性結(jié)構(gòu)樹、二叉樹圖樹樹是n個結(jié)點(diǎn)的有限集合(可以是空集)，在任一棵非空樹中：

（1）有且僅有一個稱為根的結(jié)點(diǎn)。

（2）其余結(jié)點(diǎn)可分為互不相交的子集，而且這些子集本身又是一棵樹，稱為根的子樹。JIACBDHGFEKLM從邏輯結(jié)構(gòu)看：

1）樹中只有樹根沒有父結(jié)點(diǎn)；

2）除根外，其余結(jié)點(diǎn)都有且僅一個父結(jié)點(diǎn)；3）樹中的結(jié)點(diǎn)，可以有零個或多個孩子結(jié)點(diǎn)；4)沒有孩子的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，或終端結(jié)點(diǎn)；5）除根外的其他結(jié)點(diǎn)，都存在唯一一條從根到該結(jié)點(diǎn)的路徑；JIACBDHGFEKLM樹樹的結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向子樹的分支；孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；父結(jié)點(diǎn)：B是A的孩子，則A是B的父親；兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)；堂兄結(jié)點(diǎn)：同一層上的結(jié)點(diǎn)；祖先結(jié)點(diǎn):

從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn)；子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫；結(jié)點(diǎn)的度：結(jié)點(diǎn)的子樹數(shù)目；...JIACBDHGFEKLM樹的基本術(shù)語二叉樹的定義：二叉樹要么為空，要么由根結(jié)點(diǎn)、左子樹和右子樹組成。左、右子樹本身也是二叉樹。注意：二叉樹的子樹有嚴(yán)格的左右之分，而樹沒有。二叉樹的定義二叉樹的定義ACBFEDG二叉樹的存儲順序存儲鏈表存儲二叉樹的順序存儲二叉樹的順序存儲指的是用元素在數(shù)組中的下標(biāo)表示一個結(jié)點(diǎn)與其孩子和父結(jié)點(diǎn)的關(guān)系.EGFCDABABCDEFG12345678910111213141516二叉樹的鏈表存儲二叉樹的二叉鏈表存儲(每個節(jié)點(diǎn)有兩個指針域)，分別指示出結(jié)點(diǎn)的左子樹和右子樹EGFCDABA∧B∧CE∧D∧∧F∧∧G∧rootLchilddataRchildtypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;二叉樹的鏈?zhǔn)酱鎯θ骀湵泶鎯?每個節(jié)點(diǎn)有三個指針域，分別指示出左子樹、右子樹和父結(jié)點(diǎn))EGFCDABA∧∧BCE∧D∧FG∧root∧∧∧∧LchilddataRchildParent樹的存儲樹的孩子兄弟表示法用二叉鏈表作為樹的存貯結(jié)構(gòu)。鏈表的兩個指針域分別指向該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)和其右邊的下一個兄弟結(jié)點(diǎn)IACBHGFEDA∧BF∧∧D∧C∧E∧G∧H∧I∧∧root樹的存儲樹的孩子兄弟表示法用二叉鏈表作為樹的存貯結(jié)構(gòu)。鏈表的兩個指針域分別指向該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)和其右邊的下一個兄弟結(jié)點(diǎn)ACBD

A

B

C

D=>I

I

J

K

L=>JKL借助于“孩子兄弟表示法”可將樹轉(zhuǎn)化成二叉樹二叉樹的運(yùn)算和應(yīng)用二叉樹的遍歷運(yùn)算先序、中序、后序、層序遍歷哈夫曼樹二叉樹的結(jié)構(gòu)特點(diǎn)任何一個非空的二叉樹都由三部分構(gòu)成DLR二叉樹的遍歷運(yùn)算遍歷運(yùn)算是有關(guān)二叉樹的主要運(yùn)算，遍歷方式有先序遍歷(DLR)、中序遍歷(LDR)、后序遍歷(LRD)層序遍歷DLR先序遍歷DLR：訪問根結(jié)點(diǎn)、先序遍歷左子樹、先序遍歷右子樹EGFCDAB先序遍歷序列:ABCDEFGDLR若二叉樹非空（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹；若二叉樹為空，結(jié)束——基本項(xiàng)（也叫終止項(xiàng)）若二叉樹非空——遞歸項(xiàng)（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹；

voidpreorder(BiTNode*root){//先序遍歷root指向根的二叉樹

if(root!=NULL)

{cout<<root->data；//訪問根結(jié)點(diǎn)

preorder(root->Lchild);

//先序遍歷根的左子樹

preorder(root->Rchild);//先序遍歷根的右子樹

}//if}//preorder中序遍歷LDR：中序遍歷左子樹、訪問根結(jié)點(diǎn)、中序遍歷右子樹EGFCDAB中序遍歷序列:BADCFEGDLR若二叉樹非空（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹；

voidinorder(BiTNode*root){//中序遍歷root指向根的二叉樹

if(root!=NULL)

{

inorder(root->Lchild);

//中序遍歷根的左子樹cout<<root->data；//訪問根結(jié)點(diǎn)

inorder(root->Rchild);//中序遍歷根的右子樹

}//if}//inorder后序遍歷LRD：后序遍歷左子樹、后序遍歷右子樹、訪問根結(jié)點(diǎn)EGFCDAB后序遍歷序列:BDFGECADLR若二叉樹非空（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)；

voidpostorder(BiTNode*root){//后序遍歷root指向根的二叉樹

if(root!=NULL)

{postorder(root->Lchild);

//后序遍歷根的左子樹

postorder(root->Rchild);//后序遍歷根的右子樹cout<<root->data；//訪問根結(jié)點(diǎn)

}//if}//postorder層序遍歷LRD：先根，后子樹；先左子樹，后右子樹DLREGFCDAB層序遍歷序列:ABCDEFG例1：TreeRecovery已知二叉樹的先序遍歷序列和中序遍歷序列，輸出它的后序遍歷序列．如圖輸入：DBAFCEGFABCDEG輸出：FACBGEDDBAFCEG例1：TreeRecovery先序遍歷序列特點(diǎn)：根左子樹先序序列右子樹先序序列根左子樹中序序列右子樹中序序列中序遍歷序列特點(diǎn)：例1：TreeRecoveryDBAFCEG

先序(DLR)中序(LDR)根據(jù)先序確定樹根，根據(jù)中序劃分左、右子樹FABCDEGDFABCEGBAFCEG分析輸出后序序列，必先輸出左子樹的后序序列，再輸出右子樹的后序序列，最后再輸出根。可用遞歸過程實(shí)現(xiàn)postorder(){

if(){postorder()；//輸出左子樹的后序遍歷序列

postorder()；//輸出右子樹的后序遍歷序列

輸出根；}}postorder(先序序列，中序序列){

if(序列不空){postorder(左子樹先序序列，左子樹中序序列)；

postorder(右子樹先序序列，右子樹中序序列)；輸出根；}}//postorder例2：TreesontheLevelTreesarefundamentalinmanybranchesofcomputerscience.Currentstate-of-theartparallelcomputerssuchasThinkingMachines'CM-5arebasedonfattrees.Quad-andoctal-treesarefundamentaltomanyalgorithmsincomputergraphics.Thisprobleminvolvesbuildingandtraversingbinarytrees....sampleinput:(11,LL)(7,LLL)(8,R)

(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()(3,L)(4,R)()sampleoutput:54811134721

notcomplete例2：TreesontheLevel(11,LL)(7,LLL)(8,R)

(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()(3,L)(4,R)()sampleinput:case1case254811134721例2：TreesontheLevel(11,LL)(7,LLL)(8,R)

(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()∧11∧LLhead7∧LLL54811134721例2：TreesontheLevel(11,LL)(7,LLL)(8,R)

(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()11LLhead7∧LLL8R54811134721例2：TreesontheLevel(11,LL)(7,LLL)(8,R)

(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()45L8R11LL13RL4RR7LLL2LLR1∧RRRhead54811134721例3：Isitatree?Atreeisawell-knowndatastructurethatiseitherempty(null,void,nothing)orisasetofoneormorenodesconnectedbydirectededgesbetweennodessatisfyingthefollowingproperties.Thereisexactlyonenode,calledtheroot,towhichnodirectededgespoint.//入度為0Everynodeexcepttheroothasexactlyoneedgepointingtoit.//除根之外結(jié)點(diǎn)的入度為1Thereisauniquesequenceofdirectededgesfromtheroottoeachnode.//根到每個結(jié)點(diǎn)有唯一路徑例3：Isitatree?7345681928345623412189375264(a)(b)(c)哈夫曼樹(最優(yōu)二叉樹)結(jié)點(diǎn)的帶權(quán)路徑長度從根到該結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)權(quán)的乘積稱為結(jié)點(diǎn)的帶權(quán)路徑長度樹的帶權(quán)路徑長度樹中所有葉子的帶權(quán)路徑長度之和稱為樹的帶權(quán)路徑長度記作哈夫曼樹(最優(yōu)二叉樹)設(shè)有四個葉子a、b、c和d的二叉樹中，對應(yīng)的權(quán)值分別為7、5、2和4，計(jì)算WPL。abcd752475dcab4275dabc24WPL=36WPL=46WPL=35最優(yōu)二叉樹哈夫曼算法根據(jù)給定的n個權(quán)值{w1,w2,...,wn}構(gòu)造n棵二叉樹的集合F={T1,T2,...,Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。重復(fù)2)和3)，直到F中只含一棵樹為止。這棵樹便是最優(yōu)二叉樹。Example實(shí)例合并果子(fruit.pas/dpr/c/cpp)【問題描述】

在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個最小的體力耗費(fèi)值。實(shí)例（續(xù)）合并果子(fruit.pas/dpr/c/cpp)【問題描述】

例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?、2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15。可以證明15為最小的體力耗費(fèi)值。實(shí)例（續(xù)）合并果子(fruit.p