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

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

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

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二叉樹的存儲(chǔ)2024/11/912二叉樹的結(jié)點(diǎn)的存儲(chǔ)方式通常為鏈?zhǔn)酱鎯?chǔ)，即一個(gè)結(jié)點(diǎn)中含有一個(gè)對(duì)象，以及左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的引用。對(duì)于一個(gè)沒有增加限制的二叉樹，給出通用的添加、刪除結(jié)點(diǎn)的算法是不可能的，理由是在鏈?zhǔn)酱鎯?chǔ)的二叉樹中，要確定一個(gè)結(jié)點(diǎn)的位置，需要知道它的父結(jié)點(diǎn)和它在父結(jié)點(diǎn)的位置（是左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)）。因此，在進(jìn)行添加或刪除操作時(shí)，需要先找到要添加或刪除的結(jié)點(diǎn)的位置，而這個(gè)過程會(huì)涉及到一系列的判斷和遍歷操作，因而比較復(fù)雜。不同的二叉樹可能有不同的限制條件，因此沒有通用的算法適用于所有的情況。但是，對(duì)于二叉查詢樹，人么就可以給出有關(guān)的算法，見稍后的9.5節(jié)。2024/11/9139.3二叉樹的存儲(chǔ)Node.java例子1例子1中的BinaryTree類負(fù)責(zé)創(chuàng)建的二叉樹，其結(jié)點(diǎn)Node是鏈?zhǔn)酱鎯?chǔ)的。Example9_1.javaBinaryTree.java例子1的主類，使用BinaryTree類創(chuàng)建二叉樹，并分別使用前序、中序和后序遍歷了這棵二叉樹，同時(shí)查詢了某個(gè)對(duì)象是否和樹上的某個(gè)結(jié)點(diǎn)中的對(duì)象相同.9.4平衡二叉樹2024/11/914平衡二叉樹：①左子樹和右子樹深度之差的絕對(duì)值不大于1，②左子樹和右子樹也都是平衡二叉樹。

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

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

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

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

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

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

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

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

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