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

數(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.4Huffman樹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)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時(shí)，可用樹來描述其執(zhí)行過程，等等。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)沒有前驅(qū)結(jié)點(diǎn)。6.1樹及其抽象數(shù)據(jù)類型樹結(jié)構(gòu)樹(Tree)是由n(n>=0)個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹稱為空樹，n>0的樹由以下兩個(gè)條件約定構(gòu)成：1.有且僅有一個(gè)特殊的稱為根(Root)的結(jié)點(diǎn)，它只有后繼結(jié)點(diǎn)，沒有前驅(qū)結(jié)點(diǎn)；2.其余的結(jié)點(diǎn)可分為m(n>m>=0)個(gè)互不相交的子集T0、T1、T2…、Tm-1，其中每個(gè)子集又是一棵樹，并稱其為子樹(Subtree)。6.1樹及其抽象數(shù)據(jù)類型樹定義比方上圖，左邊為只有一個(gè)結(jié)點(diǎn)的樹，A為根。右邊是一個(gè)有8個(gè)結(jié)點(diǎn)的樹，A為根，其余可以分為三個(gè)不相交的子集，也就是可以分為三個(gè)子樹。A6.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)，它沒有雙親結(jié)點(diǎn)6.1樹及其抽象數(shù)據(jù)類型根本術(shù)語結(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)過的所有結(jié)點(diǎn)根是樹中所有結(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ù)語葉子結(jié)點(diǎn)〔終端結(jié)點(diǎn)〕〔leaf〕：沒有孩子結(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ù)語結(jié)點(diǎn)n的度〔degreeofnode〕：n的孩子結(jié)點(diǎn)的數(shù)量樹的度〔degreeofatree〕：樹中所有結(jié)點(diǎn)的最大度數(shù)6.1樹及其抽象數(shù)據(jù)類型根本術(shù)語結(jié)點(diǎn)n的層次〔level〕：結(jié)點(diǎn)n所處的樹中的層次位置?？梢约僭O(shè)根的層次是0或1，本書中所有都假設(shè)根的層次為1，其他結(jié)點(diǎn)的層次是其父母結(jié)點(diǎn)的層次加1樹的高度〔heigh〕或深度〔depth〕：樹中結(jié)點(diǎn)的最大層次數(shù)6.1樹及其抽象數(shù)據(jù)類型根本術(shù)語邊〔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，Xi＋1〕都是樹中的邊，那么該序列稱為X0到Xk-1的一條路徑路徑長度〔length〕：路徑中涉及到邊的數(shù)量6.1樹及其抽象數(shù)據(jù)類型根本術(shù)語假設(shè)把樹中每個(gè)結(jié)點(diǎn)的各子樹看成從左到右有次序的〔即不能互換〕，那么稱該樹為有序樹〔OrderedTree〕；否那么稱為無序樹〔UnorderedTree〕森林〔forest〕：m棵互不相交的樹的集合〔如：{T0,T1,T2…Tm-1}〕，但可能為空6.1樹及其抽象數(shù)據(jù)類型根本術(shù)語1．樹形結(jié)構(gòu)表示法〔圖示法〕具體參見以下圖6.1樹及其抽象數(shù)據(jù)類型樹的表示2.橫向凹入表示法具體參見以下圖6.1樹及其抽象數(shù)據(jù)類型樹的表示3.嵌套集合表示法〔文氏圖表示法〕具體參見以下圖6.1樹及其抽象數(shù)據(jù)類型樹的表示4.廣義表表示法對圖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ù)類型樹的表示ADTTree<T>//樹抽象數(shù)據(jù)類型{booleanisEmpty()//判空intlevel(Tkey)//層次intsize()//結(jié)點(diǎn)數(shù)intheight()//高度voidpreorder()//先根次序遍歷voidpostorder()//后根次序遍歷voidlevelorder()//層次遍歷TreeNode<T>insert(Tx)//插入元素x作為根TreeNode<T>insert(TreeNode<T>p,Tx,inti)//插入x作為p結(jié)點(diǎn)的第i〔≥0〕個(gè)孩子voidremove(TreeNode<T>p,inti)//刪除子樹voidclear()//刪除所有結(jié)點(diǎn)TreeNode<T>search(Tkey)//查找booleancontains(Tkey)//包含Tremove(Tkey)//刪除子樹}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)〕。左孩子結(jié)點(diǎn)〔leftchild〕：二叉樹中結(jié)點(diǎn)的左孩子右孩子結(jié)點(diǎn)〔rightchild〕：二叉樹中結(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ū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差異。以下圖列出二差樹的5種根本形態(tài)，圖(c)和圖〔d〕是不同的兩棵二叉樹。【思考題6-1】①二叉樹與樹的差異二叉樹是不是度為2的樹？二叉樹是不是度為2的有序樹？為什么？2個(gè)結(jié)點(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)。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1層時(shí)，只有一個(gè)根結(jié)點(diǎn)：

2i-1=20=1；假設(shè)對所有的j，1≤j

i，命題成立；即第j層上至多有2j-1個(gè)結(jié)點(diǎn)。因二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，那么第i層的結(jié)點(diǎn)數(shù)=2(i-1)-12=2i-1。證明j=i時(shí)命題成立第i-1層的結(jié)點(diǎn)數(shù)123457686.2二叉樹二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)〔k≥1〕。證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為20+21++2k-1=1*〔1-2k〕/1-2=2k-1性質(zhì)3：對任何一棵二叉樹，假設(shè)它含有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=n1+2n2由此，n0=n2+1。1234566.2二叉樹二叉樹的性質(zhì)滿二叉樹〔fullbinarytree〕：一棵高度為h且有2h-1〔h>=0〕個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。以下說法是否正確：二叉樹中所有非葉結(jié)點(diǎn)的度數(shù)都為2的二叉樹是滿二叉樹〔錯(cuò)〕；一個(gè)高度為h的滿二叉樹中，只在h層有葉結(jié)點(diǎn)，而且每一個(gè)非葉子結(jié)點(diǎn)都是滿的，是滿二叉樹〔對〕。6.2二叉樹二叉樹的性質(zhì)完全二叉樹〔completebinarytree〕：如果深度為h、由n個(gè)結(jié)點(diǎn)的二叉樹中每個(gè)結(jié)點(diǎn)能夠與深度為h的順序編號(hào)的滿二叉樹從0到n-1標(biāo)號(hào)的結(jié)點(diǎn)一一對應(yīng)，那么稱這樣的二叉樹為完全二叉樹?！矟M二叉樹是完全二叉樹的特例〕完全二叉樹的特點(diǎn)是：在h層二叉樹中，所有的葉結(jié)點(diǎn)都出現(xiàn)在第h層或h－1層。對任一結(jié)點(diǎn)，如果其右子樹的最大層次為h，那么其左子樹的最大層次為h或h＋1。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兩邊取對數(shù)得：k-1≤log2n<kk≤log2n+1<k+1因?yàn)閗只能是整數(shù)，因此，k=log2n+1深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)〔k≥1〕。123114589126710特點(diǎn)32.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章6.2二叉樹二叉樹的性質(zhì)性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，對序號(hào)為i〔0≤i＜n〕的結(jié)點(diǎn)，有：假設(shè)i=0，那么i為根結(jié)點(diǎn)，無父母結(jié)點(diǎn)； 假設(shè)i>0，那么i的父母結(jié)點(diǎn)序號(hào)為(i-1)/2假設(shè)2i+1＜n，那么i的左孩子結(jié)點(diǎn)在2i+1；否那么i無左孩子。假設(shè)2i+2＜n，那么i的右孩子結(jié)點(diǎn)在2i+2；否那么i無右孩子。33.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章6.2二叉樹二叉樹的遍歷規(guī)那么線形表的遍歷過程：從首元素開始，訪問〔某個(gè)操作〕每一個(gè)元素，直到尾元素。樹性結(jié)構(gòu)如何遍歷？？？回憶線形數(shù)據(jù)結(jié)構(gòu)的遍歷34.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章6.2二叉樹二叉樹的遍歷規(guī)那么二叉樹的遍歷指的是沿某條搜索路徑訪問二叉樹，對二叉樹中的每個(gè)結(jié)點(diǎn)訪問一次且僅一次。這里的“訪問〞實(shí)際上指的是對結(jié)點(diǎn)進(jìn)行某種操作。(以下“訪問〞特指打印該結(jié)點(diǎn)信息)定義所有遍歷序列有6種：ABC，BAC，BCA，//先左孩子CBA，CAB，ACB。//先右孩子約定遍歷子樹的次序是先左子樹后右子樹6.2二叉樹二叉樹的遍歷規(guī)那么孩子優(yōu)先的遍歷規(guī)那么先根次序：訪問根結(jié)點(diǎn)，先根遍歷左子樹，先根遍歷右子樹。中根次序：中根遍歷左子樹，訪問根結(jié)點(diǎn)，中根遍歷右子樹。后根次序：后根遍歷左子樹，后根遍歷右子樹，訪問根結(jié)點(diǎn)。先根遍歷序列：ABDGCEFH中根遍歷序列：DGBAECHF后根遍歷序列：GDBEHFCA孩子優(yōu)先的遍歷規(guī)那么6.2二叉樹二叉樹的遍歷規(guī)那么層次遍歷序列：ABCDEFGH兄弟優(yōu)先的遍歷規(guī)那么6.2二叉樹二叉樹的遍歷規(guī)那么給出二叉樹的先根、中根、后根和層次遍歷序列。習(xí)題6.2二叉樹二叉樹的遍歷規(guī)那么ADTBinaryTree<T>{booleanisEmpty()//判空

intsize()//結(jié)點(diǎn)數(shù)

intheight()//高度

voidpreOrder()//先根次序遍歷

voidinOrder()//中根次序遍歷

voidpostOrder()//后根次序遍歷

voidlevelOrder()//按層次遍歷BinaryNode<T>insert(Tx)//插入根

BinaryNode<T>insert(BinaryNode<T>p,Tx, booleanleftChild)//插入孩子

voidremove(BinaryNode<T>parent,boolean leftChild)//刪除子樹

voidclear()//刪除所有結(jié)點(diǎn)

BinaryNode<T>search(Tkey)//查找

booleancontains(Tkey)//包含

intlevel(Tkey)//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)順序存儲(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)的順序來表達(dá)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è)大小為2h–1的數(shù)組然后用此數(shù)組自上而下、自左而右地存儲(chǔ)與此樹對應(yīng)的完全二叉樹上的結(jié)點(diǎn)二叉樹的順序存儲(chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹順序存儲(chǔ)的原那么：不管給定的二叉樹是不是完全二叉樹，都看作完全二叉樹，即按完全二叉樹的層次次序〔從上到下，從左到右〕把各結(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)46.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章二叉樹順序存儲(chǔ)結(jié)構(gòu)中其他結(jié)點(diǎn)確實(shí)定〔性質(zhì)5〕：假設(shè)給定結(jié)點(diǎn)的地址為I，那么：〔1〕假設(shè)I＝0，那么該結(jié)點(diǎn)是為根結(jié)點(diǎn)，無父親。〔2〕假設(shè)I≠0，那么該結(jié)點(diǎn)的父親結(jié)點(diǎn)地址為I-1／2的整數(shù)局部?！?〕假設(shè)2×I+1＜n，那么該結(jié)點(diǎn)的左兒子結(jié)點(diǎn)地址為2×I+1，否那么該結(jié)點(diǎn)無左兒子。〔4〕假設(shè)2×I+2＜n，那么該結(jié)點(diǎn)的右兒子結(jié)點(diǎn)地址為2×I+2，否那么該結(jié)點(diǎn)無右兒子。〔5〕假設(shè)I為奇數(shù)〔除根結(jié)點(diǎn)〕，那么該結(jié)點(diǎn)的右兄弟為I＋1?！?〕假設(shè)I為偶數(shù)〔除根結(jié)點(diǎn)〕，那么該結(jié)點(diǎn)的左兄弟為I－1。二叉樹的順序存儲(chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)對于一棵二叉樹,假設(shè)采用順序存貯時(shí),當(dāng)它為完全二叉樹時(shí),比較方便,假設(shè)為非完全二叉樹,將會(huì)浪費(fèi)大量存貯存貯單元。最壞的非完全二叉樹是全部只有右分支,設(shè)高度為K,那么需占用2K-1個(gè)存貯單元,而實(shí)際只有k個(gè)元素,實(shí)際只需k個(gè)存儲(chǔ)單元。因此，對于非完全二叉樹，宜采用下面的鏈?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ù)域、左、右指針域。有時(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)可描述為：

1eftdataright

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)50.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章如何采用以上結(jié)點(diǎn)結(jié)構(gòu)表示二叉樹？？？采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示二叉樹時(shí)，需要一個(gè)根指針〔root〕指向根結(jié)點(diǎn)假設(shè)二叉樹為空，那么根結(jié)點(diǎn)為NULL假設(shè)結(jié)點(diǎn)的某個(gè)兒子不存在，那么相應(yīng)的指針為空二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)51.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章對于上圖所示二叉樹,用二叉鏈表形式描述見以下圖：二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)52.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)53.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章考慮：n個(gè)結(jié)點(diǎn)的二叉樹中，有多少個(gè)指針域，其中多少個(gè)指向左、右孩子，多少個(gè)為空？？？假設(shè)一棵二叉樹有n個(gè)結(jié)點(diǎn),采用二叉鏈表作存貯結(jié)構(gòu)時(shí),共有2n個(gè)指針域,其中只有n-1個(gè)指針指向左右孩子,其余n+1個(gè)指針為空,沒有發(fā)揮作用,被白白浪費(fèi)掉了。二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)54.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章在二叉鏈表結(jié)點(diǎn)的根底上，三叉鏈表增加一條鏈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)55.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6.2二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)56.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章二叉樹的二叉鏈表結(jié)點(diǎn)類publicclassBinaryNode<T>{Tdata;//數(shù)據(jù)元素BinaryNode<T>left,right;//左、右孩子

publicBinaryNode(Tdata,BinaryNode<T>left,BinaryNode<T>right)

//構(gòu)造結(jié)點(diǎn)publicBinaryNode(Tdata)//構(gòu)造葉子publicStringtoString()//描述字符串publicbooleanisLeaf()//判結(jié)點(diǎn)}6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)57.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章//1.二叉鏈表結(jié)點(diǎn)類publicclassBinaryNode<T>//二叉樹的二叉鏈表結(jié)點(diǎn)類，T指定結(jié)點(diǎn)的元素類型{publicTdata;//數(shù)據(jù)域，存儲(chǔ)數(shù)據(jù)元素

publicBinaryNode<T>left,right;//鏈域，分別指向左、右孩子結(jié)點(diǎn)

//構(gòu)造結(jié)點(diǎn)，data指定元素，left、right分別指向左孩子和右孩子結(jié)點(diǎn)

publicBinaryNode(Tdata,BinaryNode<T>left,BinaryNode<T>right){this.data=data;this.left=left;this.right=right;}6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)58.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章二叉樹的結(jié)點(diǎn)類publicBinaryNode(Tdata)//構(gòu)造元素為data的葉子結(jié)點(diǎn)

{this(data,null,null);}publicStringtoString()//返回結(jié)點(diǎn)數(shù)據(jù)域的描述字符串

{returnthis.data.toString();}publicbooleanisLeaf()//判斷是否葉子結(jié)點(diǎn)

{returnthis.left==null&&this.right==null;}}6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)59.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章二叉樹類publicclassBinaryTree<T>{BinaryNode<T>root;//根結(jié)點(diǎn)

publicBinaryTree()//構(gòu)造空樹publicbooleanisEmpty()//判空}6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)60.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章二叉樹類publicclassBinaryTree<T>//二叉樹類，二叉鏈表存儲(chǔ)，T指定結(jié)點(diǎn)的元素類型{publicBinaryNode<T>root;//根結(jié)點(diǎn)，二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)

publicBinaryTree()//構(gòu)造空二叉樹

{this.root=null;}publicbooleanisEmpty()//判斷是否空二叉樹

{returnthis.root==null;}6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)61.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章二叉樹插入結(jié)點(diǎn)BinaryNode<T>insert(Tx)//插入根結(jié)點(diǎn)BinaryNode<T>insert(BinaryNode<T>parent,Tx,booleanleftChild)//插入x為parent結(jié)點(diǎn)的左/右孩子6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)publicBinaryNode<T>insert(Tx)//插入x作為根結(jié)點(diǎn)，原根結(jié)點(diǎn)作為x的左孩子；返回插入結(jié)點(diǎn){returnthis.root=newBinaryNode<T>(x,this.root,null);}//插入x為parent結(jié)點(diǎn)的左/右孩子，leftChild指定孩子，取值為true〔左〕、false〔右〕；//parent的原左/右孩子成為x結(jié)點(diǎn)的左/右孩子；返回插入結(jié)點(diǎn)。//假設(shè)x==null，不插入，返回null。假設(shè)parent==null，Java拋出空對象異常。publicBinaryNode<T>insert(BinaryNode<T>parent,Tx,booleanleftChild){if(x==null)returnnull;if(leftChild)//插入x為parent結(jié)點(diǎn)的左/右孩子，返回插入結(jié)點(diǎn)returnparent.left=newBinaryNode<T>(x,parent.left,null);returnparent.right=newBinaryNode<T>(x,null,parent.right);}6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)63.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章//刪除parent結(jié)點(diǎn)的左/右子樹publicvoidremove(BinaryNode<T>parent,booleanleftChild)publicvoidclear()//刪除所有結(jié)點(diǎn)6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)//二叉樹刪除子樹//刪除parent結(jié)點(diǎn)的左或右子樹，leftChild指定子樹，取值為true〔左〕、false〔右〕//Java自動(dòng)收回被刪除子樹占用的存儲(chǔ)空間。publicvoidremove(BinaryNode<T>parent,booleanleftChild){if(leftChild)parent.left=null;//假設(shè)parent==null，Java拋出空對象異常elseparent.right=null;}publicvoidclear()//刪除二叉樹的所有結(jié)點(diǎn){this.root=null;}6.2二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)先根遍歷1．按先根次序遍歷二叉樹的遞歸算法，將如下算法添加到二叉樹類BinaryTree<T>中假設(shè)二叉樹為空，返回；否那么，繼續(xù)。從根結(jié)點(diǎn)開始，訪問當(dāng)前結(jié)點(diǎn)。按先根次序遍歷當(dāng)前結(jié)點(diǎn)的左子樹。按先根次序遍歷當(dāng)前結(jié)點(diǎn)的右子樹。privatevoidpreorder(BinaryNode<T>p)//先根次序遍歷以p結(jié)點(diǎn)為根的子樹，遞歸方法{if(p!=null)//假設(shè)二叉樹不空{(diào)System.out.print(p.data.toString()+"");//先訪問當(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ù)，通過不同的實(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è)重載方法實(shí)現(xiàn)，如preOrder()和preOrder(p)。先根遍歷二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹publicvoidpreorder()//輸出先根次序遍歷序列

{//System.out.print("先根次序遍歷二叉樹：");preorder(this.root);//調(diào)用先根次序遍歷二叉樹的遞歸方法

System.out.println();}先根遍歷二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹publicStringtoString()//返回先根次序遍歷二叉樹所有結(jié)點(diǎn)的描述字符串

{returntoString(this.root);}privateStringtoString(BinaryNode<T>p)//返回先根次序遍歷以p為根的子樹描述字符串，遞歸方法

{if(p==null)return"∧";//輸出空子樹標(biāo)記

returnp.data.toString()+""+toString(p.left)+toString(p.right);}先根遍歷二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹將如下算法添加到二叉樹類BinaryTree<T>中

publicvoidinorder()//輸出中根次序遍歷序列

{//System.out.print("中根次序遍歷二叉樹：");inorder(this.root);System.out.println();}privatevoidinorder(BinaryNode<T>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<T>中

publicvoidpostorder()//輸出后根次序遍歷序列

{//System.out.print("后根次序遍歷二叉樹：");postorder(this.root);System.out.println();}privatevoidpostorder(BinaryNode<T>p)//后根次序遍歷以p結(jié)點(diǎn)為根的子樹，遞歸方法

{if(p!=null){postorder(p.left);postorder(p.right);System.out.print(p.data.toString()+"");//后訪問當(dāng)前結(jié)點(diǎn)元素

}}后根遍歷二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹僅知二叉樹的先序序列〞abcdefg〞不能唯一確定一棵二叉樹，如果同時(shí)二叉樹的中序序列〞cbdaegf〞，那么會(huì)如何？思考題

由二叉樹的先序和中序序列建樹二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根確定原那么：★由先序序列確定二叉樹的根結(jié)點(diǎn)，★由中序序列確定二叉樹的左右子樹序列。二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹72.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章abcdefgcbdaegfaabbccddeeffggabcdefg^^^^^^^^先序序列中序序列★由二叉樹的先序和中序序序列確定二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹73.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章一個(gè)二叉樹的先根遍歷序列和中根遍歷序列，能否畫出這個(gè)二叉樹?！部梢浴骋粋€(gè)二叉樹的后根遍歷序列和中根遍歷序列，能否畫出這個(gè)二叉樹?！部梢浴骋粋€(gè)二叉樹的先根遍歷序列和后根遍歷序列，能否畫出這個(gè)二叉樹?！膊豢梢浴诚雀懈蟾鵄BDEGHCFIDGHEBIFCAABDEGHCFIDBGEHAFICDBGEHAFICDGHEBIFCA二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹思考題74.數(shù)據(jù)結(jié)構(gòu)〔Java版〕〔第4版〕?第6章基于遍歷的操作求結(jié)點(diǎn)個(gè)數(shù)求高度查找獲得父母結(jié)點(diǎn)二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹求結(jié)點(diǎn)個(gè)數(shù)publicintsize()//返回二叉樹的結(jié)點(diǎn)數(shù)

{returnsize(root);}publicintsize(BinaryNode<T>p)//返回以p結(jié)點(diǎn)為根的子樹的結(jié)點(diǎn)數(shù)

{if(p==null)return0;return1+size(p.left)+size(p.right);}基于遍歷的操作二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹求高度：必須采用后跟次序遍歷算法，只有先分別計(jì)算出左、右子樹高度的情況下，才能計(jì)算當(dāng)前子樹高度publicintheight()//返回二叉樹的高度

{returnheight(root);}publicintheight(BinaryNode<T>p)//返回以p結(jié)點(diǎn)為根的子樹高度，后根次序遍歷

{if(p==null)return0;intlh=height(p.left);//返回左子樹的高度

intrh=height(p.right);//返回右子樹的高度

return(lh>=rh)?lh+1:rh+1;//當(dāng)前子樹高度為較高子樹的高度加1}基于遍歷的操作二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹查找publicTsearch(Tkey)//查找并返回首次出現(xiàn)的關(guān)鍵字為key元素{returnsearchNode(root,key).data;}publicBinaryNode<T>searchNode(Tkey)//查找并返回首次出現(xiàn)的關(guān)鍵字為key元素結(jié)點(diǎn){returnsearchNode(root,key);}//在以p為根的子樹中查找并返回首次出現(xiàn)的關(guān)鍵字為key元素結(jié)點(diǎn)，假設(shè)未找到返回null，先根次序遍歷publicBinaryNode<T>searchNode(BinaryNode<T>p,Tkey){if(p==null||key==null)returnnull;if(p.data.equals(key))returnp;//查找成功，返回找到結(jié)點(diǎn)BinaryNode<T>find=searchNode(p.left,key);//在左子樹中查找，遞歸調(diào)用if(find==null)//假設(shè)在左子樹中未找到find=searchNode(p.right,key);//那么繼續(xù)在右子樹中查找，遞歸調(diào)用returnfind;//返回查找結(jié)果}基于遍歷的操作二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹獲得父母結(jié)點(diǎn)//返回node結(jié)點(diǎn)的父母結(jié)點(diǎn)，假設(shè)空樹、未找到或node為根，那么返回nullpublicBinaryNode<T>getParent(BinaryNode<T>node){if(root==null||node==null||node==root)returnnull;returngetParent(root,node);}//在以p為根的子樹中查找并返回node結(jié)點(diǎn)的父母結(jié)點(diǎn)publicBinaryNode<T>getParent(BinaryNode<T>p,BinaryNode<T>node){if(p==null)returnnull;if(p.left==node||p.right==node)returnp;BinaryNode<T>find=getParent(p.left,node);if(find==null)find=getParent(p.right,node);returnfind;}基于遍歷的操作二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹//返回以p結(jié)點(diǎn)為根子樹的結(jié)點(diǎn)數(shù)intsize(BinaryNode<T>p){staticintn=0;if(p!=null){n++;size(p.left);size(p.right);}}【習(xí)題解答】存在錯(cuò)誤：Java語言方法體中的局部變量不能聲明為static。如果用局部變量n計(jì)數(shù)，每次n=0，再n++，n=1，無法實(shí)現(xiàn)計(jì)數(shù)，并且結(jié)果無法返回給調(diào)用者。思考題遞歸方法參數(shù)與返回值問題討論。有什么錯(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)系確實(shí)定：先根遍歷和后跟遍歷反映雙親與孩子結(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)明空子樹的先根次序遍歷序列建立二叉樹以廣義表表示建立二叉樹建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的完全二叉樹構(gòu)造二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹按先根和中根遍歷序列建立二叉樹在二叉樹類BinaryTree<T>中，增加create()方法實(shí)現(xiàn)以先根遍歷序列prelist、中根遍歷序列inlist建立一顆二叉樹的算法，并返回這顆二叉樹的根結(jié)點(diǎn)具體的實(shí)現(xiàn)思想就是書上〔P148〕的證明過程二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹先根和中根序列表示按先根和中根遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹

publicBinaryTree(T[]prelist,T[]inlist)//以先根和中根序列構(gòu)造二叉樹

{

this.root=create(prelist,inlist,0,0,prelist.length);

}按先根和中根遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹//以先根和中根序列創(chuàng)立一棵子樹，子樹根結(jié)點(diǎn)值是//prelist[preStart]，n指定子序列長度，返回所創(chuàng)立子樹的根結(jié)點(diǎn)privateBinaryNode<T>create(T[]prelist,T[]inlist,intpreStart,intinStart,intn){System.out.print("prelist:");print(prelist,preStart,n);System.out.print("，inlist:");print(inlist,inStart,n);System.out.println();

if(n<=0)returnnull;按先根和中根遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹Telem=prelist[preStart];//根結(jié)點(diǎn)值BinaryNode<T>p=newBinaryNode<T>(elem);//創(chuàng)立葉子結(jié)點(diǎn)inti=0;while(i<n&&!elem.equals(inlist[inStart+i]))//在中根序列中查找根值所在位置i++;p.left=create(prelist,inlist,preStart+1,inStart,i);//創(chuàng)立左子樹p.right=create(prelist,inlist,preStart+i+1,inStart+i+1,n-1-i);//創(chuàng)立右子樹returnp;}按先根和中根遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹privatevoidprint(T[]table,intstart,intn)

{

for(inti=0;i<n;i++)System.out.print(table[start+i]);

}按先根和中根遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹publicstaticvoidmain(Stringargs[]){String[]prelist={"A","B","D","G","C","E","F","H"};String[]inlist={"D","G","B","A","E","C","H","F"};BinaryTree<String>bitree=newBinaryTree<String>(prelist,inlist);bitree.preOrder();bitree.inOrder();bitree.postOrder();}按先根和中根遍歷序列建立二叉樹二叉樹的二叉鏈表實(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)明空子樹的先根次序遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹構(gòu)造過程：設(shè)prelist表示一棵二叉樹標(biāo)明空子樹的先根序列，構(gòu)造算法如下：prelist[0]一定是二叉樹的根，創(chuàng)立根結(jié)點(diǎn)；prelist[1]一定是根的左孩子；假設(shè)prelist[i]不是〞^〞，那么創(chuàng)立一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)元素是prelist[i+1]，但父母與孩子結(jié)點(diǎn)之間的鏈還未建立；否那么當(dāng)前子樹為空，返回上一層結(jié)點(diǎn);返回到當(dāng)前結(jié)點(diǎn)時(shí)，下一個(gè)元素prelist[i+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í)行步驟2~3，直到返回根結(jié)點(diǎn)，那么二叉樹建立，使root指向根結(jié)點(diǎn)。以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹在BinaryTree<T>類中增加以下構(gòu)造方法，以標(biāo)明空子樹的先根序列建立一棵二叉樹publicBinaryTree(T[]prelist)//以標(biāo)明空子樹的先根序列構(gòu)造二叉樹{this.root=create(prelist);}privateinti=0;privateBinaryNode<T>create(T[]prelist)//從i開始，創(chuàng)立一棵以prelist[i]為根的子樹，返回根結(jié)點(diǎn)，遞歸方法

以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹//以從i開始的標(biāo)明空子樹的先根序列，創(chuàng)立一棵以prelist[i]為根的子樹，返回根結(jié)點(diǎn)，遞歸方法privateinti=0;privateBinaryNode<T>create(T[]prelist){BinaryNode<T>p=null;if(i<prelist.length){Telem=prelist[i];i++;if(elem!=null)//不能elem!="∧"，因?yàn)門不一定是String{p=newBinaryNode<T>(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ù)相同}}returnp;}以標(biāo)明空子樹的先根次序遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹String[]preorder2={"A","B",null,null,"C"};//標(biāo)明空子樹的先根序列

BinaryTree<String>bitree3=newBinaryTree<String>(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<T>bitree) //深拷貝BinaryNode<T>copy(BinaryNode<T>p){if(p==null)returnnull;BinaryNode<T>q=newBinaryNode<T>(p.data);q.left=copy(p.left);//復(fù)制左子樹q.right=copy(p.right);//復(fù)制右子樹returnq;}〔習(xí)題解答〕二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹廣義表表示建立二叉樹以廣義表形式可以表示一棵樹，但不能唯一表示一棵二叉樹，因?yàn)闊o法明確左右子樹二叉樹的廣義表表示語法如以下圖，其中元素表示結(jié)點(diǎn)，“^〞表示空子樹從上可知，二叉樹的廣義表表示是遞歸定義的

二叉樹的二叉鏈表實(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〕輸出二叉樹的廣義表表示publicvoidprintGenList()privatevoidprintGenList(BinaryNode<T>p)//〔1〕廣義表表示publicvoidprintGenList()//輸出二叉樹的廣義表表示字符串{System.out.print("二叉樹的廣義表表示：");printGenList(this.root);System.out.println();}

廣義表表示建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹//輸出以p結(jié)點(diǎn)為根的一棵子樹的廣義表表示字符串，先根次序遍歷，遞歸算法privatevoidprintGenList(BinaryNode<T>p){if(p==null)//假設(shè)二叉樹空System.out.print("∧");//輸出空子樹標(biāo)記else{System.out.print(p.data.toString());//訪問當(dāng)前結(jié)點(diǎn)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)思想就是上圖privatestaticinti=0;publicstaticBinaryTree<String>createByGenList(Stringgenlist)privatestaticBinaryNode<String>create(Stringgenlist)廣義表表示建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹publicclassBinaryTree_genlist{privatestaticinti=0;publicstaticBinaryTree<String>createByGenList(Stringglist)//以廣義表表示構(gòu)造二叉樹{BinaryTree<String>bitree=newBinaryTree<String>();i=0;if(glist.length()>0)bitree.root=create(glist);//創(chuàng)立子樹，子樹根值是glist[0]returnbitree;}廣義表表示建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹//以廣義表表示創(chuàng)立一棵子樹，子樹根值是glist[i]，返回根結(jié)點(diǎn)，遞歸方法privatestaticBinaryNode<String>create(Stringglist){BinaryNode<String>p=null;charch=glist.charAt(i);if(ch>='A'&&ch<='Z')//大寫字母{p=newBinaryNode<String>(ch+"");//創(chuàng)立葉子結(jié)點(diǎn)i++;if(glist.charAt(i)=='('){i++;//跳過'('p.left=create(glist);//創(chuàng)立左子樹，遞歸調(diào)用i++;//跳過','p.right=create(glist);//創(chuàng)立右子樹，遞歸調(diào)用i++;//跳過')'}}if(ch=='^')i++;//跳過'^'returnp;//空串返回null}廣義表表示建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹publicclassBinaryTree_例6_2{publicstaticvoidmain(Stringargs[]){Stringgenlist;//="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<String>bitree=BinaryTrees.createByGenList(genlist);bitree.printGenList();//輸出二叉樹的廣義表表示字符串

//習(xí)題6//System.out.println("是否完全二叉樹？"+bitree.isCompleteBinaryTree());}}廣義表表示建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹以完全二叉樹的層次遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，對序號(hào)為i〔0≤i＜n〕的結(jié)點(diǎn)，有：假設(shè)i=0，那么i為根結(jié)點(diǎn)，無父母結(jié)點(diǎn)；假設(shè)i>0，那么i的父母結(jié)點(diǎn)序號(hào)為|(i-1)/2|。假設(shè)2i+1＜n，那么i的左孩子結(jié)點(diǎn)序號(hào)為2i+1；否那么i無左孩子。假設(shè)2i+2＜n，那么i的右孩子結(jié)點(diǎn)序號(hào)為2i+2；否那么i無右孩子。以完全二叉樹的層次遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹/二叉鏈表表示的完全二叉樹類，繼承二叉樹類publicclassCompleteBinaryTree<T>extendsBinaryTree<T>{publicCompleteBinaryTree()//構(gòu)造空二叉樹{super();}//以完全二叉樹的層次序列構(gòu)造完全二叉樹，levellist指定層次序列publicCompleteBinaryTree(T[]levellist){this.root=create(levellist,0);}//創(chuàng)立以levellist[i]為根的一棵子完全二叉樹，返回所建子樹的根結(jié)點(diǎn)privateBinaryNode<T>create(T[]levellist,inti){BinaryNode<T>p=null;if(i<levellist.length){p=newBinaryNode<T>(levellist[i]);//創(chuàng)立葉子結(jié)點(diǎn)p.left=create(levellist,2*i+1);//創(chuàng)立p的左子樹p.right=create(levellist,2*i+2);//創(chuàng)立p的右子樹}returnp;}以完全二叉樹的層次遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹

publicstaticvoidmain(Stringargs[])

{

//圖6.10所示完全二叉樹的層次遍歷序列String[]levellist={"A","B","C","D","E","F","G","H"};CompleteBinaryTree<String>cbitree=newCompleteBinaryTree<String>(levellist);cbitree.preOrder();cbitree.inOrder();cbitree.postOrder();

//習(xí)題6System.out.println("是否完全二叉樹？"+cbitree.isCompleteBinaryTree());

}}以完全二叉樹的層次遍歷序列建立二叉樹二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹

二叉樹遍歷非遞歸算法--中根遍歷進(jìn)行中根遍歷時(shí)，當(dāng)前結(jié)點(diǎn)的左子樹被訪問完后，沒有方法到達(dá)當(dāng)前結(jié)點(diǎn)及右子樹，所以在進(jìn)行當(dāng)前結(jié)點(diǎn)的左子樹的遍歷前，需要用堆棧保存當(dāng)前結(jié)點(diǎn)。進(jìn)行中根遍歷時(shí)，當(dāng)前結(jié)點(diǎn)是棧頂元素時(shí)，在堆棧中存儲(chǔ)越深的元素，就是當(dāng)前結(jié)點(diǎn)的越遠(yuǎn)的祖先結(jié)點(diǎn)，越需要最后訪問。也就是說，在從根到葉子結(jié)點(diǎn)的一條路徑上，所經(jīng)過結(jié)點(diǎn)的次序與返回結(jié)點(diǎn)的次序相反。二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹第一個(gè)結(jié)點(diǎn)：由于中序遍歷首先考慮的元素是根結(jié)點(diǎn)的最左子孫結(jié)點(diǎn)，所以第一個(gè)結(jié)點(diǎn)要從根結(jié)點(diǎn)開始，一直到最左邊的子孫結(jié)點(diǎn)為止的所有結(jié)點(diǎn)都?jí)喝攵褩?/p>

二叉樹遍歷非遞歸算法--中根遍歷二叉樹的二叉鏈表實(shí)現(xiàn)6.2二叉樹下一個(gè)結(jié)點(diǎn)：先彈出當(dāng)前結(jié)點(diǎn)然后找遍歷過程中的下一個(gè)元素，有兩種情況：如果當(dāng)前的結(jié)點(diǎn)有右子樹，那么此結(jié)點(diǎn)的右子樹都未被訪問。這時(shí)