Java數(shù)據(jù)結構之樹與二叉樹課件

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

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

publicTreeNodeleft,right;//指向左、右孩子結點的鏈

publicTreeNode(){ this("?"); } publicTreeNode(Objecto){//構造有值結點

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

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

data;}public

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

left;}二叉樹類節(jié)點publicvoidsetData(Obje13二叉樹類節(jié)點publicTreeNodesetRight(TreeNoderight){return

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

right;}//測試一個節(jié)點是否是葉子節(jié)點public

booleanisLeaf(){return

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

data;}else{return

left.getLeftmostData();}}//如何刪除最左節(jié)點或最右節(jié)點？提示：二叉樹類節(jié)點//從最左節(jié)點或最右節(jié)點獲取數(shù)據(jù)15二叉樹類節(jié)點//刪除最左或最右節(jié)點publicTreeNoderemoveLeftmost(){if(left==null){//最左節(jié)點是根節(jié)點，因為它沒有左孩子return

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

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

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

publicTreeNodeleft,right;//指向左、右孩子結點的鏈

publicTreeNode(){ this("?"); } publicTreeNode(Objecto){//構造有值結點

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

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

data;}public

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

left;}二叉樹類節(jié)點publicvoidsetData(Obje31二叉樹類節(jié)點publicTreeNodesetRight(TreeNoderight){return

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

right;}//測試一個節(jié)點是否是葉子節(jié)點public

booleanisLeaf(){return

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

data;}else{return

left.getLeftmostData();}}//如何刪除最左節(jié)點或最右節(jié)點？提示：二叉樹類節(jié)點//從最左節(jié)點或最右節(jié)點獲取數(shù)據(jù)33二叉樹類節(jié)點//刪除最左或最右節(jié)點publicTreeNoderemoveLeftmost(){if(left==null){//最左節(jié)點是根節(jié)點，因為它沒有左孩子return

right;