Java數(shù)據(jù)結(jié)構(gòu)之樹(shù)與二叉樹(shù)課件

學(xué)習(xí)目標(biāo)樹(shù)二叉樹(shù)的定義及性質(zhì)二叉樹(shù)的遍歷樹(shù)與二叉樹(shù)的轉(zhuǎn)換學(xué)習(xí)目標(biāo)樹(shù)1樹(shù)樹(shù)的定義樹(shù)的術(shù)語(yǔ)樹(shù)樹(shù)的定義2樹(shù)的定義樹(shù)（tree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹(shù)稱為空樹(shù)；對(duì)n>0的樹(shù)T，有：有一個(gè)特殊的結(jié)點(diǎn)稱為根結(jié)點(diǎn)（root），它只有直接后繼結(jié)點(diǎn)，沒(méi)有直接前驅(qū)結(jié)點(diǎn)。當(dāng)n>1時(shí)，除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)分為m（m≥0）個(gè)互不相交的集合T1,T2,…,Tm，其中每個(gè)集合Tm（1≤i≤m）本身又是一棵結(jié)構(gòu)與樹(shù)類同的子樹(shù)（subtree）。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)，但可以有零或多個(gè)直接后繼結(jié)點(diǎn)。樹(shù)的定義樹(shù)（tree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。3樹(shù)的術(shù)語(yǔ)結(jié)點(diǎn)孩子結(jié)點(diǎn)與雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)與后代結(jié)點(diǎn)結(jié)點(diǎn)的度葉子結(jié)點(diǎn)與分支結(jié)點(diǎn)樹(shù)的度樹(shù)的術(shù)語(yǔ)結(jié)點(diǎn)4二叉樹(shù)的定義及性質(zhì)二叉樹(shù)的定義二叉樹(shù)的性質(zhì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)聲明二叉樹(shù)類二叉樹(shù)的定義及性質(zhì)二叉樹(shù)的定義5二叉樹(shù)的定義二叉樹(shù)的遞歸定義二叉樹(shù)（binarytree）是n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0時(shí)稱為空二叉樹(shù)；n>0的二叉樹(shù)由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的子二叉樹(shù)構(gòu)成。二叉樹(shù)的定義二叉樹(shù)的遞歸定義6二叉樹(shù)的基本形態(tài)3個(gè)結(jié)點(diǎn)樹(shù)與二叉樹(shù)的基本形態(tài)二叉樹(shù)的基本形態(tài)3個(gè)結(jié)點(diǎn)樹(shù)與二叉樹(shù)的基本形態(tài)7二叉樹(shù)的性質(zhì)性質(zhì)1若根結(jié)點(diǎn)的層次為1，則二叉樹(shù)第i層的結(jié)點(diǎn)數(shù)目最多為2i-1（i≥1）。性質(zhì)2在深度為k的二叉樹(shù)中，至多有2k-1個(gè)結(jié)點(diǎn)（k≥0）。性質(zhì)3二叉樹(shù)中，若葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1。二叉樹(shù)的性質(zhì)性質(zhì)18滿二叉樹(shù)與完全二叉樹(shù)性質(zhì)4如果一棵完全二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則其深度。性質(zhì)5若將一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按順序表示，對(duì)于編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)，有如下特點(diǎn)：若i=1，則i為根結(jié)點(diǎn)，無(wú)雙親；若i≠1，則i的雙親是編號(hào)為i/2的結(jié)點(diǎn)。若2i≤n，則i的左孩子是編號(hào)為2i的結(jié)點(diǎn)；若2i＞n，則i無(wú)左孩子。若2i+1≤n，則i的右孩子是編號(hào)為2i+1的結(jié)點(diǎn)；若2i+1＞n，則i無(wú)右孩子。滿二叉樹(shù)與完全二叉樹(shù)9二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)10二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)11聲明二叉樹(shù)類二叉樹(shù)的結(jié)點(diǎn)類public

classTreeNode{ publicObjectdata;//數(shù)據(jù)元素

publicTreeNodeleft,right;//指向左、右孩子結(jié)點(diǎn)的鏈

publicTreeNode(){ this("?"); } publicTreeNode(Objecto){//構(gòu)造有值結(jié)點(diǎn)

data=o; left=null; right=null; }}聲明二叉樹(shù)類二叉樹(shù)的結(jié)點(diǎn)類12二叉樹(shù)類節(jié)點(diǎn)public

voidsetData(Objectdata){this.data=data;}publicObjectgetData(){return

data;}public

voidsetLeft(TreeNodeleft){this.left=left;}publicTreeNodegetLeft(){return

left;}二叉樹(shù)類節(jié)點(diǎn)publicvoidsetData(Obje13二叉樹(shù)類節(jié)點(diǎn)publicTreeNodesetRight(TreeNoderight){return

this.right=right;}publicTreeNodegetRight(){return

right;}//測(cè)試一個(gè)節(jié)點(diǎn)是否是葉子節(jié)點(diǎn)public

booleanisLeaf(){return

left==null&&right==null;}//如何從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)？二叉樹(shù)類節(jié)點(diǎn)publicTreeNodesetRight14二叉樹(shù)類節(jié)點(diǎn)//從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)publicObjectgetLeftmostData(){if(left==null){return

data;}else{return

left.getLeftmostData();}}//如何刪除最左節(jié)點(diǎn)或最右節(jié)點(diǎn)？提示：二叉樹(shù)類節(jié)點(diǎn)//從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)15二叉樹(shù)類節(jié)點(diǎn)//刪除最左或最右節(jié)點(diǎn)publicTreeNoderemoveLeftmost(){if(left==null){//最左節(jié)點(diǎn)是根節(jié)點(diǎn)，因?yàn)樗鼪](méi)有左孩子return

right;}else{//一個(gè)遞歸調(diào)用刪除左子樹(shù)的最左節(jié)點(diǎn)left=left.removeLeftmost();return

this;}}二叉樹(shù)類節(jié)點(diǎn)//刪除最左或最右節(jié)點(diǎn)16練習(xí)提供復(fù)制一棵二叉樹(shù)的方法publicstaticTreeNodetreeCopy(TreeNodesource)練習(xí)提供復(fù)制一棵二叉樹(shù)的方法17練習(xí)編寫程序，求尋找最右邊節(jié)點(diǎn)的方法。編寫程序，求刪除最右邊節(jié)點(diǎn)的方法。練習(xí)編寫程序，求尋找最右邊節(jié)點(diǎn)的方法。18學(xué)習(xí)目標(biāo)樹(shù)二叉樹(shù)的定義及性質(zhì)二叉樹(shù)的遍歷樹(shù)與二叉樹(shù)的轉(zhuǎn)換學(xué)習(xí)目標(biāo)樹(shù)19樹(shù)樹(shù)的定義樹(shù)的術(shù)語(yǔ)樹(shù)樹(shù)的定義20樹(shù)的定義樹(shù)（tree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹(shù)稱為空樹(shù)；對(duì)n>0的樹(shù)T，有：有一個(gè)特殊的結(jié)點(diǎn)稱為根結(jié)點(diǎn)（root），它只有直接后繼結(jié)點(diǎn)，沒(méi)有直接前驅(qū)結(jié)點(diǎn)。當(dāng)n>1時(shí)，除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)分為m（m≥0）個(gè)互不相交的集合T1,T2,…,Tm，其中每個(gè)集合Tm（1≤i≤m）本身又是一棵結(jié)構(gòu)與樹(shù)類同的子樹(shù)（subtree）。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)，但可以有零或多個(gè)直接后繼結(jié)點(diǎn)。樹(shù)的定義樹(shù)（tree）是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。21樹(shù)的術(shù)語(yǔ)結(jié)點(diǎn)孩子結(jié)點(diǎn)與雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)與后代結(jié)點(diǎn)結(jié)點(diǎn)的度葉子結(jié)點(diǎn)與分支結(jié)點(diǎn)樹(shù)的度樹(shù)的術(shù)語(yǔ)結(jié)點(diǎn)22二叉樹(shù)的定義及性質(zhì)二叉樹(shù)的定義二叉樹(shù)的性質(zhì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)聲明二叉樹(shù)類二叉樹(shù)的定義及性質(zhì)二叉樹(shù)的定義23二叉樹(shù)的定義二叉樹(shù)的遞歸定義二叉樹(shù)（binarytree）是n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0時(shí)稱為空二叉樹(shù)；n>0的二叉樹(shù)由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的子二叉樹(shù)構(gòu)成。二叉樹(shù)的定義二叉樹(shù)的遞歸定義24二叉樹(shù)的基本形態(tài)3個(gè)結(jié)點(diǎn)樹(shù)與二叉樹(shù)的基本形態(tài)二叉樹(shù)的基本形態(tài)3個(gè)結(jié)點(diǎn)樹(shù)與二叉樹(shù)的基本形態(tài)25二叉樹(shù)的性質(zhì)性質(zhì)1若根結(jié)點(diǎn)的層次為1，則二叉樹(shù)第i層的結(jié)點(diǎn)數(shù)目最多為2i-1（i≥1）。性質(zhì)2在深度為k的二叉樹(shù)中，至多有2k-1個(gè)結(jié)點(diǎn)（k≥0）。性質(zhì)3二叉樹(shù)中，若葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1。二叉樹(shù)的性質(zhì)性質(zhì)126滿二叉樹(shù)與完全二叉樹(shù)性質(zhì)4如果一棵完全二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則其深度。性質(zhì)5若將一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按順序表示，對(duì)于編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)，有如下特點(diǎn)：若i=1，則i為根結(jié)點(diǎn)，無(wú)雙親；若i≠1，則i的雙親是編號(hào)為i/2的結(jié)點(diǎn)。若2i≤n，則i的左孩子是編號(hào)為2i的結(jié)點(diǎn)；若2i＞n，則i無(wú)左孩子。若2i+1≤n，則i的右孩子是編號(hào)為2i+1的結(jié)點(diǎn)；若2i+1＞n，則i無(wú)右孩子。滿二叉樹(shù)與完全二叉樹(shù)27二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)28二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)29聲明二叉樹(shù)類二叉樹(shù)的結(jié)點(diǎn)類public

classTreeNode{ publicObjectdata;//數(shù)據(jù)元素

publicTreeNodeleft,right;//指向左、右孩子結(jié)點(diǎn)的鏈

publicTreeNode(){ this("?"); } publicTreeNode(Objecto){//構(gòu)造有值結(jié)點(diǎn)

data=o; left=null; right=null; }}聲明二叉樹(shù)類二叉樹(shù)的結(jié)點(diǎn)類30二叉樹(shù)類節(jié)點(diǎn)public

voidsetData(Objectdata){this.data=data;}publicObjectgetData(){return

data;}public

voidsetLeft(TreeNodeleft){this.left=left;}publicTreeNodegetLeft(){return

left;}二叉樹(shù)類節(jié)點(diǎn)publicvoidsetData(Obje31二叉樹(shù)類節(jié)點(diǎn)publicTreeNodesetRight(TreeNoderight){return

this.right=right;}publicTreeNodegetRight(){return

right;}//測(cè)試一個(gè)節(jié)點(diǎn)是否是葉子節(jié)點(diǎn)public

booleanisLeaf(){return

left==null&&right==null;}//如何從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)？二叉樹(shù)類節(jié)點(diǎn)publicTreeNodesetRight32二叉樹(shù)類節(jié)點(diǎn)//從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)publicObjectgetLeftmostData(){if(left==null){return

data;}else{return

left.getLeftmostData();}}//如何刪除最左節(jié)點(diǎn)或最右節(jié)點(diǎn)？提示：二叉樹(shù)類節(jié)點(diǎn)//從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)33二叉樹(shù)類節(jié)點(diǎn)//刪除最左或最右節(jié)點(diǎn)publicTreeNoderemoveLeftmost(){if(left==null){//最左節(jié)點(diǎn)是根節(jié)點(diǎn)，因?yàn)樗鼪](méi)有左孩子return

right;