數據結構課件

ACM/ICPC程序設計基本數據結構及其在程序設計中的應用張淑平非線性結構樹、二叉樹圖非線性結構樹、二叉樹圖樹樹是n個結點的有限集合(可以是空集)，在任一棵非空樹中：

（1）有且僅有一個稱為根的結點。

（2）其余結點可分為互不相交的子集，而且這些子集本身又是一棵樹，稱為根的子樹。JIACBDHGFEKLM從邏輯結構看：

1）樹中只有樹根沒有父結點；

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

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

A

B

C

D=>I

I

J

K

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

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

if(root!=NULL)

{cout<<root->data；//訪問根結點

preorder(root->Lchild);

//先序遍歷根的左子樹

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

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

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

if(root!=NULL)

{

inorder(root->Lchild);

//中序遍歷根的左子樹cout<<root->data；//訪問根結點

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

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

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

if(root!=NULL)

{postorder(root->Lchild);

//后序遍歷根的左子樹

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

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

先序(DLR)中序(LDR)根據先序確定樹根，根據中序劃分左、右子樹FABCDEGDFABCEGBAFCEG分析輸出后序序列，必先輸出左子樹的后序序列，再輸出右子樹的后序序列，最后再輸出根。可用遞歸過程實現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.//除根之外結點的入度為1Thereisauniquesequenceofdirectededgesfromtheroottoeachnode.//根到每個結點有唯一路徑例3：Isitatree?7345681928345623412189375264(a)(b)(c)哈夫曼樹(最優(yōu)二叉樹)結點的帶權路徑長度從根到該結點的路徑長度與該結點權的乘積稱為結點的帶權路徑長度樹的帶權路徑長度樹中所有葉子的帶權路徑長度之和稱為樹的帶權路徑長度記作哈夫曼樹(最優(yōu)二叉樹)設有四個葉子a、b、c和d的二叉樹中，對應的權值分別為7、5、2和4，計算WPL。abcd752475dcab4275dabc24WPL=36WPL=46WPL=35最優(yōu)二叉樹哈夫曼算法根據給定的n個權值{w1,w2,...,wn}構造n棵二叉樹的集合F={T1,T2,...,Tn}，其中每棵二叉樹Ti中只有一個帶權為wi的根結點，其左右子樹均空。在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。重復2)和3)，直到F中只含一棵樹為止。這棵樹便是最優(yōu)二叉樹。Example實例合并果子(fruit.pas/dpr/c/cpp)【問題描述】

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

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