最新第一章-基本概念教学讲义ppt.ppt

《最新第一章-基本概念教学讲义ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章-基本概念目錄5.1樹的概念5.2樹的表示法5.3二元樹5.4二元樹表示法5.5二元樹的走訪5.6二元樹的複製與相等測試5.7引線二元樹5.8堆積5.9二元搜尋樹5.10樹林5.1樹的概念樹(tree)是一種重要的離散結構(discretestructure)，它提供一種「具有層次關係」的概念來結構資料。樹為節點組成的有限集合，其中(1)存在一特殊節點R稱為樹根(root)；(2)其它節點可分割成n個無交集的集合。T1,T2,…,Tn，n0，而T1、T2、…Tn本身皆為樹，稱其為R的子樹(subtree)。5.2.1　

2、一般化的串列表示法上圖的樹可表示成下面的一般化串列：(A,(B,(E,K),(F,L,M),G),(C,H),(D,(I,N),(J,O,P)))若將節點A的三兒子B、C、D所形成的3個子樹，分別取名為T1、T2、T3，則此樹可簡化成(A,T1,T2,T3)其中T1=(B,(E,K),(F,L,M),G)T2=(C,H)T3=(D,(I,N),(J,O,P))程式5-1　一般化串列鍵結節點的宣告1structTreeNode2{inttag;3union4{intdata;5structTreeNode*Tlink;6}nod

3、e;7structTreeNode*link;8};5.2.2　左子右兄弟表示法每個節點都有唯一的最左兒子(leftmostchild)；每個節點都有最靠近它的右兄弟。5.2.3　分支度為2的樹表示法分支度為2的樹又稱為二元樹(binarytree)。二元樹中任一節點皆有2個指標分別指向該節點的左子樹和右子樹。二元樹的節點構造分支度為2的樹表示法5.3二元樹二元樹是一個由節點組成的有限集合，可以是空集合，或是包含了(1)一個樹根節點；(2)其它節點分割成兩個沒有交集的二元樹，其一為左子樹(leftsubtree)，另一為右子樹

4、(rightsubtree)樹和二元樹之間的差異：(1)樹不允許空節點，而空二元樹是允許的；(2)樹的子樹沒有順序，而二元樹的子樹有左右之分。5.3.1樹和二元樹的基本性質樹或二元樹皆擁有下面的性質：定理5-1：若一棵樹T的總節點數為V，總邊數為E，則V=E+1。5.3.2二元樹的性質下圖(a)稱為歪斜樹(skewtree)；(b)稱為完備二元樹(completebinarytree)(其樹葉節點皆在相鄰階層，完整定義在後)。顯而易見地，同樣數目的樹節點放在歪斜樹上，得花較多的階層；放在完備二元樹上，則只須較少的階層。5.3.

5、2二元樹的性質(續)定理5-2說明了：(1)每一階層上可放的最多節點數；(2)階層數已知時，二元樹可放的最多節點數。定理5-2：(1)二元樹上階層i的節點數目最多為2i-1，i1；(2)深度為k的二元樹，其節點數目最多為2k-1，k1。對二元樹而言，任一節點的分支度可能為0、1、或2；分支度為0者是為樹葉。樹葉的數目與分支度為2的節點數目，存在著有趣的關係，請見定理5-3。定理5-3：若T為一非空的二元樹，n0為樹葉節點數目，n2為分支度為2的節點數目，則n0=n2+1。5.3.2二元樹的性質(續)下面是完滿二元樹(ful

6、lbinarytree)和完備二元樹(completebinarytree)的定義：定義：一個深度為k的完滿二元樹即為一深度為k且有2k-1個節點的二元樹，k0。由定理5-2(2)可得深度k的二元樹其最多節點數E為2k-1。這樣的樹會將樹上所有可能存放節點的位置都已放滿，完滿(full)之名因而生成。我們可對二元樹上節點予以編號，階層小者先編，同一階層則自左向右編號，這樣的編號方式，使我們定義出完備二元樹。定義：深度為k，節點數為n的二元樹稱為完備二元樹，若且唯若以階層小者先編號，同一階層由左至右遂一編號方法，可將1到n號分

7、別找到對應的節點。完滿或完備二元樹之所以受人注意，乃因它們可以將節點以較少的階層數存放。5.3.2二元樹的性質(續)定理5-4：n個節點的完備或完滿二元樹，其深度為log2(n+1)。在二元樹中非樹葉的節點，又稱為內部節點(internalnode)。若所有內部節點恰有2個子節點，即成為正規二元樹。正式定義如下：定義：若二元樹中所有內部節點恰有2個子節點，則稱之為正規二元樹(formalbinarytree)。正規二元樹常被引用在單淘汰賽制的各項賽程安排。樹葉為參賽隊伍，內部節點為優勝隊伍，樹根即為冠軍隊伍。5.4二元樹的

8、表示法5.4.1以陣列表示二元樹定理5-5：若一個具有n個節點的完備二元樹以循序的方式編號，並依序存放在陣列A中，即第i個節點放在A[i]中，1in，則(1)節點i的父節點位在A[i2]處，i≠1（i=1時，其節點正為樹根，無父節點）。(2)若2in，則節點i的左兒子