數(shù)據(jù)結構與算法（Java語言版）課件 第9章 二叉樹與TreeSet類

第9章二叉樹與TreeSet類2024/11/919.1二叉樹的基本概念2024/11/92一棵樹上的每個結點至多有2個子結節(jié)點，稱這樣的樹是二叉樹。沒有任何結點的二叉樹被稱為空二叉樹。一個結點如果有2個子結點，那么把一個稱為左子結點，把另一個稱為右子結點，如果只有1個子結點，那么這個子結點也要分為是左子結點還是右子結點。2024/11/939.1二叉樹的基本概念●左子樹與右子樹一個結點和它的左、右子結點是父子關系。一個結點的左、右子結點是兄弟關系，二者互稱為兄弟結點，即有相同父結點的結點是兄弟結點?！窀缸雨P系與兄弟關系把二叉樹的一個結點的左子節(jié)點看作一個樹的根節(jié)點的話，那么以左子節(jié)點為根的樹也是一個二叉樹，稱作該節(jié)點的左子樹（如果沒有左子結點，左子樹是空樹），同樣把此結點右子節(jié)點看作一個樹的根節(jié)點的話，以右子節(jié)點為根的樹也是一個二叉樹（如果沒有右子結點，右子樹是空樹）。一個樹，就是由根結點和它的左子樹和右子樹所構成。2024/11/949.1二叉樹的基本概念●樹的層

樹用倒置的樹形來表示，結點按層從上向下排列，根結點是第0層。二叉樹從也是從根開始定義，根為第0層，根的子結點為第1層，以此類推。除了第0層，每一層上的結點和上一層中的一個結點有關系，但可能和下一層的至多2結點有關系。即根結點沒有父節(jié)點，其它結點有且只有一個父結點，但至多有2個子結點，葉結點沒有子結點。2024/11/959.1二叉樹的基本概念●滿二叉樹（FullBinaryTree）每個非葉結點都有兩個子結點的是滿二叉樹?！裢昝蓝鏄?PerfectBinaryTree)

2024/11/969.1二叉樹的基本概念●完全二叉樹(CompleteBinaryTree)完全二叉樹從根結點到倒數(shù)第二層的結點數(shù)目都是滿的，最后一層可以不滿，但最后一層葉子結點都是靠左對齊（按最后一層從左向右的序號，一個挨著一個靠左對齊），并且從左向右數(shù)，只允許最后一個葉子結點可以沒有兄弟結點，而且如果最后一個葉子結點沒有兄弟結點的話，它必須是左子結點。2024/11/979.1二叉樹的基本概念●樹的高度與深度一個葉結點所在的層的層數(shù)加1（層是從0開始的，只有一個根結點的二叉樹高度為1，規(guī)定空二叉樹的高度是0），稱作這個葉節(jié)點的高度，所有葉節(jié)點中，其高度最大者稱為二叉樹的高度.從根結點（包括根結點）按照父子關系找到一個葉結點所經(jīng)歷過的結點（包括葉結點）數(shù)目，稱作這個葉結點的深度。所有葉節(jié)點中，其深度最大者的深度稱為樹的深度。不難得知，樹的深度和高度是相等的，只是敘述的方式不同而已。

9.2遍歷二叉樹2024/11/98遍歷二叉樹有三種常見的方式，分別是前序遍歷，中序遍歷和后序遍歷。2024/11/999.2遍歷二叉樹●前序遍歷

publicvoidpreOrder(Nodep){//前序遍歷if(p!=null){p.visited();//輸出ppreOrder(p.left);//遞歸遍歷左子樹preOrder(p.right);//遞歸遍歷右子樹}}ABDFECG2024/11/9109.2遍歷二叉樹●中序遍歷

publicvoidinOrder(Nodep){//中序遍歷if(p!=null){inOrder(p.left);p.visited();inOrder(p.right);}}FDBEACG2024/11/9119.2遍歷二叉樹●后序遍歷FDBECGA

publicvoidpostOrder(Nodep){//后序遍歷if(p!=null){postOrder(p.left);postOrder(p.right);p.visited();}}9.3二叉樹的存儲2024/11/912二叉樹的結點的存儲方式通常為鏈式存儲，即一個結點中含有一個對象，以及左子結點和右子結點的引用。對于一個沒有增加限制的二叉樹，給出通用的添加、刪除結點的算法是不可能的，理由是在鏈式存儲的二叉樹中，要確定一個結點的位置，需要知道它的父結點和它在父結點的位置（是左子結點還是右子結點）。因此，在進行添加或刪除操作時，需要先找到要添加或刪除的結點的位置，而這個過程會涉及到一系列的判斷和遍歷操作，因而比較復雜。不同的二叉樹可能有不同的限制條件，因此沒有通用的算法適用于所有的情況。但是，對于二叉查詢樹，人么就可以給出有關的算法，見稍后的9.5節(jié)。2024/11/9139.3二叉樹的存儲Node.java例子1例子1中的BinaryTree類負責創(chuàng)建的二叉樹，其結點Node是鏈式存儲的。Example9_1.javaBinaryTree.java例子1的主類，使用BinaryTree類創(chuàng)建二叉樹，并分別使用前序、中序和后序遍歷了這棵二叉樹，同時查詢了某個對象是否和樹上的某個結點中的對象相同.9.4平衡二叉樹2024/11/914平衡二叉樹：①左子樹和右子樹深度之差的絕對值不大于1，②左子樹和右子樹也都是平衡二叉樹。

9.5二叉查詢樹2024/11/915籠統(tǒng)的二叉樹很難能形成有效算法，所以本節(jié)先給出二叉查詢樹，然后介紹兩種經(jīng)典的平衡二叉查詢樹。2024/11/9169.5二叉查詢樹●二叉查詢樹二叉查詢樹（BinarySearchTree，簡稱BST）的每個結點node都存儲一個可比較大小的對象，且滿足以下條件①node的左子樹中所有結點中的對象都小于node結點中的對象；②node的右子樹中所有結點的對象都大于等于node節(jié)點的中的對象；③左、右子樹都是二叉查詢樹。如果按中序遍歷二叉查詢樹，輸出的對象剛好是升序排列。所以也稱二叉查詢樹是有序二叉樹。按中序遍歷輸出了樹上的結點中的數(shù)據(jù)：ABCDEFG2024/11/9179.5二叉查詢樹●二叉查詢樹二叉查詢樹的任意結點中的對象大于左子結點中的對象，小于等于右子結點中的對象。但是，如果一個二叉樹的任意結點中的對象大于左子結點中的對象，小于等于右子結點中的對象，它不一定是二叉查詢樹.2024/11/9189.5二叉查詢樹Node.java例子2Example9_1.javaBinaryTree.java例子2中的主類使用例子1的BinaryTree類負責創(chuàng)建了二叉樹查詢樹，并按中序遍歷輸出了樹上的結點中的數(shù)據(jù)。2024/11/9199.5二叉查詢樹●平衡二叉查詢樹

平衡二叉查詢樹的查找操作非常類似二分法，由于是平衡二叉查詢樹，查詢過程中，結點的數(shù)目近似以2的方冪在減少，所以它的查詢時間復雜度和二分法的查詢時間復雜度相同.2024/11/9209.5二叉查詢樹Node.java例子3Example9_3.javaBinaryBST.java

平衡二叉查詢樹129231056191722282024/11/9219.5二叉查詢樹●紅黑樹紅黑樹是一種平衡的二叉搜索樹。它的平衡性質的維護主要是通過顏色標記節(jié)點等操作來達成。

Java實現(xiàn)的二叉搜索樹是紅黑樹（見稍后的TreeSet類），講解紅黑樹，內部算法細節(jié)超出了本書的范圍。2024/11/9229.5二叉查詢樹●AVL樹AVL樹是根據(jù)兩位發(fā)明者Adel’son-Velskii和Landis命名的一種平衡二叉搜索樹。

Java實現(xiàn)的二叉搜索樹是紅黑樹（見稍后的TreeSet類），講解紅黑樹，以及AVL樹的內部算法細節(jié)超出了本書的范圍。9.5TreeSet樹集2024/11/923TreeSet<E>泛型類實現(xiàn)了SortedSet接口。2024/11/9249.6TreeSet樹集創(chuàng)建一個TreeSet<E>類的對象必須要指定E的具體類型，類型是類或接口類型（不可以是基本類型，比如int、float、char等）即指定樹集的結點里的對象的類型。例如，指定E是Integer：TreeSet<Integer>treeOne=newTreeSet<>();或TreeSet<Integer>treeOne=newTreeSet<Integer>();TreeSet類不允許有兩個結點的對象相同，即大小一樣的對象。

樹集使用add(Eobj)方法向樹集添加結點。樹集使用addAll(Collection<?extendsE>c)方法添加多個結點到樹集，結點中的對象可以是參數(shù)指定的集合中的結點中的對象。2024/11/9259.6TreeSet樹集例子4Example9_4.java例子4中的主類Example9_4中首先創(chuàng)建一個空樹集treeOne，然后向空樹集treeOne添加4個節(jié)點，隨后再用treeOne創(chuàng)建樹集treeTwo。用新的大小關系創(chuàng)建treeTree，然后向treeTree添加結點，結點中的對象和treeOne的相同。9.6樹集的基本操作2024/11/926publicEfirst()返回樹集上節(jié)點值最小的節(jié)點中的對象。publicElast()返回樹集上節(jié)點值最大的節(jié)點中的對象。publicbooeleanadd(Eobj)樹集使用該方法向其添加結點，但需要注意的是，如果樹集上已經(jīng)有節(jié)點值是obj將無法將值是ob的結點添加到樹集上，此時返回false表示添加失敗。publicbooleanaddAll(Collection<?extendsE>c)樹集使用該方法向其添加多個結點，結點值可以是參數(shù)指定的集合中的結點中的對象，即c可以是鏈表，棧，隊列或另一個樹集。但需要注意的是，c中如果有相同的對象，只能有一個被添加到樹集上。2024/11/9279.7樹集的基本操作例子5RandomByTree.java

Example9_5.java雙色球的每注投注號碼由6個紅色球號碼和1個藍色球號碼組成。6個紅色球的號碼互不相同、號碼是1至33的隨機數(shù)；藍色球號碼是1至16的一個隨機數(shù)。例子5中的主類Exmple9_5使用RandomByTree類的getRandom(intnumber,intn)方法模擬雙色球。2024/11/9289.7樹集的基本操作例子6ConnectNumber.javaExample9_6.java

例子6的ConnectNumber類的intgetMaxConnectNumber(int…m)方法返回幾個正整數(shù)最大的連接數(shù)，intgetMaxConnectNumber(int…m)返回幾個正整數(shù)的最小連接數(shù)。9.8樹集的視圖2024/11/929樹集是有序集，因此，樹集的視圖也是有序集，規(guī)定視圖在添加結點時，不可以添加大于視圖中最大值的結點，也不可以添加小于視圖中最小值的結點，即對于視圖subView，subView添加的結點的節(jié)點值不能大于sunView.last()的結點值，不能小于subView.first()的結點值。publicSortedSet<E>subSet(Efrom,Eto)返回樹集的一個視圖，視圖中的結點由樹集上結點值大于等于from結點值、小于to結點值的結點所構成。如果from結點值等于to結點值，方法返回null，如果from結點值小于to結點值，會觸發(fā)運行異常：IllegalArgumentException。2024/11/9309.8樹集的視圖例子7Example9_7.java例子7的主類Example9_7獲取的樹集的視圖，查詢了視圖中的結點，并對視圖進行了添加和刪除結點的操作.樹集的視圖是樹集的一個子集，更改視圖的結點（增加或刪除節(jié)點）都會使得當前樹集發(fā)生同步的改變，同樣地，如果更改樹集的結點（增加或刪除節(jié)點），就也會使得視圖發(fā)生同步的相應的改變，即樹集的視圖和原樹集會同步變化，這也是視圖的本意。9.9樹集與數(shù)據(jù)統(tǒng)計2024/11/931

2024/11/9329.9樹集與數(shù)據(jù)統(tǒng)計例子8Example9_8.java例子8中的主類Example9_8對統(tǒng)計了隨機數(shù).9.10樹集與過濾數(shù)據(jù)2024/11/933第4章的4.3曾講過過濾數(shù)組，即去除數(shù)組中的某些數(shù)據(jù)。使用樹集來過濾數(shù)據(jù)會更加方便，而且能發(fā)揮樹集，在刪除、查詢方面的速度優(yōu)勢。經(jīng)常使用下列方法來過濾數(shù)據(jù)。publicbooleanremoveAll(Collection<?>c)刪除節(jié)點值在c里的結點publicbooleanretainAll(Collection<?>c)保留節(jié)點值在c里的結點publicbooleanremoveIf(Predicate<?superE>filter)刪除滿足filter給出的條件的結點。2024/11/9349.10樹集與過濾數(shù)據(jù)例子9Example9_9.java例子9