第5章+樹與二叉樹

1、.,第五章 樹與二叉樹,教學內容,5.2 二叉樹的基本概念,5.1 樹的基本概念,5.4 哈夫曼樹及哈夫曼編碼,5.3 二叉樹的遍歷,5.5 樹與森林,教學重點與難點,重點：,二叉樹的性質； 二叉樹的存儲方法 二叉樹的遍歷及其應用 哈夫曼編碼,難點：,二叉樹遍歷算法的應用,課 前 思 考,你見過家族譜系圖嗎？試以圖形表示從你的祖父起的家族成員關系。,這類圖形正是本章要討論的“樹”結構。,5.1.1 樹的定義,5.1.2 樹的常用術語,5.1 樹的基本概念,5.1.1 樹的定義,樹是由n（n0）個結點所構成的有限集合，當n=0時，稱為空樹；當n0時，n個結點滿足以下條件：, 有且僅有一個稱為根的

2、結點。, 其余結點可分為m（m0）個互不相交的有限集合，且每一個集合又構成一棵樹，這棵樹稱為是根結點的子樹。,5.1.1 樹的定義,例如:,root,T1,T2,T3,5.1.1 樹的定義,樹的表示方法：,樹形表示法,文氏圖表示法,凹入圖表示法,廣義表(括號)表示法,5.1.1 樹的定義,5.1.1 樹的定義,5.1.1 樹的定義,線性結構,樹型結構,第一個數(shù)據元素 (無前驅),存在一個根結點 (無前驅),最后一個數(shù)據元素 (無后繼),存在多個葉子結點 (無后繼),其它數(shù)據元素 (一個前驅、 一個后繼),其它結點 (一個前驅(雙親)、 多個后繼(孩子),元素之間存在“一對一”的關系,元素之間存

3、在“一對多”的關系,5.1.1 樹的定義,5.1.2 樹的常用術語,5.1 樹的基本概念,5.1.2 樹的常用術語,結點:,結點的度:,樹的度:,葉子結點:,分支結點:,數(shù)據元素+所有關聯(lián)子樹根的分支,結點所擁有子樹的數(shù)目,樹中所有結點的度的最大值,度為零的結點,度大于零的結點,分支:,根和子樹根之間的連線(邊),結點的路徑:,由從根到該結點所經分支和結點構成,孩子結點、雙親結點 兄弟結點、堂兄弟 祖先結點、子孫結點,結點的層次:,樹的深度：,樹中所有結點層次數(shù)的最大值加1。,假設根結點的層次為0，則其它結點的層次是其雙親結點的層次數(shù)加1。,有序樹：,樹中各結點的所有子樹之間從左到右有嚴格的次

4、序關系。,無序樹:,森林：,由m（m0）棵互不相交的樹所構成的集合。,與有序樹相反，無序樹是指樹中各結點的所有子樹之間沒有嚴格的次序關系。,5.2.1 二叉樹的定義,5.2.2 二叉樹的性質,5.2.3 二叉樹的存儲結構,5.2 二叉樹的基本概念,5.2.1 二叉樹的定義,二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。,根結點,左子樹,右子樹,5.2.1 二叉樹的定義,二叉樹的五種基本形態(tài)：,N,空樹,只含根結點,N,N,N,L,R,R,右子樹為空樹,L,左子樹為空樹,左右子樹均不為空樹,5.2.1 二叉樹的定義,具有3個結點的樹與二叉樹的形態(tài)各有多少種

5、?,樹有2種而二叉樹有5種。,問,二叉樹就是度小于等于2的樹，這個結論是否正確？,滿二叉樹的定義,如果在一棵二叉樹中，它的所有結點或者是葉結點，或者是左、右子樹都非空，并且所有葉結點都在同一層上，則稱這棵二叉樹為滿二叉樹 。,完全二叉樹的定義,如果在一棵具有n個結點的二叉樹中，它的邏輯結構與滿二叉樹的前n個結點的邏輯結構相同，則稱這樣的二叉樹為完全二叉樹,完全二叉樹,非完全二叉樹,單分支樹的定義,左支樹：,左支樹,右支樹,右支樹：,所有結點都沒有右孩子的二叉樹。,所有結點都沒有左孩子的二叉樹。,5.2.1 二叉樹的定義,5.2.2 二叉樹的性質,5.2.3 二叉樹的存儲結構,5.2 二叉樹的基

6、本概念,5.2.2 二叉樹的性質,在二叉樹的第 i 層上至多有2i 個結點。(i0),用歸納法證明： 歸納基： 歸納假設： 歸納證明：,i = 0 層時，只有一個根結點： 20 = 1；,假設對所有的 j(0ji)層，命題成立；,則第 i層的結點數(shù) 2i-1 2 = 2i。,性質1：,5.2.2 二叉樹的性質,深度為 h （h1）的二叉樹上至多含 2h-1 個結點。,性質2：,證明：,基于上一條性質，深度為 h 的二叉樹上的結點數(shù)至多為: 20+21+ +2h-1 = 2h-1 。,5.2.2 二叉樹的性質,對于任何一棵二叉樹，若其葉結點的個數(shù)為n0 ，度為2的結點個數(shù)為n2，則有n0 = n

7、2+1 。,性質3：,則 二叉樹上結點總數(shù) n = ？ 二叉樹上分支總數(shù) e = ？,n0 + n1 + n2,而 e與 n的關系如何？,證明：,n1+2n2,由此得， n0 = n2 + 1 。,設度為1的結點數(shù)為n1,e= n-1,5.2.2 二叉樹的性質,度為m的樹中，葉子結點數(shù)與其它結點數(shù)之間的關系如何？,思考,5.2.2 二叉樹的性質,具有 n 個結點的完全二叉樹的深度為 log2n +1 或 log2(n+1) 。,性質4：,證明：,設完全二叉樹的深度為 h , 則根據第二條性質得,2h-1-1 n 2h -1,即2h-1 n 2h ,h-1 log2 n h,因為 h 只能是整數(shù)

8、，因此，,h =log2n + 1,推出,5.2.2 二叉樹的性質,性質5：,若對含 n 個結點的完全二叉樹從上到下且從左至右進行 0至 n-1 的編號，則對完全二叉樹中任意一個編號為 i 的結點,有：(1) 若 i=0，則該結點是二叉樹的根，無雙親， 否則，編號為 (i-1)/2 的結點為其雙親結 點；(2) 若 2i+1n，則該結點無左孩子，否則，編 號為 2i+1 的結點為其左孩子結點；(3) 若 2i+2n，則該結點無右孩子結點，否 則，編號為2i+2 的結點為其右孩子結點。,5.2.1 二叉樹的定義,5.2.2 二叉樹的性質,5.2.3 二叉樹的存儲結構,5.2 二叉樹的基本概念,5

9、.2.3 二叉樹的存儲結構,2.二叉樹的鏈式存儲結構,1. 二叉樹的順序存儲結構,5.2.3 二叉樹的存儲結構順序存儲,用一組地址連續(xù)的存儲單元從根結點開始依次自上而下，并按層次從左到右存儲完全二叉樹上的各結點元素，即將完全二叉樹編號為i的結點元素存儲在下標為i數(shù)組元素中。,對于完全二叉樹：,5.2.3 二叉樹的存儲結構順序存儲,例如(完全二叉樹）：,5.2.3 二叉樹的存儲結構順序存儲,先在樹中增加一些并不存在的虛結點并使其成為一棵完全二叉樹，然后用與完全二叉樹相同的方法對結點進行編號，再將編號為i的結點的值存放到數(shù)組下標為i的數(shù)組單元中，虛結點不存放任何值。,對于非完全二叉樹：,5.2.3

10、 二叉樹的存儲結構順序存儲,例如(非完全二叉樹）：,問：一個深度為 k 且只有 k 個結點的右支樹需要的數(shù)組存儲單元為多少？,順序存儲僅適用于滿或完全二叉樹。,5.2.3 二叉樹的存儲結構鏈式存儲,1. 二叉鏈表,2三叉鏈表,5.2.3 二叉樹的存儲結構二叉鏈表,root,結點結構:,5.2.3 二叉樹的存儲結構三叉鏈表,結點結構:,5.2.3 二叉樹的存儲結構二叉鏈表,二叉鏈表中結點類的描述(書中P156),public class BiTreeNode ,/ 構造一個空結點 public BiTreeNode() this(null); ,/ 構造一個左、右孩子域為空的結點 public

11、BiTreeNode(Object data) this(data, null, null)； ,private Object data; / 結點的數(shù)據域 private BiTreeNode lchild, rchild; / 左、右孩子域,5.2.3 二叉樹的存儲結構二叉鏈表,二叉鏈表中結點類的描述(書中P156),public class BiTreeNode ,/ 構造一個數(shù)據域和左、右孩子域都不為空的結點 public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) this.data = data; th

12、is.lchild = lchild; this.rchild = rchild; ,5.2.3 二叉樹的存儲結構二叉鏈表,二叉鏈表存儲結構下二叉樹類的描述(書中P158),public class BiTree ,/ 構造一棵空樹 public BiTree () this.root=null; ,/ 構造一棵根結點為root的樹 public BiTree(BiTreeNode root) this.root=root; ,private BiTreeNode root; / 樹的根結點,5.3.1 二叉樹的遍歷方法及其實現(xiàn),5.3.2 二叉樹遍歷算法的應用舉例,5.3.3 建立二叉樹,5

13、.3 二叉樹的遍歷,5.3.1 二叉樹的遍歷方法及其實現(xiàn),一、問題的提出,二、二叉樹遍歷方法及其遞歸實現(xiàn),三、二叉樹遍歷方法的非遞歸實現(xiàn),5.3.1 二叉樹的遍歷方法及其實現(xiàn),沿著某一條搜索路徑對二叉樹中的結點進行訪問，使得每個結點均被訪問一次，而且僅被訪問一次。,一、問題的提出,“訪問”的含義可以很廣，如：輸出結點的信息等。,什么是遍歷?,5.3.1 二叉樹的遍歷方法及其實現(xiàn),一、問題的提出,“遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結構。,每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。

14、,5.3.1 二叉樹的遍歷方法及其實現(xiàn),一、問題的提出,二、二叉樹遍歷方法及其遞歸實現(xiàn),三、二叉樹遍歷方法的非遞歸實現(xiàn),5.3.2 二叉樹的遍歷方法及其實現(xiàn),二、二叉樹的遍歷方法及遞歸實現(xiàn),對“二叉樹”而言，可以有三條搜索路徑：,1先上后下的遍歷； 2先左后右的遍歷； 3先右后左的遍歷。,5.3.1 二叉樹的遍歷方法及其實現(xiàn),二叉樹的遍歷方法,對應三條搜索路徑，“二叉樹” 有7種遍歷方法：,1. 層次遍歷方法；,2. DLR(先根遍歷)； LDR(中根遍歷)； LRD(后根遍歷)。,3. DRL；RDL；RLD。,5.3.1 二叉樹的遍歷方法及其實現(xiàn),1.層次遍歷,若二叉樹為空，則為空操作；否

15、則，按自上而下先訪問第0層的根結點，然后再從左到右依次訪問各層次中的每一個結點。,層次遍歷序列：,ABECFDGHK,5.3.1 二叉樹的遍歷方法及其實現(xiàn),2.先根(序)遍歷(DLR)定義及遞歸實現(xiàn),若二叉樹為空樹，則空操作；否則， （1）訪問根結點； （2）先根遍歷左子樹； （3）先根遍歷右子樹。,先根遍歷序列：,ABCDEFGHK,先根遍歷序列：,A B C D E F G H K,public void preRootTraverse(BiTreeNode T) ,先根遍歷操作實現(xiàn)的遞歸算法描述:,5.3.1 二叉樹的遍歷方法及其實現(xiàn),if (T！=null) ,System.out.p

16、rint(T.getData();,preRootTraverse(T.getLchild();,preRootTraverse(T.getRchild();,5.3.1 二叉樹的遍歷方法及其實現(xiàn),3.中根(序)遍歷(LDR)定義及遞歸實現(xiàn),若二叉樹為空樹，則空操作；否則， （1）中根遍歷左子樹； （2）訪問根結點； （3）中根遍歷右子樹。,動畫播放 （6-4-2-2）,中根遍歷序列：,BDCQEHGKF,中根遍歷序列：,B D C A E H G K F,public void intRootTraverse(BiTreeNode T) ,中根遍歷操作實現(xiàn)的遞歸算法描述:,5.3.1 二叉樹

17、的遍歷方法及其實現(xiàn),if (T！=null) ,System.out.print(T.getData();,intRootTraverse(T.getLchild();,intRootTraverse(T.getRchild();,5.3.1 二叉樹的遍歷方法及其實現(xiàn),4.后根(序)遍歷(LRD)定義及遞歸實現(xiàn),若二叉樹為空樹，則空操作；否則， （1）后根遍歷左子樹； （2）后根遍歷右子樹； （3）訪問根結點。,動畫播放 （6-4-2-3）,后根遍歷序列：,DCBHKGFE,后根遍歷序列：,D C B H K G F E A,public void postRootTraverse(BiTre

18、eNode T) ,后根遍歷操作實現(xiàn)的遞歸算法描述:,5.3.1 二叉樹的遍歷方法及其實現(xiàn),if (T！=null) ,System.out.print(T.getData();,postRootTraverse(T.getLchild();,postRootTraverse(T.getRchild();,5.3.1 二叉樹的遍歷方法及其實現(xiàn),一、問題的提出,二、二叉樹遍歷方法及其遞歸實現(xiàn),三、二叉樹遍歷方法的非遞歸實現(xiàn),5.3.1 二叉樹的遍歷方法及其實現(xiàn),1 . 先根遍歷操作的非遞歸實現(xiàn),方法：,借助一個棧來記載當前被訪問結點的右孩子 結點。,主要思想：,從非空二叉樹的根結點出發(fā)，沿著該結

19、點的左子樹向下搜索，在搜索過程中每遇到一個結點就先訪問該結點，并將該結點的非空右孩子結點壓棧。當左子樹結點訪問完成后，從棧頂彈出結點的右孩子結點，然后用上述同樣的方法去遍歷該結點的右子樹，依此類推，直到二叉樹中所有的結點都被訪問為止。,5.3.1 二叉樹的遍歷方法及其實現(xiàn),1 . 先根遍歷操作的非遞歸實現(xiàn),基本步驟：, 創(chuàng)建一個棧對象，根結點入棧；, 當棧為非空時，將棧頂結點彈出棧內并訪問該結點；,LinkStack S=new LinkStack();,T=(BiTreeNode)S.pop();,S.push(T);,System.out.print(T.getData();,5.3.1

20、二叉樹的遍歷方法及其實現(xiàn),1 . 先根遍歷操作的非遞歸實現(xiàn),基本步驟：, 對當前訪問結點的非空左孩子結點相繼依次訪問，并將當前訪問結點的非空右孩子結點壓入棧內；, 重復執(zhí)行步驟和，直到棧為空為止。,While(T!=null) ,if (T.getLchild()!=null) System.out.print(T.getData();,if (T.getRchild()!=null) S.push(T.getRchild();,T=T.getLchild();,先根遍歷的非遞歸算法(書P161算法5.4),LinkStack S=new LinkStack();,T=(BiTreeNode)

21、S.pop();,S.push(T);,System.out.print(T.getData();,while(T!=null) ,if (T.getLchild()!=null) System.out.print(T.getData();,if (T.getRchild()!=null) S.push(T.getRchild();,T=T.getLchild();,while(!S.isEmpty() ,public void preRootTraverse() BiTreeNode T=root; ,if (T! =null) ,時間復雜度：O(n),5.3.1 二叉樹的遍歷方法及其實現(xiàn),

22、2 . 中根遍歷操作的非遞歸實現(xiàn),方法：,借助一個棧來記載遍歷截長過程中所經歷的而未被訪問的所有結點,主要思想：,從非空二叉樹的根結點出發(fā)，沿著該結點的左子樹向下搜索，在搜索過程中將所遇到的每一個結點依次壓棧，直到二叉樹中最左下的結點壓棧為止，然后從棧中彈出棧頂結點并對其進行訪問，訪問完后再進入該結點的右子樹并用上述同樣的方法去遍歷該結點的右子樹，依此類推，直到二叉樹中所有的結點都被訪問為止。,5.3.1 二叉樹的遍歷方法及其實現(xiàn),2 . 中根遍歷操作的非遞歸實現(xiàn),基本步驟：, 創(chuàng)建一個棧對象，根結點入棧；,若棧頂結點非空，則將棧頂結點的非空左孩子相繼進棧；,LinkStack S=new L

23、inkStack();,while( S.peek()!=null ) ,S.push(T);,S.push(BiTreeNode)S.peek().getLchild();,S.pop(); /空結點出棧,5.3.1 二叉樹的遍歷方法及其實現(xiàn),2 . 中根遍歷操作的非遞歸實現(xiàn),基本步驟：,棧頂結點出棧并訪問非空棧頂結點，再 使該棧頂結點的非空右孩子結點入棧；, 重復執(zhí)行步驟和，直到棧為空為止。,if (!S.isEmpty() ,T=(BiTreeNode)S.pop();,System.out.print(T.getData();,S.push(T.getRchild();,中根遍歷的非遞

24、歸算法(書P162算法5.5),LinkStack S=new LinkStack();,S.push(T);,while(!S.isEmpty() ,public void inRootTraverse() BiTreeNode T=root; ,if (T! =null) ,while( S.peek()!=null ) ,S.push(BiTreeNode)S.peek().getLchild();,S.pop();,if (!S.isEmpty() ,T=(BiTreeNode)S.pop();,System.out.print(T.getData();,S.push(T.getRch

25、ild();,時間復雜度：O(n),5.3.1 二叉樹的遍歷方法及其實現(xiàn),3 . 后根遍歷操作的非遞歸實現(xiàn),方法：,借助一個棧來記載遍歷截長過程中所經歷的而未被訪問的所有結點;,引進一個訪問標志變量flag和一個結點指針p。,其中：flag用來標記當前棧頂結點是否被訪問，當值為true時，表示棧頂結點已被訪問；當值為false時，表示當前棧頂結點未被訪問，指針p指向當前遍歷過程中最后一個被訪問的結點。,5.3.1 二叉樹的遍歷方法及其實現(xiàn),3 .后根遍歷操作的非遞歸實現(xiàn),基本步驟：, 創(chuàng)建一個棧對象，根結點入棧，p賦初始值null；,若棧頂結點非空，則將棧頂結點的非空左孩子相繼進棧；,Link

26、Stack S=new LinkStack();,while( S.peek()!=null ) ,S.push(T);,S.push(BiTreeNode)S.peek().getLchild();,S.pop();,BiTreeNOde p=null;,若棧非空，查看棧頂結點，若棧頂結點的右孩子為空，或者與p相等，則將棧頂結點彈出棧并訪問它，同時使p指向該結點，并置flag值為true；否則，將棧頂結點的右孩子壓入棧，并置flag值為false。,if (T.getRchild()=null |T.getRchild()=p) else ,System.out.print(T.getDat

27、a();,S.push(T.getRchild();,T=(BiTreeNode)S.pop();,p=T;,flag=true;,flag=flase;,5.3.1 二叉樹的遍歷方法及其實現(xiàn),3 . 后根遍歷操作的非遞歸實現(xiàn),基本步驟：,若flag值為true，則重復執(zhí)行步驟；否則，重復執(zhí)行步驟和，直到棧為空為止。,while( !S.isEmpty() while( !S.isEmpty() if (!flag) break; ,后根遍歷的非遞歸算法(書P163算法5.6),public void postRootTraverse() BiTreeNode T=root; ,if (T!

28、=null) ,while( !S.isEmpty() while( !S.isEmpty() if (!flag) break; ,時間復雜度：O(n),5.3.1 二叉樹的遍歷方法及其實現(xiàn),4 . 層次遍歷操作的非遞歸實現(xiàn),方法：,借助一個隊列。在遍歷開始時，首先將根結點入隊，然后每次從隊列中取出隊首元素進行處理，每處理一個結點，都是先訪問該結點，再按從左到右的順序把它的孩子結點依次入隊。,5.3.1 二叉樹的遍歷方法及其實現(xiàn),4 . 層次遍歷操作的非遞歸實現(xiàn),基本步驟：,創(chuàng)建一個鏈隊列對象，根結點入隊；,LinkStack L=new LinkQueue();,L.offer(T);,5

29、.3.1 二叉樹的遍歷方法及其實現(xiàn),4 . 層次遍歷操作的非遞歸實現(xiàn),基本步驟：,若隊列非空，重復將隊首結點出隊并訪問該結點，再將該結點的非空左、右孩子結點依次入隊，直到隊列為空為止。,while( !L.isEmpty() ,T=(BiTreeNode)L.poll();,System.out.print(T.getData();,if (T.getLchild()!=null) L.offer(T.getLchild();,if (T.getRchild()!=null) L.offer(T.getRchild();,層次遍歷的非遞歸算法(書P166算法5.7),public void l

30、evelTraverse() BiTreeNode T=root; ,if (T! =null) ,LinkStack L=new LinkQueue();,L.offer(T);,while( !L.isEmpty() ,T=(BiTreeNode)L.poll();,System.out.print(T.getData();,if (T.getLchild()!=null) L.offer(T.getLchild();,if (T.getRchild()!=null) L.offer(T.getRchild();,時間復雜度：O(n),5.3.1 二叉樹的遍歷方法及其實現(xiàn),5.3.2 二叉

31、樹遍歷算法的應用舉例,5.3.3 建立二叉樹,5.3 二叉樹的遍歷,5.3.2 二叉樹的遍歷應用舉例,1. 在二叉樹上的查找某個結點,2. 計算二叉樹中結點的個數(shù),3. 求二叉樹的深度,4.判斷兩棵二叉樹是否相等,1. 在二叉樹上的查找某個結點,要求： 實現(xiàn)方法：,在以T為根結點的二叉樹中查找值為x的結點，若找到，則返回該結點；否則，返回空值。,可在先根遍歷過程中進行查找，并將先根遍歷算法中的“訪問結點”的操作改為：將根結點的值與x進行比較的操作。,1. 在二叉樹上的查找某個結點,實現(xiàn)步驟：,1)若二叉樹為空，則不存在這個結點，返回空值；否則，將根結點的值與x進行比較，若相等，則返回該結點；,

32、2) 否則在左子樹中進行查找，若找到，則返回找到的結點；,3) 否則返回在右子樹中進行查找的結果。,1. 在二叉樹上的查找某個結點,實現(xiàn)算法(書P166算法5.8)：,public BiTreeNode searchNode(BiTreeNode T, Object x) ,if (T! =null) ,if (T.getData().equals(x) return T; else ,BiTreeNode lresult=searchNOde(T.getLchild(),x);,return lresult!=null?lresult:searchNOde(T.getRchild(),x);

33、,5.3.2 二叉樹的遍歷應用舉例,1. 在二叉樹上的查找某個結點,2. 計算二叉樹中結點的個數(shù),3. 求二叉樹的深度,4.判斷兩棵二叉樹是否相等,要求： 實現(xiàn)方法:,計算以T為根結點的二叉樹中所含結點的個數(shù)，并返回其值。,由于二叉樹中結點的個數(shù)等于1個根結點再分別加上它的左、右子樹中結點的個數(shù)，所以可以運用不同的遍歷遞歸算法的思想來統(tǒng)計出二叉樹中結點的個數(shù)。,2. 計算二叉樹中結點的個數(shù),實現(xiàn)步驟:(以中根遍歷為例),1)引進計數(shù)變量count并賦初值0 ；,2) 若二叉樹非空，則：,3) 返回count值。, 統(tǒng)計根結點的左子樹的結點個 數(shù)，并加入到count變量中；, count值加1；

34、, 統(tǒng)計根結點的右子樹的結點個 數(shù)，并加入到count變量中；,2. 計算二叉樹中結點的個數(shù),實現(xiàn)算法(參看書P167算法5.9)：,public int countNode(BiTreeNode T) ,if (T! =null) ,count+=countNode(T.getLchild();,count+;,count+=countNode(T.getRchild();,2. 計算二叉樹中結點的個數(shù),int count = 0;,return count;,5.3.2 二叉樹的遍歷應用舉例,1. 在二叉樹上的查找某個結點,2. 計算二叉樹中結點的個數(shù),3. 求二叉樹的深度,4.判斷兩棵二

35、叉樹是否相等,要求： 實現(xiàn)方法:,求出以T為根結點的二叉樹的深度并返回其值。,1)先分別求得左、右子樹的深度；,3. 求二叉樹的深度,2)再將后根遍歷算法中的“訪問結點”的操作改為：求得左、右子樹深度的最大值，最后將最大值加1后返回其值。,從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1，所以可利用后根遍歷算法來實現(xiàn)。,實現(xiàn)算法(書P168算法5.11)：,public int getDepth(BiTreeNode T) ,if (T! =null) return 0;,int lDepth = getDepth(T.getLchild();,int rDepth = g

36、etDepth(T.getRchild();,return 1 + (lDepth rDepth ? lDepth : rDepth);,3. 求二叉樹的深度,5.3.2 二叉樹的遍歷應用舉例,1. 在二叉樹上的查找某個結點,2. 計算二叉樹中結點的個數(shù),3. 求二叉樹的深度,4.判斷兩棵二叉樹是否相等,要求： 實現(xiàn)方法:,判斷根結點為T1、T2的兩棵二叉樹是否相等，若相等，則返回true；否則，返回false。,因為一棵二叉樹由根、左子樹和右子樹三個部分組成，所以只有當兩棵二叉樹的三個組成部分都對應相等時，這兩棵樹才相等。而左、右子樹的相等判斷可以用對二叉樹相等判斷的同樣方法來實現(xiàn)，即可用遞

37、歸調用來實現(xiàn)。,4.判斷兩棵二叉樹是否相等,所以，可利用先根、中根、和后根遍歷中的任何一種算法思想來實現(xiàn)。,實現(xiàn)步驟:(以中根遍歷為例),1)若兩棵二叉樹都為空，則兩棵二叉樹相等，返回true;,2)若兩棵二叉樹都非空，則：,3)其它任何情況都返回false。,若左子樹相等，則繼續(xù)判斷它們的根結點是否相等，即轉 ；,若根結點的值相等，則繼續(xù)判斷它們的右子樹是否相等，即轉 ；,若右子樹也相等，則兩棵二叉樹相等，返回true;,4.判斷兩棵二叉樹是否相等,實現(xiàn)算法(書P168算法5.12)：,public boolean isEqual(BiTreeNode T1, BiTreeNode T2)

38、,if (T1=null,if (T1!=null,return false;,5.3.1 二叉樹的遍歷方法及其實現(xiàn),5.3.2 二叉樹遍歷算法的應用舉例,5.3.3 建立二叉樹,5.3 二叉樹的遍歷,5.3.3 建立二叉樹 (二叉鏈式存儲結構),3. 由標明空子樹的先根遍歷序列建 二叉樹,1. 由先根和中根遍歷序列建二叉樹,2. 由后根和中根遍歷序列建二叉樹,4. 由完全二叉樹的順序存儲結構建 立二叉鏈式存儲結構,1. 由先根和中根遍歷序列建二叉樹,僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，,如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？,二叉樹的先序序列,

39、二叉樹的中序序列,左子樹,左子樹,右子樹,右子樹,根,根,1. 由先根和中根遍歷序列建二叉樹,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,先序序列中序序列,1. 由先根和中根遍歷序列建二叉樹-算法,建立一棵二叉樹的過程如下：,其中： preOrder是整棵樹的先根遍歷序列； inOrder是整棵樹的中根遍歷序列； reIndex是先根遍歷序列在preOrder中的開始位置; inIndex是中根遍歷序列在inOrder中的開始位置; count表示樹中結點的個數(shù)。,1. 由先根和中根遍歷序列

40、建二叉樹- 算法,實現(xiàn)方法：,引入5個參數(shù)：,preOrder、inOrder、preIndex、inIndex和count。,1. 由先根和中根遍歷序列建二叉樹-算法,public BiTree(String preOrder, String inOrder, int preIndex, int inIndex,int count) ,if (count 0) ,char r = preOrder.charAt(preIndex);,for (int i=0; i count; i+),if (r = inOrder.charAt( i + inIndex ) break;,root = n

41、ew BiTreeNode(r);,root.setLchild( new BiTree (preOrder, inOrder, preIndex + 1, inIndex,i) .root );,root.setRchild( new BiTree (preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count - i - 1) .root );,P170/算法5.13,5.3.3 建立二叉樹 (二叉鏈式存儲結構),3. 由標明空子樹的先根遍歷序列建 二叉樹,1. 由先根和中根遍歷序列建二叉樹,2. 由后根和中根遍歷序列建二叉樹,4.

42、 由完全二叉樹的順序存儲結構建 立二叉鏈式存儲結構,2. 由后根和中根遍歷序列建二叉樹,二叉樹的后序序列,二叉樹的中序序列,左子樹,左子樹,右子樹,右子樹,根,根,問：由二叉樹的前序和后序序列是否也可以唯一確定一棵樹？,2. 由后根和中根遍歷序列建二叉樹,由二叉樹的前序和后序序列不可以唯一確定一棵樹,如下二棵樹：,其前序遍歷序列都為：A B,其后序遍歷序列都為：B A,2. 由后根和中根遍歷序列建二叉樹-算法,學生可依照算法5.13自行完成！,略,5.3.3 建立二叉樹 (二叉鏈式存儲結構),3. 由標明空子樹的先根遍歷序列建 二叉樹,1. 由先根和中根遍歷序列建二叉樹,2. 由后根和中根遍歷

43、序列建二叉樹,4. 由完全二叉樹的順序存儲結構建 立二叉鏈式存儲結構,3.由標明空子樹的先根遍歷序列建 二叉樹,例如:,以字符“#”表示,AB # C # # D # #,空 樹：,只含一個根結點,A,以下列字符串表示,標明空子樹的先根遍歷序列就是在先根遍歷序列中加入空樹信息。,以字符串“A#”表示,3.由標明空子樹的先根遍歷序列建 二叉樹,算法步驟：,在完整先根遍歷數(shù)據輸入正確的前提下，由此建立二叉鏈表的算法為： 若讀入的字符是#，則建立空樹； 否則 建立根結點；遞歸建立左子樹的二叉鏈表；遞歸建立右子樹的二叉鏈表。,3.由標明空子樹的先根遍歷序列建 二叉樹,public BiTree(Str

44、ing preStr) / 算法5.14結束,P172/算法5.14,private int index=0; /用于記從preStr中取字符的位置,char c=preStr.charAt( index+ );,if (c != #) else,root = new BiTreeNode(c); /建立樹的根結點,root.setLchild(new BiTree(preStr).root); / 建立樹的左子樹,root.setRchild(new BiTree(preStr).root); / 建立樹的右子樹,root = null;,5.3.3 建立二叉樹 (二叉鏈式存儲結構),3.

45、由標明空子樹的先根遍歷序列建 二叉樹,1. 由先根和中根遍歷序列建二叉樹,2. 由后根和中根遍歷序列建二叉樹,4. 由完全二叉樹的順序存儲結構建 立二叉鏈式存儲結構,4.由完全二叉樹的順序存儲結構建立二叉鏈式存儲結構,完全二叉樹：,其對應的順序存儲結構：,右孩子的編號為,由二叉樹的性質5可知，結點編號規(guī)則：,根結點的編號為,？,0,編號為 i的結點其左孩子的編號為,？,2i+1,？,2i+2,4.由完全二叉樹的順序存儲結構建立二叉鏈式存儲結構,public BiTreeNode createBiTree(String sqBiTree,int index) ,P173/Exam5_7中,BiT

46、reeNode root=null;,if (indexsqBitree .length() ,root = new BiTreeNode(sqBiTree.charAt(index);,root.setLchild(creatBiTree(sqBiTree,2*i+1); / 建立樹的左子樹,root.setRchild(creatBiTree(sqBiTree,2*i+2); / 建立樹的右子樹,return root;,算法：,作業(yè)1：,習題五中的 三、1，2,附加題如下：,1. 已知一棵度為m的樹中有n1個度為1 的結點，n2個度為2的結點，nm個度為m的結點，問該樹中有多少片葉子？,

47、2.試采用順序存儲方法和二叉鏈式存儲方法分別畫出下圖所示的二叉樹的存儲結構。,附加題：,附加題：,3. 分別寫出題2中二叉樹的先根、中根和后序根遍歷序列。,4. 已知一棵樹二叉樹的后根遍歷和中根遍歷的序列分別為：A C D B G I H F E和A B C D E F G H I，請畫出該二叉樹，并寫出它的先根遍歷的序列。,5. 已知一棵樹二叉樹的先根遍歷和中根遍歷的序列分別為：A B D G H C E F I和G D H B A E C I F，請畫出此二叉樹，并寫出它的后根遍的序列。,1.已知一棵度為m的樹中有n1個度為1的結點，n2個度結點，nm個度為m的結點，問該樹中有多少片葉子？

48、,解：設樹的總結點個數(shù)為n, 葉子結點的個數(shù)為n0，則 n= n0 + n1 + n2 + nm (1) 又因為樹的總分支數(shù)為 n-1,且 n-1= n1 + n2 *2+ n3 *3+ nm*m (2) (1)-(2)得 1= n0n1 -2 n2 - -（m-1) nm 則： n0 = 1 + n2+2 n3+(m-1) nm,附加題解答：,2.試采用順序存儲方法和二叉鏈式存儲方法分別畫出下圖所示的二叉樹的存儲結構。,二叉鏈式存儲結構：,順序存儲結構：,附加題解答：,3.分別寫出題2中二叉樹的先根、中根和后序根遍歷序列。,前根序列：ABDEGCFH,中根序列：DBGEACHF,后根序列：D

49、GEBHFCA,附加題解答：,4. 已知一棵樹二叉樹的后根遍歷和中根遍歷的序列分別為：A C D B G I H F E和A B C D E F G H I，請畫出該二叉樹，并寫出它的先根遍歷的序列。,先根遍歷序列：EBADCFHGI,構造的二叉樹如下：,附加題解答：,5. 已知一棵樹二叉樹的先根遍歷和中根遍歷的序列分別為：A B D G H C E F I和G D H B A E C I F，請畫出此二叉樹，并寫出它的后根遍的序列。,后根遍歷序列：GHDBEIFCA,構造的二叉樹如下：,附加題解答：,5.4.1 哈夫曼樹的基本概念,5.4.2 哈夫曼樹和哈夫曼編 碼的構造方法,5.4.3 構

50、造哈夫曼樹和哈夫 曼編碼類的描述,5.4 哈夫曼樹及哈夫曼編碼,5.4.1 哈夫曼樹的基本概念,結點的路徑長度：,結點間的路徑：,從一個結點到另一個結點所經歷的結點和分支序列。,從根結點到該結點的路徑上分支的數(shù)目。,結點的權：,在實際應用中，人們往住會給樹中的每一個結點賦予一個具有某種實際意義的數(shù)值，這個數(shù)值被稱為該結點的權值。,5.4.1 哈夫曼樹的基本概念,樹的帶權路徑長度：,結點的帶權路徑長度：,結點的路徑長度與該結點的權值的乘積。,樹中所有葉結點的帶權路徑長度之和 。,假設樹上有 n 個葉結點，通常記作: 其中Li為帶權 wi的葉子結點的帶權路徑長度。,5.4.1 哈夫曼樹的基本概念,

51、最優(yōu)二叉樹：,給定n個權值并作為n個葉結點按一定規(guī)則構造一棵二叉樹，使其帶權路徑長度達到最小值，則這棵二叉樹被稱為最優(yōu)二叉樹。也稱哈夫曼樹。,在所有含 n 個葉子結點、并帶相同權 值的 二叉樹中，必存在一棵其帶權路徑 長度取最小值的樹，這樹就是“最優(yōu)樹”。,WPL(T)= 72+52+23+43+92 =60,WPL(T)= 74+94+53+42+21 =89,5.4.1 哈夫曼樹的基本概念,如何構造最優(yōu)樹（哈夫曼樹）呢？,5.4.1 哈夫曼樹的基本概念,5.4.2 哈夫曼樹和哈夫曼編 碼的構造方法,5.4.3 構造哈夫曼樹和哈夫 曼編碼類的描述,5.4 哈夫曼樹及哈夫曼編碼,5.4.2 哈

52、夫曼樹及哈夫曼編碼的構造方法,(1) 根據給定的 n 個權值 w1, w2, , wn， 構造 一個由n 棵二叉樹所構成的集合 F = T1, T2, , Tn， 其中每棵二叉樹中均只含一個帶權值為 wi 的根結點，其左、右子樹為空樹；,赫夫曼算法的主要步驟（P175）,5.4.2 哈夫曼樹及哈夫曼編碼的構造,赫夫曼算法的主要步驟（P175）,(2)在二叉樹森林F中選取根結點的權值最小和次小的兩棵二叉樹，分別把它們作為左子樹和右子樹去構造一棵新二叉樹，新二叉樹的根結點權值為其左、右子樹根結點的權值之和。,5.4.2 哈夫曼樹及哈夫曼編碼的構造方法,赫夫曼算法的主要步驟（P175）,(3) 作為

53、新二叉樹的左、右子樹的這兩棵二叉樹從森林F中刪除，同時加入剛生成的新二叉樹；,(4) 重復 (2) 和 (3) 兩步，直至 F 中只 含一棵二叉樹為止，則這種棵二叉樹就是所構成的哈夫曼樹。,5.4.2 哈夫曼樹及哈夫曼編碼的構造方法,9,例如: 已知權值 W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,5.4.2 哈夫曼樹及哈夫曼編碼的構造方法,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,哈夫曼碼,9,5,2,7,16,5.4.2 哈夫曼樹及哈夫曼編碼的構造方法,再例如:

54、書P177的例5.8 (由學生完成）,已知在一個信息通信聯(lián)絡中使用了8個字符：a、b、c、d、e、f、g和h，每個字符的使用頻度分別為：6、30、8、9、15、24、4和12，試設計各個字符的哈夫曼編碼。,問：一棵有 n個葉子結點的哈夫曼樹共有多 少個結點？,2*n+1 個,5.4.2 哈夫曼樹及哈夫曼編碼的構造方法,用哈夫曼樹進行譯碼,指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。,前綴編碼：,哈夫曼編碼是一種前綴碼。,從哈夫曼樹的根開始，從左到右把二進制編碼的每一位進行判別，若遇到0，則選擇左分支走向下一個結點；若遇到1，則選擇右分支走向下一個結點，直至到達一個樹葉結

55、點，便求得相應字符。,譯碼過程是編碼過程的逆過程：,5.4.1 哈夫曼樹的基本概念,5.4.2 哈夫曼樹和哈夫曼編 碼的構造方法,5.4.3 構造哈夫曼樹和哈夫 曼編碼類的描述,5.4 哈夫曼樹及哈夫曼編碼,5.4.3 哈夫曼樹及哈夫曼編碼類的描述,哈夫曼樹的結點存儲結構示意圖：,其中: weight域存放結點的權值； flag域存放結點是否加入哈夫曼樹的標志 值，等于1時表示已加入，否則沒加入； parent、rchild、lchild域分別存放父結 點，左、右孩子結點的地址。,5.4.3 哈夫曼樹及哈夫曼編碼類的描述,哈夫曼樹的結點類描述：（書中P178）,public class Huf

56、fmanNode ,public HuffmanNode () / 構造一個空結點 this(null); ,/ / 構造一個左、右孩子域為空的結點 public HuffmanNode (int weight ) this.weight=weight; flag=0; parent=lchild=rchild=null; ,private int weight; / 結點的數(shù)據域 private int flag; /結點是否加入哈夫曼樹的標志 private HuffmanNode parent, lchild, rchild; /父結點， 左、右孩子結點域,5.4.3 哈夫曼樹及哈夫曼編

57、碼類的描述,構造哈夫曼樹和哈夫曼編碼的類描述：,public class HuffmanTree ,（略）,書中P179,public int huffmanCoding (int W) ,int n = W.length; / 字符個數(shù) int m = 2 * n - 1; / 哈夫曼樹的結點數(shù),5.4.3 哈夫曼樹及哈夫曼編碼類的描述,例如：對于書P177例5.8，按HuffmanTree類中的HuffmanCoding方法可構造如下圖的一棵二棵樹：,weight flag parent lchild rchild,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,其存

58、儲結構HN的初始和終結狀態(tài)分別如下圖所示 ：,weight flag parent lchild rchild,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,5.4.3 哈夫曼樹及哈夫曼編碼類的描述,所得的哈夫曼編碼如下圖所示 ：,5.5.1 樹、森林與二叉樹之間的轉換,5.5.2 樹的存儲結構,5.5.3 樹與森林的遍歷,5.5 樹與森林,5.5.1 樹、森林與二叉樹之間的轉換,1. 樹轉換成二叉樹的規(guī)則：,左孩子右兄弟,5.5.1 樹、森林與二叉樹之間的轉換,樹轉換成二叉樹可形象描述為以下3個步驟：,(1) 加線,(2) 刪線,(3) 旋轉,樹,二叉樹,5.5.1 樹、森林與二叉樹之間的轉換,2. 二叉樹轉換成樹的規(guī)則：,是樹轉換成二叉樹的逆過程：,(1) 加線,(2) 刪線,(3) 旋轉,二叉樹,樹,5.5.1 樹、森林與二叉樹之間的轉換,3. 森林轉換成二叉樹