中國著名特級教師教學思想錄7.ppt

1、樹和圖,西安交通大學計教中心 ,樹的遞歸定義,樹是由n個具有相同特性的數據元素組成的集合。若n=0，則稱其為空樹。一棵非空樹T必須滿足：1）其中有一個特定的元素稱為T的根root。 2）除根以外的集合可被劃分為m個不相交的子集T1，T2，Tm，其中每個子集都是樹。它們稱為根root的子樹,與樹相關的術語,結點：在樹結構中一般把數據元素及其若干指向子樹的分支稱為結點。 結點的度：結點擁有的非空子樹的個數。 樹的度：樹中所有結點的度的最大值。 葉子結點：沒有非空子樹的結點。 分支結點：至少有一個非空子樹的結點。 孩子結點和父結點：某結點所有子樹的根結點都稱為該結點的孩子結點，同時該結點也稱為其孩子

2、結點的父結點,兄弟結點：具有相同父結點的結點互為兄弟結點。 結點的層次：根結點的層次為1,其子結點的層次為2。依次類推，子結點的層次總比父結點多一層。 樹的深度：樹中結點所在的最大層次。 有序樹和無序樹：將樹中各結點的子樹看成自左向右有序的，則稱該樹為有序樹。否則稱為無序樹。 森林：由零棵或有限棵互不相交的樹組成的集合,二叉樹的定義,二叉樹可以是空樹，當二叉樹非空時，其中有一個根元素，余下的元素組成兩個互不相交二叉樹，分別稱為根的左子樹和右子樹。二叉樹是有序樹，也就是說任意結點的左、右子樹不可交換。而一般樹的子樹間是無序的,特殊形式的二叉樹,滿二叉樹：當二叉樹每個分支結點的度都是2，且所有葉子

3、結點都在同一層上，則稱其為滿二叉樹。完全二叉樹：從滿二叉樹葉子所在的層次中，自右向左連續(xù)刪除若干葉子所得到的二叉樹被稱為完全二叉樹。滿二叉樹可看作是完全二叉樹的一個特例,二叉樹有下列重要性質,1）在二叉樹的第k層上至多有2k-1個結點(k1) 證明：當k=1時，命題顯然成立。假定k=n-1時命題成立，則第n層（k=n）的結點數最多是第n-1層的2倍，所以第n層最多有2*2n-2=2n-1個結點。命題成立。 （2）深度為h的二叉樹上至多含2h-1個結點(h1) 證明：根據性質1容易知道深度為h的二叉樹最多有20+21+2h-1個結點，即最多有2h-1個結點,3）包含n(n0)個結點的二叉樹總的分

4、支數為n-1 證明：二叉樹中除了根結點之外每個元素有且只有一個父結點。在所有子結點與父結點間有且只有一個分支，即除根外每個結點對應一個分支，因此二叉樹總的分支數為n-1,4）任何一棵二叉樹，若含有n0個葉子結點、n2個度為2的結點，則必存在關系式n0=n2+1 證明：設二叉樹含有n1個度為1的結點，則二叉樹結點總數顯然為： n0 + n1 + n2（2-2） 再看看樹的分支數，n2個度為2的結點必然有2n2個分支，n1個度為1的結點必然有n1個分支。又因為除根結點外，其余每個結點都有一個分支進入。因此二叉樹的分支數加1就是結點總數。即結點總數為： 1 + n1 + 2n2（2-3） 由（2-2

5、）（2-3）兩式可知：n0=n2+1,5）具有n個結點的完全二叉樹的深度為log2(n)+1 證明：假設二叉樹的深度為h，則必有2h-1-1n2h-1，于是有2h-1n+12h，也就是 2h-1n2h，從而得到h-1log2(n)h，于是h=log2(n)+1,6） 若對含n個結點的完全二叉樹從上到下、從左至右進行1至n的編號，則對二叉樹中任意一個編號為i的結點： 若i=1，則該結點是二叉樹的根，無父結點。否則，編號為i/2的結點為其父結點； 若2in，則該結點無左孩子。否則，編號為2i的結點為其左孩子結點； 若2i+1n，則該結點無右孩子。否則，編號為2i+1的結點為其右孩子結點。 證明通過

6、對i進行歸納即可得證,二叉樹的鏈式存儲,結點定義： struct BinTreeNode ElemType data; struct BinTreeNode *leftChild, *rightChild; ; 這里leftChild和rightChild分別為某一結點指向其左孩子和右孩子的指針。對于葉子結點或一個新生成的結點而言，其左孩子和右孩子指針都應為空值,利用這種結點形式存儲的樹一般稱為二叉鏈表。 從根結點出發(fā)，可以訪問二叉樹的任何結點。為了能夠訪問二叉樹，必須保留指向根結點的指針。這和單鏈表必須保留頭指針的道理一樣,二叉樹的常用算法包括：獲取根結點指針、判斷樹是否為空、插入或刪除結點

7、、插入或刪除子樹、二叉樹遍歷等。 二叉樹類可描述如下： class BinTree public: BinTreeNode *root;/定義根結點指針 BinTree() root=NULL; /構造函數，定義空樹 /判斷樹是否為空 bool IsEmpty() return root=NULL; /在葉子結點p下插入左子樹q void Ins_lchild(BinTreeNode *p,BinTreeNode *q) p-leftChild=q; ( 接下頁,接上頁 ) /在葉子結點p下插入右子樹q void Ins_rchild(BinTreeNode *p,BinTreeNode *q

8、) p-rightChild=q; /刪除結點p的左子樹 void Del_lchild(BinTreeNode *p) p-leftChild=NULL; /刪除結點p的右子樹 void Del_rchild(BinTreeNode *p) p-rightChild=NULL; void PreOrder(BinTreeNode *t);/先序遍歷 void InOrder(BinTreeNode *t);/中序遍歷 void PostOrder(BinTreeNode *t);/后序遍歷,二叉樹的遍歷,二叉樹遍歷是只按照某種順序訪問二叉樹的每個結點，并且每個結點只被訪問一次。這是二叉樹中經

9、常用到的操作，有三種主要的遍歷算法先序遍歷、中序遍歷和后序遍歷,1）先序遍歷 對一顆非空二叉樹進行先序遍歷時，首先訪問根結點，然后按先序遍歷方式訪問左子樹，最后按先序遍歷方式訪問右子樹。先序遍歷算法如下： void BinTree:PreOrder(BinTreeNode *t) if (t) Visit( t ); /訪問根結點 PreOrder( t-leftChild ); /遍歷左子樹 PreOrder( t-rightChild ); /遍歷右子樹,2）中序遍歷 對一顆非空二叉樹進行中序遍歷時，首先按中序遍歷方式訪問左子樹，然后訪問根結點，最后按中序遍歷方式訪問右子樹。中序遍歷算法如

10、下： void BinTree:InOrder(BinTreeNode *t) if(t) InOrder( t-leftChild );/ 遍歷左子樹 Visit( t ); / 訪問根節(jié)點 InOrder( t-rightChild ); / 遍歷右子樹,3）后序遍歷 對一顆非空二叉樹進行中序遍歷時，首先按后序遍歷方式訪問左子樹，然后按后序遍歷方式訪問右子樹，最后訪問根結點。后序遍歷算法如下： void BinTree:PostOrder(BinTreeNode *t) if(t) PostOrder( t-leftChild ); /遍歷左子樹 PostOrder( t-rightChi

11、ld ); /遍歷右子樹 Visit( t ); /訪問根節(jié)點,圖的基本概念,圖的來源：通信網、交通網等，它表現了數據對象間多對多的聯系。在該結構中，數據元素一般稱為頂點。 圖的定義： 圖是由頂點集合及頂點間的關系集合組成的一種數據結構。一般記作Graph( V, E )。其中V是頂點的有限非空集合；E是頂點之間關系的有限集合,以下是圖的相關術語 邊：若頂點x到y(tǒng)是的一條雙向通路，則稱為邊，用(x，y)表示。 ?。喝繇旤cx到y(tǒng)是的一條單向通路，則稱為弧，用表示。 鄰接點：如果(x,y)是圖中的一條邊，則稱x與y互為鄰接點；如果是圖中的一條弧，則稱y為x的鄰接點。 頂點的度：一個頂點v的度是與它

12、相關聯的邊的條數,無向圖：若圖是由一些頂點和邊構成則稱之為無向圖。 有向圖：若圖是由一些頂點和弧構成則稱之為有向圖。 權：某些圖的邊或弧具有與它相關的數，稱之為權。這種帶權圖叫做網絡,路徑：在圖中，若從頂點vi出發(fā)，沿一些邊或弧，經過頂點vp1，vp2，vpm，到達頂點vj。則稱頂點序列( vi，vp1，vp2，vpm，vj )為從頂點vi到頂點vj的路徑。若路徑上各頂點均不互相重復，則稱這樣的路徑為簡單路徑。 路徑長度：非帶權圖的路徑長度是指此路徑上邊或弧的條數，帶權圖的路徑長度是指路徑上各邊或弧的權之和,子圖：設有兩個圖G(V，E)和G(V，E)。若V包含V且E包含E，則稱圖G是圖G的子圖

13、。 連通圖：在無向圖中，若從頂點vi到頂點vj有路徑，則稱頂點vi與vj是連通的。如果圖中任意一對頂點都是連通的，則稱此圖是連通圖。 強連通圖：在有向圖中，若對于每一對頂點vi和vj，都存在從vi到vj和從vj到vi的路徑，則稱此圖是強連通圖,生成樹：一個連通圖的生成樹是它的極小連通子圖。即包含了所有頂點以及最少的邊或弧的子圖，并且這些邊或弧使得任意兩頂點相互連通。在含有n個頂點的無向圖中，生成樹一定有n-1條邊，且生成樹的形式可能有多個,圖的存儲方式,1鄰接矩陣 利用數組實現的。它利用一維數組存儲頂點信息，利用二維數組存儲頂點間邊或弧的信息。此二維數組又稱鄰接矩陣。 鄰接矩陣 存儲方式可用于

14、無向圖或有向圖。無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的,圖的鄰接矩陣存儲可以用下面的結構體表示： #define MAX_NUM 100 / 最大頂點個數 typedef struct VertexType vexsMAX_NUM; /頂點信息數組 ArcType MatrixMAX_NUMMAX_NUM; /鄰接矩陣 int vexnum,arcnum; /圖的實際頂點數和弧(邊)數 int kind; /圖的種類標志, 1有向圖, /2有向網,3無向圖,4無向網 MGraph; 其中ArcType是頂點關系的數據類型。VertexType是頂點的數據類型。MAX_NUM表

15、示最多可存的頂點數,假設無向圖G=(V,E)是一個有n個頂點的圖，則圖的鄰接矩陣A是n階方陣，其內容如下,其中W(i, j)是與邊或弧相關的權,對于含權的網絡而言，其鄰接矩陣可定義如下,a)無向圖鄰接矩陣 (b)有向圖鄰接矩陣 (c)網絡鄰接矩陣,2鄰接表 鄰接表存儲形式是一種鏈表與數組結合的存儲形式。在鄰接表中有兩種結點，一種是頭結點，另一種是表結點。 （1）頭結點都存儲一個頂點的詳細信息，為了便于管理，所有頭結點都存放在一個數組中。 （2）對于某個頂點而言，需要將所有與它鄰接的頂點存儲為表結點形式，并將它們鏈接成單鏈表，這個單鏈表就稱為該頂點的鄰接表。 （3）還要在每個頂點的頭結點中存儲指

16、向其鄰接表首元結點的指針,鄰接表的結點結構,c)網絡的表結點,a)頭結點,b)無權圖的表結點,圖的鄰接表描述,define MAX_NUM 100/頂點最大允許數量 struct AdjNode /表結點類型定義 int adjvex; /該鄰接點在數組中的位置 InfoType info;/該弧相關信息 struct AdjNode *next; /指向下一鄰接點的指針 ; typedef struct VNode /頭結點類型定義 VertexType data; /頂點信息 AdjNode *first; /指向鄰接表第一個結點 AdjListMAX_NUM,typedef struct

17、 AdjList headArray; /頭結點數組 int vexnum, arcnum; /圖的當前頂點數和弧數 int kind; /圖的種類標志 ALGraph; 其中AdjNode為表結點，InfoType為與邊相關信息的數據類型（可以包括權等）。VNode為頭結點，VertexType是頂點的數據類型，MAX_NUM表示最多可以存放的頂點個數,圖的遍歷方法,1深度優(yōu)先搜索 假定從圖中某個頂點v 出發(fā)進行遍歷，則首先訪問此頂點，然后依次從v的各個未被訪問的鄰接點出發(fā)，執(zhí)行深度優(yōu)先搜索遍歷，直至圖中所有和v有路徑相通的頂點都被訪問到，若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問

18、的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止,用非遞歸的方式描述如下：首先訪問圖中某一起始頂點v0，由v0出發(fā)，訪問它的任一鄰接點vi；再從vi出發(fā)，訪問與vi鄰接但還沒有訪問過的頂點vj；如此進行下去，直至到達某一頂點vt后，發(fā)現vt所有的鄰接頂點都被訪問過。于是從vt退到前一次剛訪問過的頂點vs，看看vs是否還有其他沒有被訪問的鄰接頂點。如果有則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止,bool visitedMAX; /頂點訪問標志數組 /從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G的

19、 /某個連通子圖 void DFS(ALGraph G, int v) AdjNode *p; visitedv = TRUE; coutnext ) if(!visitedp-adjvex) DFS(G,p-adjvex);,2廣度優(yōu)先搜索 假定從圖中某個頂點v 出發(fā)進行遍歷，則首先訪問此頂點，再依次訪問v的所有未被訪問過的鄰接點，然后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和v有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止,以圖(a)為例，假設從A出發(fā)進行廣度優(yōu)先搜索，首先訪問

20、A，然后依次訪問A的各個未被訪問過的鄰接頂點B、E、D,再分別從B、E、D出發(fā)，訪問它們的所有還未被訪問過的鄰接頂點C、F、G,為了實現逐層訪問，廣度優(yōu)先搜索算法中使用了一個隊列，以記憶正在訪問的這一層和上一層的頂點，以便于向下一層訪問,A B E D C F G,哈夫曼樹和哈夫曼編碼,設計二進制編碼方案時要考慮不同字符的使用頻率，使用頻率高的字符編碼應當盡量短一些。但是僅僅考慮使用頻率也是不夠的。 例如：某個文件由A、B、C、D四個字符組成，其中A用得最多，C次之。 方案1: A 1 C 0 B 10 D 11 那么象1100這樣的二進制數據具有二義性，既代表AACC，又可代表ABC，還可代

21、表DCC。 為了不使二進制編碼具有二義性，每個字符編碼都不能與其他字符編碼的前面若干位重合,a)有二義性的編碼系統(tǒng)對應的二叉樹 (b)無二義性的編碼系統(tǒng)對應的二叉樹,任何一個無二義性的二進制字符編碼系統(tǒng)必然與這樣一顆二叉樹對應，該二叉樹的葉子結點對應著所有需要轉換的字符，并且按照左分支代表0、右分支代表1的規(guī)則，從根到該葉子的分支對應的0、1序列就構成葉子對應字符的二進制編碼,可以利用二叉樹分析字符編碼問題。假設二叉樹中的左分支代表0，右分支代表1，則不論字符是采用何種0、1組合形式構成的編碼，它必然對應某個二叉樹中一個結點,1）假設每個字符使用頻率是相等的，那么不同字符的編碼長度之和就可衡量

22、編碼系統(tǒng)的優(yōu)劣。而某個字符編碼的長度就是對應的二叉樹中根到某個葉子的分支的數目（又稱為根到葉子的路徑長度）。 2）如果每個字符使用頻率不相等，那么將不同字符的編碼長度乘上其使用權值再加起來，也可衡量編碼系統(tǒng)的優(yōu)劣。也就是用根到每個葉子的路徑長度乘以葉子對應字符的使用權值再加起來作為衡量標準，顯然這種加權和除以字符總數就是每個字符的加權平均編碼長度,二叉樹帶權路徑長度：設二叉樹有n個帶有權值的葉子結點，每個葉子到根的路徑長度乘以其權值之和稱為二叉樹帶權路徑長度。一般記作： 其中，wi為第i個葉子的權重，li為第i個葉子到根的路徑長度。 哈夫曼樹：以一些帶有固定權值的結點作為葉子所構造的，具有最小帶權路徑長度的二叉樹稱為哈夫曼樹,假定有n個具有權值的結點，則哈夫曼樹的構造算法如下： 根據給定的n個權值w1, w2, , wn，構造n棵二叉樹的集合F=T1, T2, , Tn，其中每棵二叉樹中均只含一個帶權值為wi的根結點，其左、右子樹為空樹； 在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹