《數(shù)據(jù)結(jié)構(gòu)JAVA版課件ppt.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)JAVA版課件ppt.ppt（30頁珍藏版）》請在匯文網(wǎng)上搜索。

1、The course of elaboration for Data Structures 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(JAVA版版)YT_JAVA煙臺職業(yè)學(xué)院精品課火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去第第7章章 樹和二叉樹樹和二叉樹樹樹 1二叉樹二叉樹 2二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 3樹轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹 5線索二叉樹線索二叉樹 6二叉樹的遍歷二叉樹的遍歷 4火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去71 樹樹v樹的定義樹的定義 樹是由一個或多個結(jié)點構(gòu)

2、成的有限集合。每棵樹必有一個稱做根的結(jié)點。樹是由一個或多個結(jié)點構(gòu)成的有限集合。每棵樹必有一個稱做根的結(jié)點。根結(jié)點可以有零個以上的子結(jié)點，而各子結(jié)點也可為子樹。根結(jié)點可以有零個以上的子結(jié)點，而各子結(jié)點也可為子樹。v樹的有關(guān)術(shù)語樹的有關(guān)術(shù)語l根結(jié)點根結(jié)點(root)一棵樹中沒有父結(jié)點的結(jié)點一棵樹中沒有父結(jié)點的結(jié)點l葉結(jié)點或終端結(jié)點葉結(jié)點或終端結(jié)點(leaf node)沒有子結(jié)點的結(jié)點沒有子結(jié)點的結(jié)點l非終端結(jié)點非終端結(jié)點(nonterminal)除了葉結(jié)點以外的其他結(jié)點除了葉結(jié)點以外的其他結(jié)點l父結(jié)點父結(jié)點(parent)和子結(jié)點和子結(jié)點(child)若結(jié)點若結(jié)點X有一個以結(jié)點有一個以結(jié)點Y為樹根

3、為樹根的子樹，則的子樹，則X為為Y的父結(jié)點，而的父結(jié)點，而Y就是就是X的子結(jié)點的子結(jié)點l兄弟兄弟(sibling)同一個父結(jié)點的結(jié)點同一個父結(jié)點的結(jié)點l分支度分支度(degree)每個結(jié)點的子結(jié)點數(shù)每個結(jié)點的子結(jié)點數(shù)l高度高度(height)或深度或深度(depth)一棵樹中最大層數(shù)一棵樹中最大層數(shù)l祖先祖先(ancestor)由結(jié)點由結(jié)點X到根結(jié)點路徑上所有的結(jié)點到根結(jié)點路徑上所有的結(jié)點l森林森林(forest)n0個樹的集合個樹的集合火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.2 二叉樹二叉樹v二叉樹（二叉樹（Binary

4、 tree）的遞歸定義）的遞歸定義 二叉樹是有二叉樹是有n個結(jié)點組成的有限集合，個結(jié)點組成的有限集合，n=0時為空二時為空二叉樹；叉樹；n0時，二叉樹是由有一個根結(jié)點和兩棵互不相時，二叉樹是由有一個根結(jié)點和兩棵互不相交的、分別稱為左子樹和右子樹構(gòu)成。二叉樹有一種有序交的、分別稱為左子樹和右子樹構(gòu)成。二叉樹有一種有序樹。樹。兩棵不同的二叉樹兩棵不同的二叉樹:火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去722 二叉樹的性質(zhì)二叉樹的性質(zhì)v二叉樹的第二叉樹的第I 層上最多有層上最多有2i-1個結(jié)點個結(jié)點v在深度為在深度為k的二叉樹中，最大

5、結(jié)點數(shù)為的二叉樹中，最大結(jié)點數(shù)為2k-1個結(jié)點個結(jié)點v二叉樹中，若葉子結(jié)點數(shù)為二叉樹中，若葉子結(jié)點數(shù)為n0，度為，度為2的結(jié)點數(shù)為的結(jié)點數(shù)為n2，則有，則有n0=n2+1v若一棵完全二叉樹有有若一棵完全二叉樹有有n個結(jié)點，則其深度為個結(jié)點，則其深度為k=log2n+1v一棵深度為一棵深度為k的滿二叉樹是具有的滿二叉樹是具有2k-1個結(jié)點的二叉樹。個結(jié)點的二叉樹。對滿二叉樹進行編號，從根結(jié)點開始，自上而下，自左到右編號。對滿二叉樹進行編號，從根結(jié)點開始，自上而下，自左到右編號。若一棵具有若一棵具有n個結(jié)點深度為個結(jié)點深度為k的二叉樹，若每個結(jié)點都與深度為的二叉樹，若每個結(jié)點都與深度為k的的滿二叉

6、樹編號為滿二叉樹編號為1n一一對應(yīng)，則稱此二叉樹為一一對應(yīng)，則稱此二叉樹為完全二叉樹完全二叉樹。v若將一棵具有若將一棵具有n個結(jié)點的完全二叉樹，對于編號為個結(jié)點的完全二叉樹，對于編號為i的結(jié)點，有如下的結(jié)點，有如下特點：特點：若i=1，則i為根結(jié)點，無雙親；否則i結(jié)點的雙親編號為i/2的結(jié)點。若2in，則i的左孩子編號為2i，否則i無左孩子。若2i+1n，則i的右孩子編號為2i+1，否則i無右孩子?；馂?zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)v 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)(適合

7、于完全二叉樹適合于完全二叉樹)非完全二叉樹的順序存儲結(jié)構(gòu)如下圖 火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)v二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) 二叉鏈?zhǔn)芥準(zhǔn)酱鎯Y(jié)構(gòu)的每個結(jié)點包含三個域:Root指向二叉樹的根結(jié)點。若二叉樹為空，則root=null。在一棵有n個結(jié)點的鏈?zhǔn)酱鎯Φ亩鏄渲?，有n+1個空鏈域。dataleftChildrightChild火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.3 二叉樹的存儲結(jié)構(gòu)二叉

8、樹的存儲結(jié)構(gòu)(1)不帶頭結(jié)點的二叉樹不帶頭結(jié)點的二叉樹;(2)帶頭結(jié)點的二叉樹帶頭結(jié)點的二叉樹ABCDEFG (a)ABCDEFG (b)rootroot 火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)v聲明二叉樹類聲明二叉樹類 二叉樹的結(jié)點類二叉樹的結(jié)點類 Package ds_java;Public class treenodel Public string data;Public treenode1 left,right;Public treenode1()This(“?”);Publi

9、c treenode1(string d)Data=d;Left=right=null;火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.4 二叉樹的遍歷二叉樹的遍歷v 遍歷二叉樹就是按照一定的規(guī)則訪問二叉樹中遍歷二叉樹就是按照一定的規(guī)則訪問二叉樹中所有的結(jié)點，并且每個結(jié)點僅被訪問一次。所謂所有的結(jié)點，并且每個結(jié)點僅被訪問一次。所謂的訪問，是指對每個結(jié)點數(shù)據(jù)進行查詢、修改等的訪問，是指對每個結(jié)點數(shù)據(jù)進行查詢、修改等操作。操作。v若對子樹的訪問按若對子樹的訪問按“先左后右先左后右”的次序進行，則的次序進行，則遍歷二叉樹有三種方法：遍歷

10、二叉樹有三種方法：l先根遍歷：訪問根結(jié)點，先根遍歷左子樹，先根先根遍歷：訪問根結(jié)點，先根遍歷左子樹，先根遍歷右子樹。遍歷右子樹。l中根遍歷：中根遍歷左子樹，訪問根結(jié)點，中根中根遍歷：中根遍歷左子樹，訪問根結(jié)點，中根遍歷右子樹。遍歷右子樹。l后根遍歷：后根遍歷左子樹，后根遍歷右子樹，后根遍歷：后根遍歷左子樹，后根遍歷右子樹，訪問根結(jié)點。訪問根結(jié)點?；馂?zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.4 二叉樹的遍歷二叉樹的遍歷實例實例 ABCDE可得到上面二叉樹先根遍歷的順序為：ABDCE中根遍歷上圖得到的順序為：BDAEC后根遍歷上面

11、的二叉樹得到的序列為：DBECA火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.4 二叉樹的遍歷二叉樹的遍歷v程序?qū)崿F(xiàn)程序?qū)崿F(xiàn) 先根遍歷遞歸程序先根遍歷遞歸程序 public static void PreOrder（int Pointer）if（Pointer！=-1）/遍歷的終止條件遍歷的終止條件 /處理打印節(jié)點內(nèi)容處理打印節(jié)點內(nèi)容 System.out.print(“”+TreeDataPointer+”)；PreOrder（LeftNodePointer）；）；/處理左子樹處理左子樹 PreOrder（RightNodeP

12、ointer）；）；/處理右子樹處理右子樹 火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.4 二叉樹的遍歷二叉樹的遍歷v程序?qū)崿F(xiàn)程序?qū)崿F(xiàn) 中序遍歷遞歸程序中序遍歷遞歸程序 public static void InOrder（int Pointer）if（Pointer！=-1）/遍歷的終止條件遍歷的終止條件 /處理打印節(jié)點內(nèi)容處理打印節(jié)點內(nèi)容 InOrder（LeftNodePointer）；）；/處理左子樹處理左子樹 System.out.print(“”+TreeDataPointer+”)；InOrder（RightNo

13、dePointer）；）；/處理右子樹處理右子樹 火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.4 二叉樹的遍歷二叉樹的遍歷后根遍歷遞歸程序后根遍歷遞歸程序:public static void PostOrder（int Pointer）if（Pointer！=-1）/遍歷的終止條件遍歷的終止條件 /處理打印節(jié)點內(nèi)容處理打印節(jié)點內(nèi)容 PostOrder（LeftNodePointer）；）；/處理左子樹處理左子樹 PostOrder（LeftNodePointer）；）；/處理左子樹處理左子樹 System.out.print

14、(“”+TreeDataPointer+”)；火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.4.3 二叉樹的非遞歸算法二叉樹的非遞歸算法v以中根遍歷為例以中根遍歷為例 中根遍歷二叉樹的非遞歸算法描述如下：設(shè)置一個中根遍歷二叉樹的非遞歸算法描述如下：設(shè)置一個棧為空；從二叉樹根結(jié)點棧為空；從二叉樹根結(jié)點P開始，若開始，若P不空或棧不空，循不空或棧不空，循環(huán)執(zhí)行以下操作，直到走完二叉樹或棧為空為止。環(huán)執(zhí)行以下操作，直到走完二叉樹或棧為空為止。l若若P不空，將不空，將P進棧，進入左子樹；進棧，進入左子樹；l若若P不空并且棧不空，出棧不空

15、并且棧不空，出棧P，訪問，訪問P結(jié)點，再進入結(jié)點，再進入P的右的右子樹。子樹。算法實現(xiàn)算法實現(xiàn):Tree5類繼承類繼承tree2類，以表明空子樹的先根次序建立類，以表明空子樹的先根次序建立一棵二叉樹。一棵二叉樹。設(shè)計一個棧設(shè)計一個棧stack1，元素是，元素是object對象，棧元素是二對象，棧元素是二叉樹的結(jié)點類叉樹的結(jié)點類treenode1。程序中將出棧的。程序中將出棧的object對對象強制轉(zhuǎn)換為象強制轉(zhuǎn)換為treenode1對象對象。火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.4.3 二叉樹的非遞歸算法二叉樹的非遞歸算

16、法 Public void inordertraver()Stack1 s1=new stack1(20);Treenode1 p=root;Syatem.out.print(“中根次序：中根次序：“);While(p|!s1.isempty()If(p)S1.push(p);P=p.left;Else P=(treenode1)s1.pop();System.out.print(p.data+”“);P=p.right;System.out.println();火災(zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要當(dāng)機立斷，披上浸濕的衣服或裹上濕毛毯、濕被褥勇敢地沖出去7.4.4 二叉樹的按層遍歷二叉樹的按層遍歷v二叉樹的層序遍歷算法如下二叉樹的層序遍歷算法如下：（1）初始化設(shè)置一個隊列；（2）把根結(jié)點指針入隊列；（3）當(dāng)隊列非空時，循環(huán)執(zhí)行以下步驟:（a）出隊列取得當(dāng)前隊頭結(jié)點，訪問該結(jié)點；（b）若該結(jié)點的左孩子結(jié)點非空，則將該結(jié)點的左孩子結(jié)點指針入隊列；（c）若該結(jié)點的右孩子結(jié)點非空，則將該結(jié)點的右孩子結(jié)點指針入隊列；（4）結(jié)束?；馂?zāi)襲來時要迅速疏散逃生，不可蜂擁而出或留戀財物，要