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

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

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

2024/11/969.1二叉樹的基本概念●完全二叉樹(CompleteBinaryTree)完全二叉樹從根結(jié)點到倒數(shù)第二層的結(jié)點數(shù)目都是滿的，最后一層可以不滿，但最后一層葉子結(jié)點都是靠左對齊（按最后一層從左向右的序號，一個挨著一個靠左對齊），并且從左向右數(shù)，只允許最后一個葉子結(jié)點可以沒有兄弟結(jié)點，而且如果最后一個葉子結(jié)點沒有兄弟結(jié)點的話，它必須是左子結(jié)點。2024/11/979.1二叉樹的基本概念●樹的高度與深度一個葉結(jié)點所在的層的層數(shù)加1（層是從0開始的，只有一個根結(jié)點的二叉樹高度為1，規(guī)定空二叉樹的高度是0），稱作這個葉節(jié)點的高度，所有葉節(jié)點中，其高度最大者稱為二叉樹的高度.從根結(jié)點（包括根結(jié)點）按照父子關(guān)系找到一個葉結(jié)點所經(jīng)歷過的結(jié)點（包括葉結(jié)點）數(shù)目，稱作這個葉結(jié)點的深度。所有葉節(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二叉樹的結(jié)點的存儲方式通常為鏈式存儲，即一個結(jié)點中含有一個對象，以及左子結(jié)點和右子結(jié)點的引用。對于一個沒有增加限制的二叉樹，給出通用的添加、刪除結(jié)點的算法是不可能的，理由是在鏈式存儲的二叉樹中，要確定一個結(jié)點的位置，需要知道它的父結(jié)點和它在父結(jié)點的位置（是左子結(jié)點還是右子結(jié)點）。因此，在進行添加或刪除操作時，需要先找到要添加或刪除的結(jié)點的位置，而這個過程會涉及到一系列的判斷和遍歷操作，因而比較復(fù)雜。不同的二叉樹可能有不同的限制條件，因此沒有通用的算法適用于所有的情況。但是，對于二叉查詢樹，人么就可以給出有關(guān)的算法，見稍后的9.5節(jié)。2024/11/9139.3二叉樹的存儲Node.java例子1例子1中的BinaryTree類負責創(chuàng)建的二叉樹，其結(jié)點Node是鏈式存儲的。Example9_1.javaBinaryTree.java例子1的主類，使用BinaryTree類創(chuàng)建二叉樹，并分別使用前序、中序和后序遍歷了這棵二叉樹，同時查詢了某個對象是否和樹上的某個結(jié)點中的對象相同.9.4平衡二叉樹2024/11/914平衡二叉樹：①左子樹和右子樹深度之差的絕對值不大于1，②左子樹和右子樹也都是平衡二叉樹。

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

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

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

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

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

樹集使用add(Eobj)方法向樹集添加結(jié)點。樹集使用addAll(Collection<?extendsE>c)方法添加多個結(jié)點到樹集，結(jié)點中的對象可以是參數(shù)指定的集合中的結(jié)點中的對象。2024/11/9259.6TreeSet樹集例子4Example9_4.java例子4中的主類Example9_4中首先創(chuàng)建一個空樹集treeOne，然后向空樹集treeOne添加4個節(jié)點，隨后再用treeOne創(chuàng)建樹集treeTwo。用新的大小關(guān)系創(chuàng)建treeTree，然后向treeTree添加結(jié)點，結(jié)點中的對象和treeOne的相同。9.6樹集的基本操作2024/11/926publicEfirst()返回樹集上節(jié)點值最小的節(jié)點中的對象。publicElast()返回樹集上節(jié)點值最大的節(jié)點中的對象。publicbooeleanadd(Eobj)樹集使用該方法向其添加結(jié)點，但需要注意的是，如果樹集上已經(jīng)有節(jié)點值是obj將無法將值是ob的結(jié)點添加到樹集上，此時返回false表示添加失敗。publicbooleanaddAll(Collection<?extendsE>c)樹集使用該方法向其添加多個結(jié)點，結(jié)點值可以是參數(shù)指定的集合中的結(jié)點中的對象，即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ī)定視圖在添加結(jié)點時，不可以添加大于視圖中最大值的結(jié)點，也不可以添加小于視圖中最小值的結(jié)點，即對于視圖subView，subView添加的結(jié)點的節(jié)點值不能大于sunView.last()的結(jié)點值，不能小于subView.first()的結(jié)點值。publicSortedSet<E>subSet(Efrom,Eto)返回樹集的一個視圖，視圖中的結(jié)點由樹集上結(jié)點值大于等于from結(jié)點值、小于to結(jié)點值的結(jié)點所構(gòu)成。如果from結(jié)點值等于to結(jié)點值，方法返回null，如果from結(jié)點值小于to結(jié)點值，會觸發(fā)運行異常：IllegalArgumentException。2024/11/9309.8樹集的視圖例子7Example9_7.java例子7的主類Example9_7獲取的樹集的視圖，查詢了視圖中的結(jié)點，并對視圖進行了添加和刪除結(jié)點的操作.樹集的視圖是樹集的一個子集，更改視圖的結(jié)點（增加或刪除節(jié)點）都會使得當前樹集發(fā)生同步的改變，同樣地，如果更改樹集的結(jié)點（增加或刪除節(jié)點），就也會使得視圖發(fā)生同步的相應(yīng)的改變，即樹集的視圖和原樹集會同步變化，這也是視圖的本意。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里的結(jié)點publicbooleanretainAll(Collection<?>c)保留節(jié)點值在c里的結(jié)點publicbooleanremoveIf(Predicate<?superE>filter)刪除滿足filter給出的條件的結(jié)點。2024/11/9349.10樹集與過濾數(shù)據(jù)例子9Example9_9.java例子9