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

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

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

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

4、c TreeNode(Object o) / 構(gòu)造有值結(jié)點data = o;left = null;right = null;二叉樹類節(jié)點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é)點public TreeNode setRight(TreeNode right) return t

5、his.right = right;public TreeNode getRight() return right;/ 測試一個節(jié)點是否是葉子節(jié)點public boolean isLeaf() return left = null & right = null;/如何從最左節(jié)點或最右節(jié)點獲取數(shù)據(jù)？二叉樹類節(jié)點/從最左節(jié)點或最右節(jié)點獲取數(shù)據(jù)public Object getLeftmostData()if (left=null) return data; else return left.getLeftmostData();/如何刪除最左節(jié)點或最右節(jié)點？提示：二叉樹類節(jié)點/刪除最左或最右節(jié)點public TreeNode removeLeftmost()if(left=null)/最左節(jié)點是根節(jié)點，因為它沒有左孩子return right;else/一個遞歸調(diào)用刪除左子樹的最左節(jié)點left = left.removeLeftmost();return this;練習提供復制一棵二叉樹的