數(shù)據(jù)結(jié)構(gòu)主講人：蔣衛(wèi)祥常州信息職業(yè)技術(shù)學(xué)院4.1樹引言Introduction樹（Tree）結(jié)構(gòu)是除了根結(jié)點和葉子結(jié)點之外，樹中任意一個結(jié)點只有一個直接前驅(qū)結(jié)點（父結(jié)點）和多個直接后繼結(jié)點（孩子結(jié)點），根結(jié)點沒有前驅(qū)結(jié)點，葉子結(jié)點沒有后繼結(jié)點。本節(jié)學(xué)習(xí)樹的定義、樹的術(shù)語、樹的表示、樹的抽象數(shù)據(jù)類型、樹的存儲結(jié)構(gòu)。Part01樹的定義樹（Tree）是n（n≥0）個結(jié)點的有限集T，T為空時稱為空樹，T非空時它滿足以下兩個約定條件：①有且僅有一個特定的稱為根（Root）的結(jié)點。②其余的結(jié)點可分為m（m≥0）個互不相交的有限子集Tl，T2，…，Tm，其中每個子集本身又是一棵樹，并稱其為根的子樹（SubTree）。樹的概念樹的定義樹是遞歸定義的。結(jié)點是樹的基本單位，若干個結(jié)點組成一棵子樹，若干棵互不相交的子樹組成一棵樹。樹中的每一個結(jié)點都是該樹中某一棵子樹的根。因此，樹是由結(jié)點組成的、結(jié)點之間的具有層次關(guān)系的非線性結(jié)構(gòu)?？諛?、1個結(jié)點、n個結(jié)點的樹如右圖所示。樹的遞歸定義樹的定義Part02樹的術(shù)語1.結(jié)點、父母、孩子與兄弟結(jié)點樹的術(shù)語結(jié)點是樹的基本單位，結(jié)點是包含一個數(shù)據(jù)元素及指向其若干子樹的分支。在樹的圖形表示中為一個圓圈。結(jié)點的前驅(qū)結(jié)點稱為其父母（Parent）結(jié)點，結(jié)點的后繼結(jié)點稱為其孩子（Child）結(jié)點。一棵樹中只有根結(jié)點沒有父母結(jié)點，其他結(jié)點有且僅有一個父母結(jié)點。擁有同一個父母結(jié)點的多個結(jié)點之間稱為兄弟（Sibling）結(jié)點。結(jié)點的祖先(Ancestor)是指其父母結(jié)點以及父母的父母結(jié)點等，直至根結(jié)點。結(jié)點的后代（Descendant，也稱子孫）是指其所有孩子結(jié)點，以及孩子的孩子結(jié)點等。2.度樹的術(shù)語結(jié)點的度（Degree）是結(jié)點所擁有的子樹數(shù)。度為0的結(jié)點稱為葉子結(jié)點（Leaf），又稱為終端結(jié)點；樹中除葉子結(jié)點之外的其他結(jié)點稱為分支結(jié)點，又稱為非終端結(jié)點。樹的度是樹中各結(jié)點的度的最大值。3.結(jié)點層次、樹的高度樹的術(shù)語結(jié)點的層次（Level）反映結(jié)點在樹中的層次位置，約定根結(jié)點的層次為1，其余結(jié)點的層次等于其父母結(jié)點的層次加1。顯然，兄弟結(jié)點層次相同。樹的高度（Height）或深度（Depth）是指樹中各結(jié)點的層次最大值。4.邊、路徑樹的術(shù)語設(shè)樹中X結(jié)點是Y結(jié)點父母結(jié)點，有序?qū)Γ╔，Y）稱為連接這兩個結(jié)點的分支，也稱為邊。設(shè)（X0，X1，…，Xk-1）是樹中結(jié)點組成的序列，且（Xi，Xi+1）（0≦i≦k-1）都是樹中的邊，則稱該序列為X0到Xk-1的一條路徑（Path）。路徑長度（PathLength）為路徑上的邊數(shù)。5.無序樹、有序樹樹的術(shù)語

在樹的定義中，結(jié)點的子樹T0，Tl，T2，…，Tm-1之間沒有次序，可以交換位置，稱為無序樹。

如果結(jié)點的子樹T0，Tl，T2，…，Tm-1從左到右是有次序的，不能交換位置，則稱為有序樹。6.森林樹的術(shù)語森林（Forest）是m（m≥0）棵互不相交的樹的集合。對樹中的每一個結(jié)點而言，其子樹的集合即為森林，可以通過森林與樹相互遞歸的定義來描述樹。Part03樹的表示1.圖示法樹的表示結(jié)點用圓圈表示，結(jié)點名字寫在圓圈旁或圓圈內(nèi)，子樹與其根之間用無向邊來連接，如右圖是圖示法表示的樹。2.嵌套集合表示法樹的表示用集合的包含關(guān)系描述樹結(jié)構(gòu)，可以使用如右圖是樹的嵌套集合表示。3.凹入表示法樹的表示類似于書的目錄，使用線段的伸縮描述樹結(jié)構(gòu)。右圖是樹的凹入表示法。Part04樹的抽象數(shù)據(jù)類型樹的接口TTree樹的抽象數(shù)據(jù)類型publicinterfaceTTree<T>{

publicbooleanisEmpty();//判斷是否空樹

publicintcount();//返回樹的結(jié)點個數(shù)

publicintheight();//返回樹的高度//返回p結(jié)點的孩子結(jié)點個數(shù)

publicintchildCount(TreeNode<T>p);

publicvoidpreOrder();//先序遍歷樹

publicvoidpostOrder();//后序遍歷樹

publicvoidlevelOrder();//層次遍歷樹

//返回p結(jié)點的第i(i>=0)個孩子結(jié)點

publicTreeNode<T>getChild(TreeNode<T>p,inti);

//返回p結(jié)點的最后一個孩子結(jié)點publicTreeNode<T>getLastChild(TreeNode<T>p); //返回p結(jié)點的最后一個兄弟結(jié)點publicTreeNode<T>getLastSibling(TreeNode<T>p);//返回node的父結(jié)點publicTreeNode<T>getParent(TreeNode<T>node);publicTreeNode<T>search(Tx);//查找并返回元素為x的結(jié)點publicvoidinsertRoot(Tx);//插入元素x作為根結(jié)點//插入x元素作為p結(jié)點的第i個孩子publicTreeNode<T>insertChild(TreeNode<T>p,Tx,inti);

//插入最后一個孩子結(jié)點publicTreeNode<T>insertLastChild(TreeNode<T>p,Tx); //插入最后一個兄弟結(jié)點publicTreeNode<T>insertLastSibling(TreeNode<T>p,Tx);//刪除以P的第i個孩子為根的子樹publicvoidremoveChild(TreeNode<T>p,inti); publicvoidremoveAll();//刪除樹}樹的結(jié)點類樹的抽象數(shù)據(jù)類型publicclassTreeNode<T>{

publicTdata;//數(shù)據(jù)域，存儲數(shù)據(jù)元素

publicTreeNode<T>child;//孩子結(jié)點

publicTreeNode<T>sibling;//兄弟結(jié)點

publicTreeNode(Tdata,TreeNode<T>child,TreeNode<T>sibling){

this.data=data;

this.child=child;

this.sibling=sibling; }

publicTreeNode(Tdata){

this(data,null,null);//構(gòu)造指定值的葉子結(jié)點 }

publicTreeNode(){

this(null,null,null);//空樹 }}Part05樹的存儲結(jié)構(gòu)假設(shè)以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中，附設(shè)一個指示器指向其雙親結(jié)點到鏈表中的位置。也就是說每個結(jié)點除了知道自己之外還需要知道它的雙親在哪里。雙親表示法如右圖所示，其中data為結(jié)點本身，parent為其父結(jié)點（雙親）在鏈表中的位置（下標(biāo)）。1.雙親表示法樹的存儲結(jié)構(gòu)1.雙親表示法樹的存儲結(jié)構(gòu)由于根結(jié)點是沒有雙親的，約定根結(jié)點的位置域為-1。根據(jù)結(jié)點的parent指針很容易找到它的雙親結(jié)點。所用時間復(fù)雜度為O(1)，當(dāng)parent為-1時，表示找到了樹的根結(jié)點。缺點：如果要找到孩子結(jié)點，需要遍歷整個結(jié)構(gòu)才行。把每個結(jié)點的孩子結(jié)點排列起來，以單鏈表作為存儲結(jié)構(gòu)，則n個結(jié)點有n個孩子鏈表，如果是葉子結(jié)