第一章-基本概念.ppt

第五章樹,資料結構與演算法,徐熊健,目錄,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，n0，而T1、T2、Tn本身皆為樹，稱其為R的子樹(subtree)。,5.1.2專有名詞,樹的定義：樹為節點組成的有限集合，其中(1)存在一特殊節點R稱為樹根(root)；(2)其它節點可分割成n個無交集的集合。T1,T2,Tn，n0，而T1、T2、Tn本身皆為樹，稱其為R的子樹(subtree)。在本章中若無特別聲明，所提到的樹皆為如定義所描述的有根樹(rootedtree)。,5.1.2專有名詞(續),節點:圖中圓圈和向下的分支樹根:節點A分支度:一個節點其所有子樹的數目樹葉:分支度為0的節點,兒子:任何節點X，其子樹的樹根Y，為X的兒子父親:Y是X的父親深度:樹的最高階層,5.2樹的表示法,一般化的串列表示左子右兄弟表示法(圖一)分支度為2的樹示法(圖二),圖一,圖二,5.2.1一般化的串列表示法,上圖的樹可表示成下面的一般化串列：(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一般化串列鍵結節點的宣告,1structTreeNode2inttag;3union4intdata;5structTreeNode*Tlink;6node;7structTreeNode*link;8;,5.2.2左子右兄弟表示法,每個節點都有唯一的最左兒子(leftmostchild)；每個節點都有最靠近它的右兄弟。,5.2.3分支度為2的樹表示法,分支度為2的樹又稱為二元樹(binarytree)。二元樹中任一節點皆有2個指標分別指向該節點的左子樹和右子樹。,二元樹的節點構造,分支度為2的樹表示法,5.3二元樹,二元樹是一個由節點組成的有限集合，可以是空集合，或是包含了(1)一個樹根節點；(2)其它節點分割成兩個沒有交集的二元樹，其一為左子樹(leftsubtree)，另一為右子樹(rightsubtree)樹和二元樹之間的差異：(1)樹不允許空節點，而空二元樹是允許的；(2)樹的子樹沒有順序，而二元樹的子樹有左右之分。,5.3.1樹和二元樹的基本性質,樹或二元樹皆擁有下面的性質：定理5-1：若一棵樹T的總節點數為V，總邊數為E，則V=E+1。,5.3.2二元樹的性質,下圖(a)稱為歪斜樹(skewtree)；(b)稱為完備二元樹(completebinarytree)(其樹葉節點皆在相鄰階層，完整定義在後)。顯而易見地，同樣數目的樹節點放在歪斜樹上，得花較多的階層；放在完備二元樹上，則只須較少的階層。,5.3.2二元樹的性質(續),定理5-2說明了：(1)每一階層上可放的最多節點數；(2)階層數已知時，二元樹可放的最多節點數。定理5-2：(1)二元樹上階層i的節點數目最多為2i-1，i1；(2)深度為k的二元樹，其節點數目最多為2k-1，k1。,對二元樹而言，任一節點的分支度可能為0、1、或2；分支度為0者是為樹葉。樹葉的數目與分支度為2的節點數目，存在著有趣的關係，請見定理5-3。定理5-3：若T為一非空的二元樹，n0為樹葉節點數目，n2為分支度為2的節點數目，則n0=n2+1。,5.3.2二元樹的性質(續),下面是完滿二元樹(fullbinarytree)和完備二元樹(completebinarytree)的定義：定義：一個深度為k的完滿二元樹即為一深度為k且有2k-1個節點的二元樹，k0。由定理5-2(2)可得深度k的二元樹其最多節點數E為2k-1。這樣的樹會將樹上所有可能存放節點的位置都已放滿，完滿(full)之名因而生成。我們可對二元樹上節點予以編號，階層小者先編，同一階層則自左向右編號，這樣的編號方式，使我們定義出完備二元樹。定義：深度為k，節點數為n的二元樹稱為完備二元樹，若且唯若以階層小者先編號，同一階層由左至右遂一編號方法，可將1到n號分別找到對應的節點。完滿或完備二元樹之所以受人注意，乃因它們可以將節點以較少的階層數存放。,5.3.2二元樹的性質(續),定理5-4：n個節點的完備或完滿二元樹，其深度為log2(n+1)。,在二元樹中非樹葉的節點，又稱為內部節點(internalnode)。若所有內部節點恰有2個子節點，即成為正規二元樹。正式定義如下：定義：若二元樹中所有內部節點恰有2個子節點，則稱之為正規二元樹(formalbinarytree)。,正規二元樹常被引用在單淘汰賽制的各項賽程安排。樹葉為參賽隊伍，內部節點為優勝隊伍，樹根即為冠軍隊伍。,5.4二元樹的表示法,5.4.1以陣列表示二元樹定理5-5：若一個具有n個節點的完備二元樹以循序的方式編號，並依序存放在陣列A中，即第i個節點放在Ai中，1in，則(1)節點i的父節點位在Ai2處，i1（i=1時，其節點正為樹根，無父節點）。(2)若2in，則節點i的左兒子節點位在A2i處；若2in，節點i沒有左兒子節點。(3)若2i+1n，節點i的右兒子節點位在A2i+1處；若2i+1n，節點i沒有左兒子節點。,5.5二元樹的走訪,假如一組資料已用二元樹的組織在一起，總有需求對其全數資料做動作，例如計算所有數目、印出所有資料、在所有資料中搜尋某項資料、等。此時即須對此二元樹做走訪(traversal)的運算，利用走訪二元樹的同時，將計算、列印或搜尋的動作完成。事實上走訪即在決定二元樹上資料被處理（計算、列印或搜尋）的順序。我們也希望走訪的演算法對任何節點皆一致，是容易撰寫程式實作的。若對一個二元樹上的節點而言，V表示處理節點上的資料，L表示走訪其左子樹，R表示走訪其右子樹。,5.5二元樹的走訪(續),因為對稱的緣故，我們可以只考慮先走訪左邊再走訪右邊的情形，那麼圖5-20(b)則只剩下三種走訪方式，我們以V所在的相對位置，分別對此三種走訪方式取名如下：(1)LVR中序走訪(inordertraversal)或中序表示法(infixnotation)；(2)LRV後序走訪(postordertraversal)或後序表示法(postfixnotation)；(3)VLR前序走訪(preordertraversal)或前序表示法(prefixnotation)。,5.5.1中序走訪,利用遞迴的方式撰寫中序走訪的程序；希望把二元樹中序走訪的順序印出來。,程式5-3二元樹的中序走訪1structBTreeNode2structBTreeNode*leftchild;3chardata;4structBTreeNode*rightchild;5;6structBTreeNode*root;7voidinorder(structBTreeNode*node)8if(node!=NULL)9inorder(node-leftchild);10coutdata;11inorder(node-rightchild);1213,範例5-12,下圖為一棵運算式二元樹。,其對應中序表示運算式為：(A+B)*C+D/(E-F)。,5.5.2後序走訪,茲將後序走訪的程序撰寫如下：程式5-4二元樹的後序走訪14voidpostorder(structBTreeNode*node)15if(node!=NULL)16postorder(node-leftchild);17postorder(node-rightchild);18coutdata;1920,以後序走訪，列出右圖之運算式二元樹中的所有資料，可得到：AB+C*D-/+其正為對應的後序運算式。,5.5.3前序走訪,前序走訪的程序可撰寫如下：程式5-5二元樹的前序走訪21voidpreorder(structBTreeNode*node)22if(node!=NULL)23coutdata;24preorder(node-leftchild);25preorder(node-rightchild);2627,以前序走訪，列出右圖之運算式二元樹中的所有資料，可得到：+*+ABC/D-EF其正為對應的前序運算式。,5.5.5階層走訪,階層走訪(level-ordertraversal)是依階層的順序，進行二元樹的走訪，先走訪階層小的節點，後走訪階層大的節點，同一階層者則依自左向右的順序走訪。對下圖的二元樹，進行階層走訪的結果為：ABCDEFGHI。對同一階層而言，先走訪的節點，其子節點亦在下一階層中先被走訪。這種先進先出的特性，恰可用佇列予以儲存與處,5.6二元樹的複製與相等測試,5.6.1二元樹的複製二元樹的複製可以用遞迴的方式來完成，請看下面的程序：程式5-8二元樹的複製1structBTreeNode2structBTreeNode*leftchild;3chardata;4structBTreeNode*rightchild;5;6structBTreeNode*root;7structBTreeNode*Copy(structBTreeNode*TreeRoot)8structBTreeNode*CopyRoot;9if(TreeRoot=NULL)10returnNULL;11CopyRoot=(structBTreeNode*)malloc(sizeof(BTreeNode);12CopyRoot-data=TreeRoot-data;13CopyRoot-leftchild=Copy(TreeRoot-leftchild);14CopyRoot-rightchild=Copy(TreeRoot-rightchild);15returnCopyRoot;16;,5.6.2二元樹的相等,下面的程式用遞迴的方式，檢測兩棵二元樹是否相等。程式5-9檢測兩棵二元樹是否相等1structBTreeNode2structBTreeNode*leftchild;3chardata;4structBTreeNode*rightchild;5;6structBtreeNode*rightchild;7intEqual(structBTreeNode*u,structBTreeNode*v);8if(u=NULL)15,5.7引線二元樹,在二元樹的鍵結表示中，樹葉節點的兩個子樹指標皆指向NULL；由定理5-1得知n=E+1，其中n為節點個數，E為分支數。而n個鍵結節點，有2n個指標空間，每個分支恰佔用一個指標空間，共有E(=n-1)個指標是用到的（不是空的），而共有n+1個指標空間是空指標(NULL)，比非空的節點還多。有學者提出對這些放空指標的空間加以利用的概念與其放空指標，不如放指向其它節點的指標，稱之為引線(thread)，使得某些運算（如：走訪、等）可以加快。這個概念發展出了引線二元樹(threadedbinarytree)這種資料結構。,範例5-17,下圖為加了引線的二元樹。,這些加入的引線將使二元樹的中序走訪更加便利。沿著上右圖箭頭所指示的順序走訪，即可完成此二元樹的中序走訪；GDHBAIECF為此二元樹的中序表示。,範例5-17(續),為了區別節點指標放的是一般指標（內部節點）、抑或是引線指標（樹葉節點），我們另以2個欄位分別區別左和右子樹指標空間存放的對象。其節點的記憶體配置有如下圖所示。,其中leftthread(rightthread)為0時，表示leftchild(rightchild)存放的是一般節點指標；leftthread(rightthread)為1時，表示leftchild(rightchild)存放的是引線指標。由上頁圖的引線二元樹可知，有最左和最右兩條引線尚無妥善的安排，我們另設計一空的引線節點做為樹根，那麼範例5-17的引線二元樹，將如下圖所示。,5.7.1引線二元樹的中序走訪,茲將引線二元樹所需節點的宣告詳列於程式5-10中，並定義決定節點p在中序表示中的後繼節點q（簡稱：中序後繼點）的程序：,程式5-10決定節點node的中序後繼點1structTBTreeNode2intleftthread;3structTBTreeNode*leftchild;4chardata;5structTBTreeNode*rightchild;6intrightthread;7;8structTBTreeNode*root;9structTBTreeNode*Next(structTBTreeNode*node)10structTBTreeNode*temp;11temp=node-rightchild;12if(node-rightthead)returntemp;13while(!temp-leftthead)temp=temp-leftchild;14returntemp;15;,5.7.1引線二元樹的中序走訪(續),程式5-11引線二元樹的中序表示（上接程式5-10）1voidInorderTBTree()2structTBTreeNode*node;3for(node=Next(root);node!=root;node=Next(node)4coutdata;5,於是要得到引線二元樹的中序表示，只須從中序表示中的第一節點起，讓每一節點node，都執行Next(node)程序，即可得：,5.7.2在引線二元樹中加入節點,在引線二元樹中，樹葉節點節點的右子樹指標所指向、或內部節點右子樹的最左樹葉，為其中序後繼節點；而且任一節點若無左子樹，則其左子樹指標乃指向其中序前接節點；這些性質必須在節點新增進入引線二元樹時，也要保持。在本節中我們討論節點new插入成為引線二元樹的節點p的右子節點的情形；至於插入成為左子節點的情形，則讓各位模擬推敲。,5.7.2在引線二元樹中加入節點(續),new會成為p的右子節點的情況，共有以下兩種：(1)若p沒有右子節點(p-rightthread為1)，如圖(a)，則new插入後應形成如圖(b)所示。(2)若p有右子節點(p-rightthread為0)，如圖(c)，則new插入後應形成如圖(d)所示。,程式5-12插入節點new成為引線二元樹中節點p的右子節點（上接程式5-10、5-11）,1voidInsertRight(structTBTreeNode*p,2structTBTreeNode*new)3structTBTreeNode*q;4new-rightchild=p-rightchild;5new-rightthead=p-rightthread;6new-leftchild=p;7new-leftthread=1;8p-rightchild=new;9p-rightthead=0;10if(!new-rightthread)11q=Next(new);12q-leftchild=new;1314,5.8堆積,堆積(heap)是一個特殊的完備二元樹，節點的資料與其子節點的資料之間，有事先定好的大小關係存在。正式的定義如下：定義：最大堆疊為一完備二元樹，任一節點的資料內容不小於其子節點的資料內容。最小堆疊為一完備二元樹，任一節點的資料內容不大於其子節點的資料內容。,5.8.1插入節點至最大堆積中,最大堆積是一完備二元樹，所以如圖(a)之最大堆積，於加入新節點後，樹的形狀必須如圖(b)所示，灰色節點即為新節點；若加入的節點資料分別為1，9，12，則其最大堆積將分別變成如圖(c)、(d)、(e)所示。,程式5-13新增節點至最大堆積中,最大堆積本身是一棵完備二元樹，可以用陣列表示之。下面是新增節點至最大堆積的程序。,1definemaxsize1002intheapmaxsize;3intn,i;4voidInsertHeap(intx)5if(n=maxsize)HeapFull();6else7n+;8i=n;9while(i=1)1416,5.8.2刪除最大堆積中的最大資料,圖(a)中的最大堆積，在刪除最大資料後，其樹形應變成如圖(b)所示；將最未一個樹葉節點的資料6，暫挪至樹根節點內，如圖5-37(c)；再將圖(c)些非最大堆積的結構，調整成為最大堆積：10和8中選大者與6對調，即成圖(d)。,程式5-14刪除最大堆積中的最大資料（上接程式5-13）,1intDeletHeap()2intx,i,j;3if(n=0)HeapEmpty();4else5x=heap1;6n-;7i=1;8while(iheap2*i+1)10j=2*i;11else12j=2*i+1;13heapi=heapj;14i=j;1516heapi=heapn+1;17returnx;1819,5.8.3優先佇列,由於最大堆積（或最小堆積）的結構，可提供最大元素（或最小元素），而其維護堆積的成本為O(logn)，n為總元素個數。堆積常被當成優先佇列(priorityqueue)使用此時佇列被組織成完備二元樹，若新加入佇列的資料有大小關係、優先順序的需求時，此優先佇列即以O(logn)的代價，將新資料放入優先佇列（可能是最大或最小堆積，依實際大小關係、優先順序的需求而定）中提供依元素的優先順序做為處理順序的服務。,5.9二元搜尋樹,二元搜尋樹是一棵二元樹，可能是空二元樹；若不為空二元樹，則滿足下列性質：所有節點內的資料內容是相異的左子節點的資內容(如果有)比父節點的資料內容小右子節點的資料內容(如果有)比父節點的資料內容大以左和右子節點為樹根的左子樹和右子樹也是二元搜尋樹,程式5-15在二元搜尋樹中搜尋資料（遞迴呼叫）,二元搜尋樹對資料大小的掌握十分明確若欲搜尋的資料x比樹節點p中的資料小，則只須搜尋節點p的左子樹；若比節點p中的資料大，則只須搜尋p的右子樹；若恰與節點p資料相等，則搜尋成功。這樣的判斷可以遞迴地應用在各子樹節點中。,1structBSTreeNode2structBSTreeNode*leftchild;3intdata;4structBSTreeNode*rightchild;5;6structBSTreeNode*root;7structBSTreeNode*SearchBST(structBSTreeNode*Tree,intx)8if(tree=NULL)returnNULL;9if(x=tree-data)returntree;10if(xdata)11returnSearchBST(tree-leftchild,x);12returnSearchBST(tree-rightchild,x);13,程式5-15在二元搜尋樹中搜尋資料（遞迴呼叫）,程式5-16在二元搜尋樹中搜尋資料（非遞迴呼叫）,在二元搜尋樹十分龐大時，遞迴呼叫的效率不會太好；可單純利用迴圈來完成搜尋的動作，以提高執行效率，請看程式5-16：,14structBSTreeNode*SearchBST_iterative15(structBSTreeNode*node,intx)16while(node!=NULL)17if(x=node-data)returnnode;18if(xdata)19node=node-leftchild;20else21node=node-leftchild;2223returnNULL;24,5.9.2新增資料於二元搜尋樹中,欲新增資料進入一二元搜尋樹中，得先決定該資料在二元搜尋樹中應出現的位置，這可透過5.9.1節提到的搜尋動作來解決；在二元搜尋樹定義的性質(1)中我們限定了元素必須相異，所以搜尋新資料的結果必是NULL必須將搜尋的結果，改為新增資料所應在位置的節點指標！,程式5-17在二元搜尋樹中新增資料,25intInsertBST(intx);26structBSTreeNode*p*q;27p=root;q=NULL;28while(p!=NULL)29q