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

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

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

data;}public

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

left;}二叉樹類節(jié)點(diǎn)publicvoidsetData(Obje13二叉樹類節(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ù)？二叉樹類節(jié)點(diǎn)publicTreeNodesetRight14二叉樹類節(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)？提示：二叉樹類節(jié)點(diǎn)//從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)15二叉樹類節(jié)點(diǎn)//刪除最左或最右節(jié)點(diǎn)publicTreeNoderemoveLeftmost(){if(left==null){//最左節(jié)點(diǎn)是根節(jié)點(diǎn)，因?yàn)樗鼪]有左孩子return

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

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

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

data;}public

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

left;}二叉樹類節(jié)點(diǎn)publicvoidsetData(Obje31二叉樹類節(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ù)？二叉樹類節(jié)點(diǎn)publicTreeNodesetRight32二叉樹類節(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)？提示：二叉樹類節(jié)點(diǎn)//從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)33二叉樹類節(jié)點(diǎn)//刪除最左或最右節(jié)點(diǎn)publicTreeNoderemoveLeftmost(){if(left==null){//最左節(jié)點(diǎn)是根節(jié)點(diǎn)，因?yàn)樗鼪]有左孩子return

right;