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

1、學(xué)習(xí)目標(biāo) q樹 q二叉樹的定義及性質(zhì) q二叉樹的遍歷 q樹與二叉樹的轉(zhuǎn)換 樹 q樹的定義 q樹的術(shù)語(yǔ) 樹的定義 q 樹（tree）是由n（n0）個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹稱為空樹；對(duì) n0的樹T，有： q 有一個(gè)特殊的結(jié)點(diǎn)稱為根結(jié)點(diǎn)（root），它只有直接后繼結(jié)點(diǎn)，沒(méi)有直接前驅(qū)結(jié) 點(diǎn)。 q 當(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)。 A GH D EJ CB IF (a) n=0 空樹 (b)

2、 n=1 樹中只有一個(gè)根結(jié)點(diǎn) A rootroot level=1 level=2 level=3 depth=3 (c) n=10,度為3的樹 樹的術(shù)語(yǔ) q結(jié)點(diǎn) q孩子結(jié)點(diǎn)與雙親結(jié)點(diǎn) q兄弟結(jié)點(diǎn) q祖先結(jié)點(diǎn)與后代結(jié)點(diǎn) q結(jié)點(diǎn)的度 q葉子結(jié)點(diǎn)與分支結(jié)點(diǎn) q樹的度 二叉樹的定義及性質(zhì) q二叉樹的定義 q二叉樹的性質(zhì) q二叉樹的存儲(chǔ)結(jié)構(gòu) q聲明二叉樹類 二叉樹的定義 q二叉樹的遞歸定義 q二叉樹（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)樹與二叉

3、樹的基本形態(tài) 二叉樹的性質(zhì) q性質(zhì)1 q若根結(jié)點(diǎn)的層次為1，則二叉樹第i層的結(jié)點(diǎn)數(shù)目最多為 2i-1（i1）。 q性質(zhì)2 q在深度為k的二叉樹中，至多有2k-1個(gè)結(jié)點(diǎn)（k0）。 q性質(zhì)3 q二叉樹中，若葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則有 n0=n2+1。 q 滿二叉樹與完全二叉樹 q 性質(zhì)4 q 如果一棵完全二叉樹有n個(gè)結(jié)點(diǎn)，則其深度。 q 性質(zhì)5 q 若將一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹按順序表示，對(duì)于編號(hào)為i（1in） 的結(jié)點(diǎn)，有如下特點(diǎn)： q 若i=1，則i為根結(jié)點(diǎn)，無(wú)雙親；若i1，則i的雙親是編號(hào)為i /2的結(jié)點(diǎn)。 q 若2in，則i的左孩子是編號(hào)為2i的結(jié)點(diǎn)；若2in，則i無(wú)左孩子

4、。 q 若2i+1n，則i的右孩子是編號(hào)為2i+1的結(jié)點(diǎn)；若2i+1n，則i無(wú)右孩子。 二叉樹的存儲(chǔ)結(jié)構(gòu) q 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) C A B E G D left right data root (a) 二叉樹 (b) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) A BC DEG 聲明二叉樹類 q 二叉樹的結(jié)點(diǎn)類 public class TreeNode public Object data; / 數(shù)據(jù)元素 public TreeNode left, right; / 指向左、右孩子 結(jié)點(diǎn)的鏈 public TreeNode() this(?); public TreeNode(Object o)

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

6、 right) q return this.right = right; q q public TreeNode getRight() q return right; q q / 測(cè)試一個(gè)節(jié)點(diǎn)是否是葉子節(jié)點(diǎn) q public boolean isLeaf() q return left = null q q /如何從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù)？ 二叉樹類節(jié)點(diǎn) q /從最左節(jié)點(diǎn)或最右節(jié)點(diǎn)獲取數(shù)據(jù) q public Object getLeftmostData() q if (left=null) q return data; q else q return left.getLeftmostData(); q q q /如何刪除最左節(jié)點(diǎn)或最右節(jié)點(diǎn)？ q 提示： 二叉樹類節(jié)點(diǎn) q /刪除最左或最右節(jié)點(diǎn) qpublic TreeNode removeLeftmost() qif(left=null) q/最左節(jié)點(diǎn)是根節(jié)點(diǎn)，因?yàn)樗鼪](méi)有左孩子 qreturn right; qelse q/一個(gè)遞歸調(diào)用刪除左子樹的最左節(jié)點(diǎn) qleft = left.removeLeftmost(); qreturn this; q q 練習(xí)