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

1、學(xué)習(xí)目標(biāo)樹二叉樹的定義及性質(zhì)二叉樹的遍歷樹與二叉樹的轉(zhuǎn)換樹樹的定義樹的術(shù)語樹的定義樹（tree）是由n（n0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹稱為空樹；對(duì)n0的樹T，有：有一個(gè)特殊的結(jié)點(diǎn)稱為根結(jié)點(diǎn)（root），它只有直接后繼結(jié)點(diǎn)，沒有直接前驅(qū)結(jié)點(diǎn)。當(dāng)n1時(shí)，除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)分為m（m0）個(gè)互不相交的集合T1, T2, , Tm，其中每個(gè)集合Tm（1im）本身又是一棵結(jié)構(gòu)與樹類同的子樹（subtree）。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)，但可以有零或多個(gè)直接后繼結(jié)點(diǎn)。樹的術(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)樹的度二叉樹的定義及性質(zhì)二叉樹的定

2、義二叉樹的性質(zhì)二叉樹的存儲(chǔ)結(jié)構(gòu)聲明二叉樹類二叉樹的定義二叉樹的遞歸定義二叉樹（binary tree）是n（n0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0時(shí)稱為空二叉樹；n0的二叉樹由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹和右子樹的子二叉樹構(gòu)成。二叉樹的基本形態(tài)3個(gè)結(jié)點(diǎn)樹與二叉樹的基本形態(tài)二叉樹的性質(zhì)性質(zhì)1若根結(jié)點(diǎn)的層次為1，則二叉樹第i層的結(jié)點(diǎn)數(shù)目最多為2i-1（i1）。性質(zhì)2在深度為k的二叉樹中，至多有2k-1個(gè)結(jié)點(diǎn)（k0）。性質(zhì)3二叉樹中，若葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1。滿二叉樹與完全二叉樹性質(zhì)4如果一棵完全二叉樹有n個(gè)結(jié)點(diǎn)，則其深度。性質(zhì)5若將一棵具有n個(gè)結(jié)點(diǎn)的完全二

3、叉樹按順序表示，對(duì)于編號(hào)為i（1in）的結(jié)點(diǎn)，有如下特點(diǎn)：若i=1，則i為根結(jié)點(diǎn)，無雙親；若i1，則i的雙親是編號(hào)為i /2的結(jié)點(diǎn)。若2in，則i的左孩子是編號(hào)為2i的結(jié)點(diǎn)；若2in，則i無左孩子。若2i+1n，則i的右孩子是編號(hào)為2i+1的結(jié)點(diǎn)；若2i+1n，則i無右孩子。二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)聲明二叉樹類二叉樹的結(jié)點(diǎn)類public class TreeNode public Object data; / 數(shù)據(jù)元素public TreeNode left, right; / 指向左、右孩子結(jié)點(diǎn)的鏈public TreeNode() this(?);publi

4、c TreeNode(Object o) / 構(gòu)造有值結(jié)點(diǎn)data = o;left = null;right = null;二叉樹類節(jié)點(diǎn)public void setData(Object data) this.data = data;public Object getData() return data;public void setLeft(TreeNode left) this.left = left;public TreeNode getLeft() return left;二叉樹類節(jié)點(diǎn)public TreeNode setRight(TreeNode right) return t

5、his.right = right;public TreeNode getRight() return right;/ 測試一個(gè)節(jié)點(diǎn)是否是葉子節(jié)點(diǎn)public boolean isLeaf() return left = null & right = null;/如何從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)？二叉樹類節(jié)點(diǎn)/從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)public Object getLeftmostData()if (left=null) return data; else return left.getLeftmostData();/如何刪除最左節(jié)點(diǎn)或最右節(jié)點(diǎn)？提示：二叉樹類節(jié)點(diǎn)/刪除最左或最右節(jié)點(diǎn)public TreeNode removeLeftmost()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;練習(xí)提供復(fù)制一棵二叉樹的