數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹

1、數(shù) 據(jù) 結(jié) 構(gòu),第 6 章 樹和二叉樹,線性結(jié)構(gòu)： 線性表（順序表、鏈表） 棧和隊(duì)列 數(shù)組、廣義表 非線性結(jié)構(gòu)： 樹 圖,引言,主要內(nèi)容,6.1 樹及其抽象數(shù)據(jù)類型 6.2 二叉樹 6.3 線索二叉樹 6.4 Huffman樹 6.5 樹的表示和實(shí)現(xiàn),樹結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。 樹結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。 樹結(jié)構(gòu)在客觀世界中是大量存在的，例如家譜、行政組織機(jī)構(gòu)都可用樹形象地表示。 樹在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹來(lái)組織信息；在分析算法的行為時(shí)，可用樹來(lái)描述其執(zhí)行過(guò)程，等等。

2、,6.1 樹及其抽象數(shù)據(jù)類型,樹結(jié)構(gòu),6.1 樹及其抽象數(shù)據(jù)類型,樹結(jié)構(gòu)舉例,由上可知，在樹結(jié)構(gòu)中，除根結(jié)點(diǎn)以外的結(jié)點(diǎn)只有一個(gè)直接前驅(qū)結(jié)點(diǎn)，可以有零個(gè)至多個(gè)直接后繼結(jié)點(diǎn)；根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。,6.1 樹及其抽象數(shù)據(jù)類型,樹結(jié)構(gòu),樹(Tree)是由n(n=0)個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹稱為空樹，n0的樹由以下兩個(gè)條件約定構(gòu)成： 1. 有且僅有一個(gè)特殊的稱為根(Root)的結(jié)點(diǎn)，它只有后繼結(jié)點(diǎn)，沒(méi)有前驅(qū)結(jié)點(diǎn)； 2. 其余的結(jié)點(diǎn)可分為m(nm=0)個(gè)互不相交的子集T0、T1、T2、Tm-1，其中每個(gè)子集又是一棵樹，并稱其為子樹(Subtree)。,6.1 樹及其抽象數(shù)據(jù)類型,樹定義,比如上圖，

3、左邊為只有一個(gè)結(jié)點(diǎn)的樹，A為根。右邊是一個(gè)有8個(gè)結(jié)點(diǎn)的樹，A為根，其余可以分為三個(gè)不相交的子集，也就是可以分為三個(gè)子樹。,A,6.1 樹及其抽象數(shù)據(jù)類型,樹定義,6.1 樹及其抽象數(shù)據(jù)類型,樹定義,結(jié)點(diǎn)的雙親結(jié)點(diǎn)或父母結(jié)點(diǎn)（parent）：結(jié)點(diǎn)上面的相鄰結(jié)點(diǎn)，或指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 結(jié)點(diǎn)n的孩子結(jié)點(diǎn)（child）：任何一個(gè)以n作為雙親結(jié)點(diǎn)的結(jié)點(diǎn)，或指結(jié)點(diǎn)n的后繼結(jié)點(diǎn) 樹的根（root）：有且僅有的一個(gè)特定的結(jié)點(diǎn)，它沒(méi)有雙親結(jié)點(diǎn),6.1 樹及其抽象數(shù)據(jù)類型,基本術(shù)語(yǔ),結(jié)點(diǎn)n的祖先結(jié)點(diǎn)（ancestor）：包括n的雙親結(jié)點(diǎn)， n的雙親結(jié)點(diǎn)的雙親結(jié)點(diǎn)，等等；即指從根結(jié)點(diǎn)到其父母結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn) 根是

4、樹中所有結(jié)點(diǎn)的公共祖先結(jié)點(diǎn) 結(jié)點(diǎn)n的子孫（后代）結(jié)點(diǎn)（descendant）：任何一個(gè)以n作為祖先結(jié)點(diǎn)的結(jié)點(diǎn)；即指結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，以及孩子的孩子等 兄弟結(jié)點(diǎn)（sibling）：如果結(jié)點(diǎn)m和n共有一個(gè)雙親結(jié)點(diǎn)，則稱m和n為兄弟結(jié)點(diǎn),6.1 樹及其抽象數(shù)據(jù)類型,基本術(shù)語(yǔ),葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)）（leaf）：沒(méi)有孩子結(jié)點(diǎn)的結(jié)點(diǎn) 分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：葉子結(jié)點(diǎn)之外的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或者非終端結(jié)點(diǎn) 子樹（subtree）：在樹T中，n的子孫結(jié)點(diǎn)組成了以n作為根的T的子樹,6.1 樹及其抽象數(shù)據(jù)類型,基本術(shù)語(yǔ),結(jié)點(diǎn)n的度（degree of node）：n的孩子結(jié)點(diǎn)的數(shù)量 樹的度（degree of

5、a tree）：樹中所有結(jié)點(diǎn)的最大度數(shù),6.1 樹及其抽象數(shù)據(jù)類型,基本術(shù)語(yǔ),結(jié)點(diǎn)n的層次（level）：結(jié)點(diǎn)n所處的樹中的層次位置。可以假設(shè)根的層次是0或1，本書中所有都假設(shè)根的層次為1，其他結(jié)點(diǎn)的層次是其父母結(jié)點(diǎn)的層次加1 樹的高度（heigh ）或深度（depth） ：樹中結(jié)點(diǎn)的最大層次數(shù),6.1 樹及其抽象數(shù)據(jù)類型,基本術(shù)語(yǔ),邊（edge）：設(shè)樹中X結(jié)點(diǎn)是Y結(jié)點(diǎn)的父母結(jié)點(diǎn)，有序?qū)Γ╔，Y）稱為連接這兩個(gè)結(jié)點(diǎn)的分支，也稱為邊 路徑（path）:從一個(gè)結(jié)點(diǎn)n到另一個(gè)結(jié)點(diǎn)的邊序列，如設(shè)（X0，X1，Xk-1）是由樹中結(jié)點(diǎn)組成的一個(gè)序列，且（Xi，Xi1）都是樹中的邊，則該序列稱為X0到Xk-

6、1的一條路徑 路徑長(zhǎng)度（length）：路徑中涉及到邊的數(shù)量,6.1 樹及其抽象數(shù)據(jù)類型,基本術(shù)語(yǔ),若把樹中每個(gè)結(jié)點(diǎn)的各子樹看成從左到右有次序的（即不能互換），則稱該樹為有序樹（Ordered Tree）；否則稱為無(wú)序樹（Unordered Tree） 森林（forest）：m棵互不相交的樹的集合（如：T0,T1,T2Tm-1），但可能為空,6.1 樹及其抽象數(shù)據(jù)類型,基本術(shù)語(yǔ),1樹形結(jié)構(gòu)表示法（圖示法） 具體參見(jiàn)下圖,6.1 樹及其抽象數(shù)據(jù)類型,樹的表示,2. 橫向凹入表示法 具體參見(jiàn)下圖,6.1 樹及其抽象數(shù)據(jù)類型,樹的表示,3. 嵌套集合表示法（文氏圖表示法） 具體參見(jiàn)下圖,6.1 樹及

7、其抽象數(shù)據(jù)類型,樹的表示,4. 廣義表表示法 對(duì)圖6-1（c）的樹結(jié)構(gòu)，廣義表表示法可表示為： （A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I）,6.1 樹及其抽象數(shù)據(jù)類型,樹的表示,ADT Tree /樹抽象數(shù)據(jù)類型 boolean isEmpty() /判空 int level(T key) /層次 int size() /結(jié)點(diǎn)數(shù) int height() /高度 void preorder() /先根次序遍歷 void postorder() /后根次序遍歷 void levelorder() /層次遍歷 TreeNode insert(T x) /插入元素x作為根 Tre

8、eNode insert(TreeNode p, T x, int i) /插入x作為p結(jié)點(diǎn)的第i（0）個(gè)孩子 void remove(TreeNode p, int i) /刪除子樹 void clear() /刪除所有結(jié)點(diǎn) TreeNode search(T key) /查找 boolean contains(T key) /包含 T remove(T key) /刪除子樹 ,6.1 樹及其抽象數(shù)據(jù)類型,樹的抽象數(shù)據(jù)類型,6.2 二叉樹,二叉樹定義1：樹的度小于等于2的樹（不完善）。 二叉樹定義2：二叉樹是一特殊的樹結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)子樹（即在樹中不存在度大于2的結(jié)點(diǎn)）

9、。 左孩子結(jié)點(diǎn)（left child）：二叉樹中結(jié)點(diǎn)的左孩子 右孩子結(jié)點(diǎn)（right child）：二叉樹中結(jié)點(diǎn)的右孩子 二叉樹定義3：二叉樹是n個(gè)結(jié)點(diǎn)的有限集合： 空二叉樹； 由一個(gè)根結(jié)點(diǎn)、兩棵互不相交的左子樹和右子樹組成。,二叉樹的定義,6.2 二叉樹,二叉樹的定義,圖 二叉樹的5種基本形態(tài),二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說(shuō)明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。 下圖列出二差樹的5種基本形態(tài)，圖(c) 和圖（d）是不同的兩棵二叉樹。,【思考題6-1】二叉樹與樹的差別,二叉樹是不是度為2的樹？二叉樹是不是度為2的有序樹？為什么？,2個(gè)結(jié)

10、點(diǎn)的樹和二叉樹的基本形態(tài),6.2 二叉樹,二叉樹的定義,【思考題6-1】,畫出3個(gè)結(jié)點(diǎn)的樹和二叉樹的基本形態(tài)。,6.2 二叉樹,二叉樹的定義,6.2 二叉樹,二叉樹的性質(zhì),性質(zhì)1： 在二叉樹的第 i 層上至多有2i-1 個(gè)結(jié)點(diǎn)。(i1),用歸納法證明： 歸納基： 歸納假設(shè)： 歸納證明：,i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)： 2i-1 = 20 = 1；,假設(shè)對(duì)所有的 j，1 j i，命題成立； 即第j層上至多有2j-1 個(gè)結(jié)點(diǎn)。,因二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹， 則第 i 層的結(jié)點(diǎn)數(shù) = 2(i-1)-1 2 = 2i-1 。,證明j=i時(shí)命題成立,第i-1層的結(jié)點(diǎn)數(shù),8,6.2 二叉樹,二叉

11、樹的性質(zhì),性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)（k1）。,證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 1 *（1-2k）/1-2 = 2k-1,性質(zhì) 3 ： 對(duì)任何一棵二叉樹，若它含有n0 個(gè)葉子結(jié)點(diǎn)、n2 個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式： n0 = n2+1。,證明： 設(shè) 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 又 設(shè)二叉樹上分支總數(shù)為 b ，則： 從前驅(qū) (入支）角度（從下向上） 有b= n-1 從后繼（出支）角度（從上向下） 有 b=n1+2n2 +0*n0 從而有： n0 + n1 + n2 1=

12、n1+2n2 由此， n0 = n2 + 1 。,6.2 二叉樹,二叉樹的性質(zhì),滿二叉樹（full binary tree）：一棵高度為h且有2h-1（h=0）個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。 以下說(shuō)法是否正確： 二叉樹中所有非葉結(jié)點(diǎn)的度數(shù)都為2的二叉樹是滿二叉樹（錯(cuò)）； 一個(gè)高度為h的滿二叉樹中，只在h層有葉結(jié)點(diǎn)，而且每一個(gè)非葉子結(jié)點(diǎn)都是滿的，是滿二叉樹（對(duì)）。,6.2 二叉樹,二叉樹的性質(zhì),完全二叉樹（complete binary tree）：如果深度為h、由n個(gè)結(jié)點(diǎn)的二叉樹中每個(gè)結(jié)點(diǎn)能夠與深度為h的順序編號(hào)的滿二叉樹從0到n-1標(biāo)號(hào)的結(jié)點(diǎn)一一對(duì)應(yīng)，則稱這樣的二叉樹為完全二叉樹。（滿二叉樹是

13、完全二叉樹的特例） 完全二叉樹的特點(diǎn)是： 在h層二叉樹中，所有的葉結(jié)點(diǎn)都出現(xiàn)在第h層或h1層。 對(duì)任一結(jié)點(diǎn)，如果其右子樹的最大層次為h，則其左子樹的最大層次為h或h1。,6.2 二叉樹,二叉樹的性質(zhì),6.2 二叉樹,二叉樹的性質(zhì),6.2 二叉樹,二叉樹的性質(zhì),性質(zhì)4：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為： log2n +1 。,證明：,設(shè)完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k-1 -1 n 2k -1 或 2k-1 n 2k 兩邊取對(duì)數(shù)得： k-1 log2 n k k log2 n +1 k +1 因?yàn)?k 只能是整數(shù)，因此， k =log2n + 1,深度為 k 的二叉樹上至多含

14、 2k - 1 個(gè)結(jié)點(diǎn)（k1）。,特點(diǎn),6.2 二叉樹,二叉樹的性質(zhì),性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，對(duì)序號(hào)為i（0in）的結(jié)點(diǎn)，有： 若i=0，則i為根結(jié)點(diǎn)，無(wú)父母結(jié)點(diǎn)； 若i0，則i的父母結(jié)點(diǎn)序號(hào)為(i-1)/2 若2i+1n，則i的左孩子結(jié)點(diǎn)在2i+1；否則i無(wú)左孩子。 若2i+2n，則i的右孩子結(jié)點(diǎn)在2i+2；否則i無(wú)右孩子。,6.2 二叉樹,二叉樹的遍歷規(guī)則,線形表的遍歷過(guò)程： 從首元素開始，訪問(wèn)（某個(gè)操作）每一個(gè)元素，直到尾元素。 樹性結(jié)構(gòu)如何遍歷？,回顧線形數(shù)據(jù)結(jié)構(gòu)的遍歷,6.2 二叉樹,二叉樹的遍歷規(guī)則,二叉樹的遍歷指的是沿某條搜索路徑訪問(wèn)二叉樹，對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)訪問(wèn)

15、一次且僅一次。這里的“訪問(wèn)”實(shí)際上指的是對(duì)結(jié)點(diǎn)進(jìn)行某種操作。 (以下“訪問(wèn)”特指打印該結(jié)點(diǎn)信息),定義,所有遍歷序列有6種： ABC，BAC，BCA， /先左孩子 CBA，CAB，ACB。 /先右孩子 約定遍歷子樹的次序是先左子樹后右子樹,6.2 二叉樹,二叉樹的遍歷規(guī)則,孩子優(yōu)先的遍歷規(guī)則,先根次序：訪問(wèn)根結(jié)點(diǎn)，先根遍歷左子樹，先根遍歷右子樹。 中根次序：中根遍歷左子樹，訪問(wèn)根結(jié)點(diǎn)，中根遍歷右子樹。 后根次序：后根遍歷左子樹，后根遍歷右子樹，訪問(wèn)根結(jié)點(diǎn)。 先根遍歷序列：A B D G C E F H 中根遍歷序列：D G B A E C H F 后根遍歷序列：G D B E H F C A,

16、孩子優(yōu)先的遍歷規(guī)則,6.2 二叉樹,二叉樹的遍歷規(guī)則,層次遍歷序列： A B C D E F G H,兄弟優(yōu)先的遍歷規(guī)則,6.2 二叉樹,二叉樹的遍歷規(guī)則,給出二叉樹的先根、中根、后根和層次遍歷序列。,習(xí)題,6.2 二叉樹,二叉樹的遍歷規(guī)則,ADT BinaryTree boolean isEmpty() /判空 int size() /結(jié)點(diǎn)數(shù) int height() /高度 void preOrder() /先根次序遍歷 void inOrder() /中根次序遍歷 void postOrder() /后根次序遍歷 void levelOrder() /按層次遍歷 BinaryNode i

17、nsert(T x) /插入根 BinaryNode insert(BinaryNode p, T x, boolean leftChild) /插入孩子 void remove(BinaryNode parent, boolean leftChild) /刪除子樹 void clear() /刪除所有結(jié)點(diǎn) BinaryNode search(T key) /查找 boolean contains(T key) /包含 int level(T key) /key結(jié)點(diǎn)所在層次 ,6.2 二叉樹,二叉樹抽象數(shù)據(jù)類型,順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的順序存儲(chǔ)結(jié)構(gòu)

18、,順序存儲(chǔ)結(jié)構(gòu)： 它是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素 順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)： 存儲(chǔ)單元僅僅存儲(chǔ)結(jié)點(diǎn)的值 二叉樹結(jié)點(diǎn)之間的邏輯關(guān)系由數(shù)組中下標(biāo)的順序來(lái)體現(xiàn),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),因此，必須把二叉樹的所有結(jié)點(diǎn)安排成為一個(gè)恰當(dāng)?shù)男蛄校Y(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系： 首先要為一個(gè)深度為h的樹分配一個(gè)大小為 2h1的數(shù)組 然后用此數(shù)組自上而下、自左而右地存儲(chǔ)與此樹對(duì)應(yīng)的完全二叉樹上的結(jié)點(diǎn),二叉樹的順序存儲(chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹順序存儲(chǔ)的原則： 不管給定的二叉樹是不是完全二叉樹，都看作完全二叉樹，即按完全二叉樹的層次次序（從上到下，從左到

19、右）把各結(jié)點(diǎn)依次存入數(shù)組中 此結(jié)構(gòu)有什么缺點(diǎn)？,二叉樹的順序存儲(chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的順序存儲(chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的順序存儲(chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹順序存儲(chǔ)結(jié)構(gòu)中其他結(jié)點(diǎn)的確定（性質(zhì)5）： 假設(shè)給定結(jié)點(diǎn)的地址為I，則： （1）若I0，則該結(jié)點(diǎn)是為根結(jié)點(diǎn)，無(wú)父親。 （2）若I0，則該結(jié)點(diǎn)的父親結(jié)點(diǎn)地址為I-12的整數(shù)部分。 （3）若2I+1n，則該結(jié)點(diǎn)的左兒子結(jié)點(diǎn)地址為2I+1，否則該結(jié)點(diǎn)無(wú)左兒子。 （4）若2I+2 n，則該結(jié)點(diǎn)的右兒子結(jié)點(diǎn)地址為2I+2，否則該結(jié)點(diǎn)無(wú)右兒子。 （5）若I為奇數(shù)（除根結(jié)點(diǎn)），則該結(jié)點(diǎn)的右兄

20、弟為I1。 （6）若I為偶數(shù)（除根結(jié)點(diǎn)），則該結(jié)點(diǎn)的左兄弟為I1。,二叉樹的順序存儲(chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),對(duì)于一棵二叉樹,若采用順序存貯時(shí),當(dāng)它為完全二叉樹時(shí),比較方便,若為非完全二叉樹,將會(huì)浪費(fèi)大量存貯存貯單元。 最壞的非完全二叉樹是全部只有右分支,設(shè)高度為K,則需占用2K-1個(gè)存貯單元,而實(shí)際只有k個(gè)元素,實(shí)際只需k個(gè)存儲(chǔ)單元。 因此，對(duì)于非完全二叉樹，宜采用下面的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,二叉樹的順序存儲(chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),由二叉樹的定義可知，二叉樹的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和兩個(gè)分別指向其左右子樹的兩個(gè)分支構(gòu)成，所以二叉樹的結(jié)點(diǎn)包括兩個(gè)部分：數(shù)據(jù)域、左、右指針域。

21、 有時(shí)候?yàn)榱朔奖阏业皆摻Y(jié)點(diǎn)的雙親還會(huì)在設(shè)置一個(gè)指針域指向其雙親結(jié)點(diǎn)。,二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉鏈表中一個(gè)結(jié)點(diǎn)可描述為：,二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),如何采用以上結(jié)點(diǎn)結(jié)構(gòu)表示二叉樹？ 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示二叉樹時(shí)，需要一個(gè)根指針（root）指向根結(jié)點(diǎn) 若二叉樹為空，則根結(jié)點(diǎn)為NULL 若結(jié)點(diǎn)的某個(gè)兒子不存在，則相應(yīng)的指針為空,二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),對(duì)于上圖所示二叉樹,用二叉鏈表形式描述見(jiàn)下圖：,二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)

22、結(jié)構(gòu),考慮：n個(gè)結(jié)點(diǎn)的二叉樹中，有多少個(gè)指針域，其中多少個(gè)指向左、右孩子，多少個(gè)為空？ 若一棵二叉樹有n個(gè)結(jié)點(diǎn),采用二叉鏈表作存貯結(jié)構(gòu)時(shí),共有2n個(gè)指針域,其中只有n-1個(gè)指針指向左右孩子,其余n+1個(gè)指針為空,沒(méi)有發(fā)揮作用,被白白浪費(fèi)掉了。,二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),在二叉鏈表結(jié)點(diǎn)的基礎(chǔ)上，三叉鏈表增加一條鏈parent連接父母結(jié)點(diǎn)，這樣就存儲(chǔ)了父母結(jié)點(diǎn)與孩子結(jié)點(diǎn)的雙向關(guān)系，每個(gè)結(jié)點(diǎn)至少有4個(gè)域。,二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),6.2 二叉樹,二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的二叉鏈表結(jié)點(diǎn)類 public class Bi

23、naryNode T data; /數(shù)據(jù)元素 BinaryNode left, right; /左、右孩子 public BinaryNode(T data, BinaryNode left, BinaryNode right) /構(gòu)造結(jié)點(diǎn) public BinaryNode(T data) /構(gòu)造葉子 public String toString() /描述字符串 public boolean isLeaf() /判結(jié)點(diǎn) ,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),/1. 二叉鏈表結(jié)點(diǎn)類 public class BinaryNode /二叉樹的二叉鏈表結(jié)點(diǎn)類，T指定結(jié)點(diǎn)的元素類型 public

24、 T data; /數(shù)據(jù)域，存儲(chǔ)數(shù)據(jù)元素 public BinaryNode left, right; /鏈域，分別指向左、右孩子結(jié)點(diǎn) /構(gòu)造結(jié)點(diǎn)，data指定元素，left、right分別指向左孩子和右孩子結(jié)點(diǎn) public BinaryNode(T data, BinaryNode left, BinaryNode right) this.data = data; this.left = left; this.right = right; ,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),二叉樹的結(jié)點(diǎn)類 public BinaryNode(T data) /構(gòu)造元素為data的葉子結(jié)點(diǎn) this(d

25、ata, null, null); public String toString() /返回結(jié)點(diǎn)數(shù)據(jù)域的描述字符串 return this.data.toString(); public boolean isLeaf() /判斷是否葉子結(jié)點(diǎn) return this.left=null ,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),二叉樹類 public class BinaryTree BinaryNode root; /根結(jié)點(diǎn) public BinaryTree() /構(gòu)造空樹 public boolean isEmpty() /判空 ,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),二叉樹類 public

26、 class BinaryTree /二叉樹類，二叉鏈表存儲(chǔ)，T指定結(jié)點(diǎn)的元素類型 public BinaryNode root; /根結(jié)點(diǎn)，二叉鏈表結(jié)點(diǎn)結(jié)構(gòu) public BinaryTree() /構(gòu)造空二叉樹 this.root=null; public boolean isEmpty() /判斷是否空二叉樹 return this.root=null; ,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),二叉樹插入結(jié)點(diǎn),BinaryNode insert(T x) /插入根結(jié)點(diǎn) BinaryNode insert(BinaryNode parent, T x, boolean leftChild)

27、 /插入x為parent結(jié)點(diǎn)的左/右孩子,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),public BinaryNode insert(T x) /插入x作為根結(jié)點(diǎn)，原根結(jié)點(diǎn)作為x的左孩子；返回插入結(jié)點(diǎn) return this.root = new BinaryNode(x, this.root, null); /插入x為parent結(jié)點(diǎn)的左/右孩子，leftChild指定孩子，取值為true（左）、false（右）； /parent的原左/右孩子成為x結(jié)點(diǎn)的左/右孩子；返回插入結(jié)點(diǎn)。 /若x=null，不插入，返回null。若parent=null，Java拋出空對(duì)象異常。 public Bina

28、ryNode insert(BinaryNode parent, T x, boolean leftChild) if (x=null) return null; if (leftChild) /插入x為parent結(jié)點(diǎn)的左/右孩子，返回插入結(jié)點(diǎn) return parent.left=new BinaryNode(x, parent.left, null); return parent.right=new BinaryNode(x, null, parent.right); ,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),/刪除parent結(jié)點(diǎn)的左/右子樹 public void remove(Bin

29、aryNode parent, boolean leftChild) public void clear() /刪除所有結(jié)點(diǎn),6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),/ 二叉樹刪除子樹 /刪除parent結(jié)點(diǎn)的左或右子樹，leftChild指定子樹，取值為true（左）、false（右） /Java自動(dòng)收回被刪除子樹占用的存儲(chǔ)空間。 public void remove(BinaryNode parent, boolean leftChild) if (leftChild) parent.left = null; /若parent=null，Java拋出空對(duì)象異常 else parent.rig

30、ht = null; public void clear() /刪除二叉樹的所有結(jié)點(diǎn) this.root = null; ,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),先根遍歷,1按先根次序遍歷二叉樹的遞歸算法，將如下算法添加到二叉樹類BinaryTree中 若二叉樹為空，返回；否則，繼續(xù)。 從根結(jié)點(diǎn)開始，訪問(wèn)當(dāng)前結(jié)點(diǎn)。 按先根次序遍歷當(dāng)前結(jié)點(diǎn)的左子樹。 按先根次序遍歷當(dāng)前結(jié)點(diǎn)的右子樹。 private void preorder(BinaryNode p) /先根次序遍歷以p結(jié)點(diǎn)為根的子樹，遞歸方法 if (p!=null) /若二叉樹不空 System.out.print(p.data.toSt

31、ring()+ ); /先訪問(wèn)當(dāng)前結(jié)點(diǎn)元素 preorder(p.left); /按先根次序遍歷p的左子樹，遞歸調(diào)用，參數(shù)為左孩子 preorder(p.right); /按先根次序遍歷p的右子樹，遞歸調(diào)用，參數(shù)為右孩子 ,6.2 二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),遞歸方法必須有參數(shù)，通過(guò)不同的實(shí)際參數(shù)區(qū)別遞歸調(diào)用執(zhí)行中的多個(gè)方法。 一棵二叉樹由多棵子樹組成，一個(gè)結(jié)點(diǎn)也是一棵子樹的根。 二叉樹類中實(shí)現(xiàn)遍歷規(guī)則的遞歸算法以p為參數(shù)，表示以某種次序遍歷以p結(jié)點(diǎn)為根的子樹，當(dāng)p指向不同結(jié)點(diǎn)時(shí)，遍歷不同的子樹；當(dāng)p為空子樹時(shí)，遞歸結(jié)束。 二叉樹類還必須提供從根結(jié)點(diǎn)開始遍歷的方法，因此，每種遍歷算法由兩個(gè)重

32、載方法實(shí)現(xiàn)，如preOrder()和preOrder(p)。,先根遍歷,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,public void preorder() /輸出先根次序遍歷序列 / System.out.print(先根次序遍歷二叉樹： ); preorder(this.root); /調(diào)用先根次序遍歷二叉樹的遞歸方法 System.out.println(); ,先根遍歷,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,public String toString() /返回先根次序遍歷二叉樹所有結(jié)點(diǎn)的描述字符串 return toString(this.root); private String

33、toString(BinaryNode p) /返回先根次序遍歷以p為根的子樹描述字符串，遞歸方法 if (p=null) return ; /輸出空子樹標(biāo)記 return p.data.toString()+ + toString(p.left) + toString(p.right); ,先根遍歷,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,將如下算法添加到二叉樹類BinaryTree中 public void inorder() /輸出中根次序遍歷序列 / System.out.print(中根次序遍歷二叉樹： ); inorder(this.root); System.out.println

34、(); private void inorder(BinaryNode p) /中根次序遍歷以p結(jié)點(diǎn)為根的子樹，遞歸方法 if (p!=null) inorder(p.left); /中根次序遍歷p的左子樹，遞歸調(diào)用 System.out.print(p.data.toString()+ ); inorder(p.right); /中根次序遍歷p的右子樹，遞歸調(diào)用 ,中根遍歷,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,將如下算法添加到二叉樹類BinaryTree中 public void postorder() /輸出后根次序遍歷序列 / System.out.print(后根次序遍歷二叉樹： )

35、; postorder(this.root); System.out.println(); private void postorder(BinaryNode p) /后根次序遍歷以p結(jié)點(diǎn)為根的子樹，遞歸方法 if (p!=null) postorder(p.left); postorder(p.right); System.out.print(p.data.toString()+ ); /后訪問(wèn)當(dāng)前結(jié)點(diǎn)元素 ,后根遍歷,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,僅知二叉樹的先序序列”abcdefg” 不能唯一確定一棵二叉樹，如果同時(shí)已知二叉樹的中序序列”cbdaegf”，則會(huì)如何？,思考題 由二

36、叉樹的先序和中序序列建樹,二叉樹的先序序列,二叉樹的中序序列,左子樹,左子樹,右子樹,右子樹,根,根,確定原則： 由先序序列確定二叉樹的根結(jié)點(diǎn)， 由中序序列確定二叉樹的左右子樹序列。,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,a b c d e f g,c b d a e g f,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,由二叉樹的 先序和中序序 序列確定二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,已知一個(gè)二叉樹的先根遍歷序列和中根遍歷序列，能否畫出這個(gè)二叉樹。（可以） 已知一個(gè)二叉樹的后根遍歷序列和中根遍歷序列，能否畫出這個(gè)二叉樹。（

37、可以） 已知一個(gè)二叉樹的先根遍歷序列和后根遍歷序列，能否畫出這個(gè)二叉樹。（不可以）,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,思考題,基于遍歷的操作,求結(jié)點(diǎn)個(gè)數(shù) 求高度 查找 獲得父母結(jié)點(diǎn),二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,求結(jié)點(diǎn)個(gè)數(shù) public int size() /返回二叉樹的結(jié)點(diǎn)數(shù) return size(root); public int size(BinaryNode p) /返回以p結(jié)點(diǎn)為根的子樹的結(jié)點(diǎn)數(shù) if (p=null) return 0; return 1+size(p.left)+size(p.right); ,基于遍歷的操作,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,

38、求高度：必須采用后跟次序遍歷算法，只有先分別計(jì)算出左、右子樹高度的情況下，才能計(jì)算當(dāng)前子樹高度 public int height() /返回二叉樹的高度 return height(root); public int height(BinaryNode p) /返回以p結(jié)點(diǎn)為根的子樹高度，后根次序遍歷 if (p=null) return 0; int lh = height(p.left); /返回左子樹的高度 int rh = height(p.right); /返回右子樹的高度 return (lh=rh) ? lh+1 : rh+1; /當(dāng)前子樹高度為較高子樹的高度加1 ,基于遍歷的

39、操作,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,查找 public T search(T key) /查找并返回首次出現(xiàn)的關(guān)鍵字為key元素 return searchNode(root, key).data; public BinaryNode searchNode(T key) /查找并返回首次出現(xiàn)的關(guān)鍵字為key元素結(jié)點(diǎn) return searchNode(root, key); /在以p為根的子樹中查找并返回首次出現(xiàn)的關(guān)鍵字為key元素結(jié)點(diǎn)，若未找到返回null，先根次序遍歷 public BinaryNode searchNode(BinaryNode p, T key) if (p=n

40、ull | key=null) return null; if (p.data.equals(key) return p; /查找成功，返回找到結(jié)點(diǎn) BinaryNode find=searchNode(p.left, key); /在左子樹中查找，遞歸調(diào)用 if (find=null) /若在左子樹中未找到 find=searchNode(p.right, key); /則繼續(xù)在右子樹中查找，遞歸調(diào)用 return find; /返回查找結(jié)果 ,基于遍歷的操作,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,獲得父母結(jié)點(diǎn) /返回node結(jié)點(diǎn)的父母結(jié)點(diǎn)，若空樹、未找到或node為根，則返回null pu

41、blic BinaryNode getParent(BinaryNode node) if (root=null | node=null | node=root) return null; return getParent(root, node); /在以p為根的子樹中查找并返回node結(jié)點(diǎn)的父母結(jié)點(diǎn) public BinaryNode getParent(BinaryNode p, BinaryNode node) if (p=null) return null; if (p.left=node | p.right=node) return p; BinaryNode find = getP

42、arent(p.left, node); if (find=null) find = getParent(p.right, node); return find; ,基于遍歷的操作,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,/返回以p結(jié)點(diǎn)為根子樹的結(jié)點(diǎn)數(shù) int size(BinaryNode p) static int n=0; if (p!=null) n+; size(p.left); size(p.right); ,【習(xí)題解答】存在錯(cuò)誤： Java語(yǔ)言方法體中的局部變量不能聲明為static。 如果用局部變量n計(jì)數(shù)，每次n=0，再n+，n=1，無(wú)法實(shí)現(xiàn)計(jì)數(shù)，并且結(jié)果無(wú)法返回給調(diào)用者。,思考

43、題 遞歸方法參數(shù)與返回值問(wèn)題討論。有什么錯(cuò)誤？,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,構(gòu)造二叉樹,構(gòu)造一棵二叉樹必須明確以下兩種關(guān)系： 結(jié)點(diǎn)與其雙親結(jié)點(diǎn)及孩子結(jié)點(diǎn)間的層次關(guān)系。 兄弟結(jié)點(diǎn)間左或右的次序關(guān)系。 關(guān)系的確定： 先根遍歷和后跟遍歷反映雙親與孩子結(jié)點(diǎn)之間的層次關(guān)系 中跟遍歷反映兄弟結(jié)點(diǎn)之間的左右關(guān)系 總之，由二叉樹的一種遍歷序列不能唯一確定一顆二叉樹。,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,由二叉樹的一種遍歷序列不能唯一確定一棵二叉樹 先根遍歷序列為AB,構(gòu)造二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,書上介紹的建立二叉樹的方法： 按先根和中根次序遍歷序列建立二叉樹 以標(biāo)明空子樹的先

44、根次序遍歷序列建立二叉樹 以廣義表表示建立二叉樹 建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的完全二叉樹,構(gòu)造二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,按先根和中根遍歷序列建立二叉樹,在二叉樹類BinaryTree中，增加create ()方法實(shí)現(xiàn)以先根遍歷序列prelist、中根遍歷序列inlist建立一顆二叉樹的算法，并返回這顆二叉樹的根結(jié)點(diǎn) 具體的實(shí)現(xiàn)思想就是書上（P148）的證明過(guò)程,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,先根和中根序列表示,按先根和中根遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,public BinaryTree(T prelist, T inlist) /以先根和中根序列構(gòu)

45、造二叉樹 this.root = create(prelist, inlist, 0, 0, prelist.length); ,按先根和中根遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,/以先根和中根序列創(chuàng)建一棵子樹，子樹根結(jié)點(diǎn)值是/prelistpreStart，n指定子序列長(zhǎng)度，返回所創(chuàng)建子樹的根結(jié)點(diǎn) private BinaryNode create(T prelist, T inlist, int preStart, int inStart, int n) System.out.print(prelist:); print(prelist, preStart, n); S

46、ystem.out.print(，inlist:); print(inlist, inStart, n); System.out.println(); if (n=0) return null;,按先根和中根遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,T elem=prelistpreStart; /根結(jié)點(diǎn)值 BinaryNode p=new BinaryNode(elem); /創(chuàng)建葉子結(jié)點(diǎn) int i=0; while (in ,按先根和中根遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,private void print(T table, int start,

47、int n) for (int i=0; in; i+) System.out.print(tablestart+i); ,按先根和中根遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,public static void main(String args) String prelist=A,B,D,G,C,E,F,H; String inlist=D,G,B,A,E,C,H,F; BinaryTree bitree=new BinaryTree(prelist,inlist); bitree.preOrder(); bitree.inOrder(); bitree.postOrder

48、(); ,按先根和中根遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,中根遍歷序列： CBDFEGAMLNKJOPRQIHS 后根遍歷序列： CFGEDBMNLKRQPOJISHA,思考題 由中根和后根遍歷序列 構(gòu)造二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,習(xí)題解答,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹,僅有先根遍歷不能唯一確定一顆二叉樹。但是，如果在先根遍歷中加入反映兄弟結(jié)點(diǎn)間的左右次序的信息（如以“”標(biāo)明空子樹），則可以唯一確定一顆二叉樹。,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹,二叉樹的二叉鏈

49、表實(shí)現(xiàn),6.2 二叉樹,構(gòu)造過(guò)程：設(shè)prelist表示一棵二叉樹標(biāo)明空子樹的先根序列，構(gòu)造算法如下： prelist0一定是二叉樹的根，創(chuàng)建根結(jié)點(diǎn)； prelist1一定是根的左孩子； 若prelisti不是”，則創(chuàng)建一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)元素是prelisti+1，但父母與孩子結(jié)點(diǎn)之間的鏈還未建立；否則當(dāng)前子樹為空，返回上一層結(jié)點(diǎn); 返回到當(dāng)前結(jié)點(diǎn)時(shí)，下一個(gè)元素prelisti+1是當(dāng)前結(jié)點(diǎn)的右孩子結(jié)點(diǎn)；當(dāng)一個(gè)結(jié)點(diǎn)的左右孩子鏈都已建立，則以當(dāng)前結(jié)點(diǎn)為根的一棵子樹就已建立，返回上一層結(jié)點(diǎn); 重復(fù)執(zhí)行步驟23，直到返回根結(jié)點(diǎn)，則二叉樹建立，使root指向根結(jié)點(diǎn)。,以標(biāo)明空子樹的先根次序遍歷

50、序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,在BinaryTree類中增加以下構(gòu)造方法，以標(biāo)明空子樹的先根序列建立一棵二叉樹 public BinaryTree(T prelist) /以標(biāo)明空子樹的先根序列構(gòu)造二叉樹 this.root = create(prelist); private int i=0; private BinaryNode create(T prelist) /從i開始，創(chuàng)建一棵以prelisti為根的子樹，返回根結(jié)點(diǎn)，遞歸方法,以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,/以從i開始的標(biāo)明空子樹的先根序列，創(chuàng)建一棵以pre

51、listi為根的子樹，返回根結(jié)點(diǎn)，遞歸方法 private int i=0; private BinaryNode create(T prelist) BinaryNode p = null; if (i(elem); /創(chuàng)建葉子結(jié)點(diǎn) p.left = create(prelist); /創(chuàng)建p的左子樹，遞歸調(diào)用，實(shí)際參數(shù)與形式參數(shù)相同 p.right = create(prelist); /創(chuàng)建p的右子樹，遞歸調(diào)用，實(shí)際參數(shù)與形式參數(shù)相同 return p; ,以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,String preorder2 = A,B,nul

52、l,null,C; /標(biāo)明空子樹的先根序列 BinaryTree bitree3 = new BinaryTree(preorder2); bitree3.preOrder(); bitree3.inOrder(); bitree3.postOrder();,以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,思考題 二叉樹的構(gòu)造、遍歷及插入。,以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,思考題 能否采用以標(biāo)明空子樹的中根序列或后根序列構(gòu)造一棵二叉樹？為什么？ BinaryTree(BinaryTree bitree) /深拷貝,

53、BinaryNode copy(BinaryNode p) if (p=null) return null; BinaryNode q = new BinaryNode(p.data); q.left = copy(p.left); /復(fù)制左子樹 q.right = copy(p.right); /復(fù)制右子樹 return q; （習(xí)題解答）,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,廣義表表示建立二叉樹,以廣義表形式可以表示一棵樹，但不能唯一表示一棵二叉樹，因?yàn)闊o(wú)法明確左右子樹 二叉樹的廣義表表示語(yǔ)法如下圖，其中元素表示結(jié)點(diǎn)，“”表示空子樹 從上可知，二叉樹的廣義表表示是遞歸定義的,二叉樹的二叉

54、鏈表實(shí)現(xiàn),6.2 二叉樹,廣義表表示建立二叉樹的示例如下：,廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,習(xí)-22 畫出用以下廣義表形式表示的一棵二叉樹。 /習(xí)題解答,A(B,C(D(F,G(J,),E(H(K,L),I(,M),廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,（1） 輸出二叉樹的廣義表表示 public void printGenList() private void printGenList(BinaryNode p) /（1） 廣義表表示 public void printGenList

55、() /輸出二叉樹的廣義表表示字符串 System.out.print(二叉樹的廣義表表示：); printGenList(this.root); System.out.println(); ,廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,/輸出以p結(jié)點(diǎn)為根的一棵子樹的廣義表表示字符串，先根次序遍歷，遞歸算法 private void printGenList(BinaryNode p) if (p=null) /若二叉樹空 System.out.print(); /輸出空子樹標(biāo)記 else System.out.print(p.data.toString(); /訪問(wèn)當(dāng)前結(jié)點(diǎn)

56、if (p.left!=null | p.right!=null) /非葉子結(jié)點(diǎn)，有子樹 System.out.print(); printGenList(p.left); /輸出p的左子樹，遞歸調(diào)用 System.out.print(,); printGenList(p.right); /輸出p的右子樹，遞歸調(diào)用 System.out.print(); ,廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,按廣義表次序遍歷序列建立二叉樹： 【例6.2】 二叉樹的廣義表表示。 具體的實(shí)現(xiàn)思想就是上圖 private static int i=0; public static Binar

57、yTree createByGenList(String genlist) private static BinaryNode create(String genlist),廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,public class BinaryTree_genlist private static int i=0; public static BinaryTree createByGenList(String glist) /以廣義表表示構(gòu)造二叉樹 BinaryTree bitree = new BinaryTree(); i=0; if (glist.length

58、()0) bitree.root = create(glist); /創(chuàng)建子樹，子樹根值是glist0 return bitree; ,廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,/以廣義表表示創(chuàng)建一棵子樹，子樹根值是glisti，返回根結(jié)點(diǎn)，遞歸方法 private static BinaryNode create(String glist) BinaryNode p=null; char ch=glist.charAt(i); if (ch=A /空串返回null ,廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,public class BinaryTree_

59、例6_2 public static void main(String args) String genlist;/ = AA(BB(DD(,G),),C(E,F(H,); /圖6.18所示二叉樹的廣義表表示 / genlist = ;/A(B,C); genlist = A(B,C(D(F,G(J,),E(H(K,L),I(,M); BinaryTree bitree = BinaryTrees.createByGenList(genlist); bitree.printGenList(); /輸出二叉樹的廣義表表示字符串 /習(xí)題6 / System.out.println(是否完全二叉樹？

60、 +bitree.isCompleteBinaryTree(); ,廣義表表示建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,以完全二叉樹的層次遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，對(duì)序號(hào)為i（0in）的結(jié)點(diǎn)，有： 若i=0，則i為根結(jié)點(diǎn)，無(wú)父母結(jié)點(diǎn)；若i0，則i的父母結(jié)點(diǎn)序號(hào)為|(i-1)/2|。 若2i+1n，則i的左孩子結(jié)點(diǎn)序號(hào)為2i+1；否則i無(wú)左孩子。 若2i+2n，則i的右孩子結(jié)點(diǎn)序號(hào)為2i+2；否則i無(wú)右孩子。,以完全二叉樹的層次遍歷序列建立二叉樹,二叉樹的二叉鏈表實(shí)現(xiàn),6.2 二叉樹,/二叉鏈表表示的完全二叉樹類，繼承