對(duì)于樹這個(gè)數(shù)據(jù)結(jié)構(gòu)弛针，第一次看到這個(gè)樹肯定是一臉蒙逼，瑪?shù)吕罨剩瑯湎髯拢糠N樹的那個(gè)樹么？哈哈哈掉房，當(dāng)然不是茧跋，前面我們說過數(shù)組添加、刪除數(shù)據(jù)很慢卓囚，查詢數(shù)據(jù)很快瘾杭；而鏈表添加、刪除數(shù)據(jù)很快哪亿，但是查找數(shù)據(jù)很慢粥烁，我們就想啊，有沒有一種數(shù)據(jù)結(jié)構(gòu)取二者之精華蝇棉，那不就是一個(gè)添加讨阻，刪除，查詢都很快的數(shù)據(jù)結(jié)構(gòu)嗎篡殷？那用起來多舒服岸鬯薄！

這個(gè)取二者之精華的數(shù)據(jù)結(jié)構(gòu)就是樹（tree）,而且隨著各種大佬對(duì)樹這種結(jié)構(gòu)的改進(jìn)板辽，就有了很多種樹搀绣，常見的有二叉樹，紅黑樹戳气，2-3-4樹等各種樹链患，我們就一起看看這幾種簡(jiǎn)單樹到底是什么鬼！

進(jìn)群：697699179可以獲取Java瓶您、大數(shù)據(jù)各類入門學(xué)習(xí)資料麻捻！

這是我的微信公眾號(hào)【編程study】各位大佬有空可以關(guān)注下，每天更新Java呀袱、大數(shù)據(jù)學(xué)習(xí)方法贸毕，感謝！

學(xué)習(xí)中遇到問題有不明白的地方夜赵，推薦加小編Java|大數(shù)據(jù)學(xué)習(xí)群：697699179內(nèi)有視頻教程 明棍，直播課程 ，等學(xué)習(xí)資料寇僧，期待你的加入

1.樹的基本概念

樹的基本結(jié)構(gòu)就是由一個(gè)個(gè)的節(jié)點(diǎn)組成摊腋，如下圖所示沸版，然后每一個(gè)節(jié)點(diǎn)都通過邊相連，那么有人要問了兴蒸，這些節(jié)點(diǎn)是什么笆恿浮？emmm...上篇博客實(shí)現(xiàn)了鏈表橙凳，就是類似鏈表的那個(gè)節(jié)點(diǎn)一樣的東西蕾殴，本質(zhì)上就是一個(gè)Node的實(shí)例，在這個(gè)實(shí)例中岛啸，有幾個(gè)屬性钓觉，分別幾個(gè)子節(jié)點(diǎn)和其中保存的數(shù)據(jù)；

這里注意一下坚踩，任意一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)只能有一個(gè)荡灾，子節(jié)點(diǎn)可肯能有多個(gè)；這很好理解堕虹，現(xiàn)實(shí)中，你可以有多個(gè)孩子芬首，但是你能有多個(gè)親爹嗎赴捞？？郁稍？

比如對(duì)于B節(jié)點(diǎn)來說赦政，A是父節(jié)點(diǎn)，D耀怜，E恢着，F(xiàn)都是子節(jié)點(diǎn)，而對(duì)于沒有子節(jié)點(diǎn)的那種節(jié)點(diǎn)财破，叫做葉節(jié)點(diǎn)掰派，這里的D、E左痢、F靡羡、G、H都是葉節(jié)點(diǎn)俊性；由于一切節(jié)點(diǎn)都是從A出發(fā)的略步，所以A叫做根節(jié)點(diǎn)

注：第一次看這個(gè)圖是不是不覺得像一棵樹啊，其實(shí)你要把這個(gè)圖旋轉(zhuǎn)180度定页，倒過來看就比較像一棵樹了趟薄，哈哈哈！話說用過linux操作系統(tǒng)的人應(yīng)該知道linux的各種目錄"/"就是樹結(jié)構(gòu)典徊。杭煎。恩够。

那么什么是二叉樹呢？這很簡(jiǎn)單岔帽，每個(gè)節(jié)點(diǎn)最多只能兩個(gè)子節(jié)點(diǎn)玫鸟，我們看看下圖，這就是一個(gè)二叉樹的基本結(jié)構(gòu)

根據(jù)上圖犀勒，我們說一下樹的基本術(shù)語：

路徑：從任意一個(gè)節(jié)點(diǎn)到另外任意一個(gè)節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)的順序排列就是路徑屎飘；

根節(jié)點(diǎn)：一棵樹只有一個(gè)根節(jié)點(diǎn)，要保證根到任意一個(gè)節(jié)點(diǎn)只有一條路徑贾费，否則就不是樹了钦购，比如下圖這個(gè)就不是樹

父節(jié)點(diǎn)：與當(dāng)前節(jié)點(diǎn)連接的上一層節(jié)點(diǎn)就是父節(jié)點(diǎn)

子節(jié)點(diǎn)：與當(dāng)前節(jié)點(diǎn)連接的下一層節(jié)點(diǎn)就是子節(jié)點(diǎn)

葉節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)就是葉結(jié)點(diǎn)

子樹：上圖中在樹中隨便找一個(gè)節(jié)點(diǎn)B當(dāng)作根節(jié)點(diǎn)，然后B的所有子節(jié)點(diǎn)褂萧，子節(jié)點(diǎn)的子節(jié)點(diǎn)等等就構(gòu)成了一個(gè)子樹押桃；

左/右子節(jié)點(diǎn)：由于二叉樹的每一個(gè)節(jié)點(diǎn)都只有兩個(gè)節(jié)點(diǎn)，于是左邊的子節(jié)點(diǎn)叫做左子節(jié)點(diǎn)导犹，右邊的就叫做右子節(jié)點(diǎn)唱凯；

2.二叉搜索樹

什么是二叉搜索樹呢？其實(shí)就是一種特殊的二叉樹谎痢，只是我們向其中添加數(shù)據(jù)的時(shí)候定義了一種規(guī)則磕昼，比如下圖B中存了數(shù)據(jù)20，現(xiàn)在我們要添加數(shù)據(jù)10和30节猿，應(yīng)該怎么放呢票从？我們將小于20的數(shù)據(jù)放在左子節(jié)點(diǎn)，大于20的數(shù)據(jù)放在右子節(jié)點(diǎn)滨嘱，這就是二叉搜索樹峰鄙，樹如其名，搜索起來特別快太雨；

順便提一下平衡樹和非平衡樹吟榴，數(shù)據(jù)在左右子節(jié)點(diǎn)中分布比較平均就是平衡樹，不怎么平均的就是非平衡樹囊扳，下圖所示煤墙，76這個(gè)節(jié)點(diǎn)只有一個(gè)右子節(jié)點(diǎn)，而且還連著這么多數(shù)據(jù)宪拥，有點(diǎn)不平衡....

下面我們簡(jiǎn)單用java代碼來表示樹的節(jié)點(diǎn)（還是用靜態(tài)內(nèi)部類的形式）：

2.1.添加節(jié)點(diǎn)

添加節(jié)點(diǎn)的時(shí)候要準(zhǔn)備兩個(gè)指針仿野，parentNode=null和current=root,首先我們要判斷root是不是為null，如果是的話直接將我們要添加的節(jié)點(diǎn)newNode放到第一個(gè)節(jié)點(diǎn)就ok了她君；

假如有root節(jié)點(diǎn)之后再要添加新的節(jié)點(diǎn)脚作，先讓parentNode指向current節(jié)點(diǎn)（就是root節(jié)點(diǎn)），current這個(gè)指針指向哪里就必須要判斷newNode和root中數(shù)據(jù)的大小，如果newNode大球涛，則current就指向左子節(jié)點(diǎn)劣针，反之則指向右子節(jié)點(diǎn)；同時(shí)會(huì)判斷左子結(jié)點(diǎn)或者右子節(jié)點(diǎn)是否存在亿扁，不存在的話直接將newNode放到該位置即可捺典，存在的話繼續(xù)執(zhí)行while循環(huán)；具體代碼如下：

publicbooleanadd(intvalue){? ? ? ? Node newNode =newNode(value);if(root==null) {? ? ? ? ? ? root = newNode;returntrue;? ? ? ? }else{? ? ? ? ? ? Node parentNode =null;? ? ? ? ? ? Node current = root;while(current!=null){? ? ? ? ? ? ? ? parentNode = current;if(value

2.2.遍歷樹

我們要查看一下樹中的所有節(jié)點(diǎn)中的數(shù)據(jù)从祝，就需要我們實(shí)現(xiàn)對(duì)樹中所有節(jié)點(diǎn)的遍歷襟己，這個(gè)遍歷方式有很多種，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)牍陌，可想而知最容易想到的方式就是遞歸擎浴；

最常見的三種遍歷方式：前序、中序毒涧、后序贮预，其中重點(diǎn)是中序，最后會(huì)按照從小到大的順序打印出來：

前序：根節(jié)點(diǎn)-----左子樹-------右子樹

中序：左子樹-----根節(jié)點(diǎn)--------右子樹

后序：右子樹-------根節(jié)點(diǎn)--------左子樹

三種方式分別用代碼來實(shí)現(xiàn)為?契讲，?最重要的是中序?仿吞；

//中序遍歷publicvoidinfixOrder(Node current){if(current !=null){? ? ? ? infixOrder(current.leftChild);? ? ? ? System.out.print(current.key+" ");? ? ? ? infixOrder(current.rightChild);? ? }}//前序遍歷publicvoidpreOrder(Node current){if(current !=null){? ? ? ? System.out.print(current.key+" ");? ? ? ? preOrder(current.leftChild);? ? ? ? preOrder(current.rightChild);? ? }}//后序遍歷publicvoidpostOrder(Node current){if(current !=null){? ? ? ? postOrder(current.leftChild);? ? ? ? postOrder(current.rightChild);? ? ? ? System.out.print(current.key+" ");? ? }}

好好想想這里中序的遞歸。捡偏。唤冈。。

2.3.查找節(jié)點(diǎn)

比如下面這個(gè)圖中要查找57這個(gè)節(jié)點(diǎn)是否存在霹琼，我們首先將57比63小务傲，我們就把57和左子結(jié)點(diǎn)27比較凉当，57大枣申；然后57在和51比較，再就是和58比較看杭，小于58再和左子結(jié)點(diǎn)57比較忠藤，相等的話就返回這個(gè)57的節(jié)點(diǎn)

用代碼來實(shí)現(xiàn)原理：

publicNodefind(Integervalue){? ? ? ? Node current = root;while(current!=null){if(valuecurrent.key){? ? ? ? ? ? ? ? current = current.rightChild;? ? ? ? ? ? }else{returncurrent;? ? ? ? ? ? }? ? ? ? }returnnull;? ? }

2.4.最大值和最小值

假如我們要找樹中的最大值和最小值還是很容易的，因?yàn)闃渲械臄?shù)據(jù)都是按照了規(guī)則放的楼雹，最小值應(yīng)該就是最左邊的子節(jié)點(diǎn)模孩，最大值應(yīng)該就是最右邊的字節(jié)點(diǎn)，我們也用代碼來看看：

//查詢樹中最大值publicNode findMax(){? ? ? ? Node current = root;? ? ? ? Node max=null;while(current!=null){? ? ? ? ? ? max = current;? ? ? ? ? ? current = current.leftChild;? ? ? ? }returnmax;? ? }//查詢書中最小值publicNode findMin(){? ? ? ? Node current = root;? ? ? ? Node min =null;while(current!=null){? ? ? ? ? ? min = current;? ? ? ? ? ? current = current.rightChild;? ? ? ? }returnmin;? ? }

這里的max和min兩個(gè)指針比較關(guān)鍵贮缅，因?yàn)楫?dāng)跳出while循環(huán)的時(shí)候榨咐，curent肯定是為null，但是我們想要打印出這個(gè)current的父節(jié)點(diǎn)谴供，于是我們可以用這兩個(gè)指著保存一下块茁；

其實(shí)到這里一個(gè)樹的基本結(jié)構(gòu)和功能就差不多了，可以自己測(cè)試一下；

2.5.刪除節(jié)點(diǎn)

刪除節(jié)點(diǎn)最后說数焊，為什么呢永淌？因?yàn)閯h除節(jié)點(diǎn)最復(fù)雜，你想啊佩耳，節(jié)點(diǎn)是分為很多種的遂蛀，假如刪除的是葉節(jié)點(diǎn)那很容易，直接將這個(gè)葉節(jié)點(diǎn)的父節(jié)點(diǎn)對(duì)它的引用變?yōu)閚ull就行了干厚，但假如要?jiǎng)h除的節(jié)點(diǎn)是中間的節(jié)點(diǎn)呢李滴？這就比較麻煩了，這個(gè)中間節(jié)點(diǎn)又分為有一個(gè)子節(jié)點(diǎn)萍诱，兩個(gè)子節(jié)點(diǎn)悬嗓，對(duì)于有一個(gè)子節(jié)點(diǎn)的很好處理，但是兩個(gè)子節(jié)點(diǎn)的就最麻煩裕坊！

我們重點(diǎn)看看第三個(gè)圖包竹，刪除的節(jié)點(diǎn)又兩個(gè)子節(jié)點(diǎn)的時(shí)候，肯定要想一個(gè)新的節(jié)點(diǎn)去代替那個(gè)6節(jié)點(diǎn)籍凝，使得整個(gè)樹不破壞結(jié)構(gòu)周瞎，還是可以正常使用，這種方式叫做找后繼節(jié)點(diǎn)饵蒂，顧名思義就是找6那個(gè)節(jié)點(diǎn)后面的節(jié)點(diǎn)來代替6節(jié)點(diǎn)声诸，而且必須是6節(jié)點(diǎn)的右子節(jié)點(diǎn)（想象為什么呢?），我們慢慢看有哪幾種后繼節(jié)點(diǎn)滿足要求退盯；

第一種：被刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)的左節(jié)點(diǎn)彼乌，下圖所示的30就滿足條件啊渊迁；而且這給了我們一個(gè)啟發(fā)慰照，這種的后繼節(jié)點(diǎn)就是找一個(gè)比被刪除節(jié)點(diǎn)大一點(diǎn)點(diǎn)的節(jié)點(diǎn)；換句話來說琉朽，就是在被刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)中找最小的節(jié)點(diǎn)毒租；

第二種：被刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)只有一個(gè)右子節(jié)點(diǎn)，說起來很繞箱叁，看圖墅垮，我們直接將35作為新的節(jié)點(diǎn)放在被刪除節(jié)點(diǎn)25的位置就可以了，其他的不動(dòng)耕漱；

現(xiàn)在我們總結(jié)一下刪除節(jié)點(diǎn)所需要的重點(diǎn)：

（1）.刪除的節(jié)點(diǎn)是葉節(jié)點(diǎn)算色，我們找到該葉節(jié)點(diǎn)的父節(jié)點(diǎn)，修改父節(jié)點(diǎn)指向葉結(jié)點(diǎn)的引用為null即可螟够；

（2）.刪除的節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)

2.1.這個(gè)子節(jié)點(diǎn)是左子結(jié)點(diǎn)

2.2.這個(gè)子節(jié)點(diǎn)是右子節(jié)點(diǎn)

（3）.刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)灾梦，這種就要找后繼節(jié)點(diǎn)來補(bǔ)上被刪除節(jié)點(diǎn)的那個(gè)位置，防止樹的結(jié)構(gòu)被破壞，找后繼節(jié)點(diǎn)就是找被刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)中最小的值

3.1.被刪除的節(jié)點(diǎn)的右子節(jié)點(diǎn)只有右子節(jié)點(diǎn)的話斥废，就直接將右子節(jié)點(diǎn)變?yōu)楹罄^節(jié)點(diǎn)椒楣；

3.2.被刪除的節(jié)點(diǎn)的右子節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)的話，找這兩個(gè)子節(jié)點(diǎn)中的最小值即可牡肉；即使這兩個(gè)子節(jié)點(diǎn)后面還有子節(jié)點(diǎn)捧灰，也是一樣的找最小值

既然思路已經(jīng)理清楚了，那就用代碼來表達(dá)出來统锤，比較多：

//根據(jù)數(shù)據(jù)刪除對(duì)應(yīng)的節(jié)點(diǎn)publicboolean delete(int value){? ? ? ? Nodeparent=null;? ? ? ? Node current = root;? ? ? ? Boolean isLeftChild =null;//當(dāng)根節(jié)點(diǎn)不存在的時(shí)候毛俏，執(zhí)行刪除操作會(huì)拋出異常if(root==null) {try{thrownewException("樹中沒有數(shù)據(jù)，你刪除空氣八橇煌寇！");? ? ? ? ? ? }catch(Exceptione) {? ? ? ? ? ? ? ? e.printStackTrace();? ? ? ? ? ? }returnfalse;? ? ? ? }//這里只是移動(dòng)了parent和current的指針，首先是判斷節(jié)點(diǎn)是在根節(jié)點(diǎn)的左邊還是右邊逾雄，確定了之后再慢慢往下找阀溶，最后將current移動(dòng)到被刪除的節(jié)點(diǎn)那里，//后面我們就可以通過current這個(gè)指針獲取刪除節(jié)點(diǎn)的信息;//如果最后current==null了鸦泳，說明最后沒有找到該節(jié)點(diǎn)银锻，就返回falsewhile(value!=current.key){parent= current;if(value

所有的邏輯就這么多，我們可以把所有的代碼整理一下做鹰，并且測(cè)試一下結(jié)果击纬，成功；

package com.wyq.test;import com.wyq.test.MyTree.Node;publicclassMyTree{privateNode root;publicstaticclassNode{privateInteger key;//節(jié)點(diǎn)中存的數(shù)據(jù)privateNode leftChild;//左子結(jié)點(diǎn)privateNode rightChild;//右子節(jié)點(diǎn)publicNode(Integer key){this.key = key;this.leftChild =null;this.rightChild =null;? ? ? ? }publicvoiddisplayNode(){? ? ? ? ? ? System.out.println("{"+key+"}");? ? ? ? }? ? }publicbooleanadd(intvalue){? ? ? ? Node newNode =newNode(value);if(root==null) {? ? ? ? ? ? root = newNode;returntrue;? ? ? ? }else{? ? ? ? ? ? Node parentNode =null;? ? ? ? ? ? Node current = root;while(current!=null){? ? ? ? ? ? ? ? parentNode = current;if(valuecurrent.key){? ? ? ? ? ? ? ? current = current.rightChild;? ? ? ? ? ? }else{returncurrent;? ? ? ? ? ? }? ? ? ? }returnnull;? ? }//查詢樹中最大值publicNodefindMax(){? ? ? ? Node current = root;? ? ? ? Node max=null;while(current!=null){? ? ? ? ? ? max = current;? ? ? ? ? ? current = current.leftChild;? ? ? ? }returnmax;? ? }//查詢書中最小值publicNodefindMin(){? ? ? ? Node current = root;? ? ? ? Node min =null;while(current!=null){? ? ? ? ? ? min = current;? ? ? ? ? ? current = current.rightChild;? ? ? ? }returnmin;? ? }//根據(jù)數(shù)據(jù)刪除對(duì)應(yīng)的節(jié)點(diǎn)publicbooleandelete(intvalue){? ? ? ? Node parent =null;? ? ? ? Node current = root;? ? ? ? Boolean isLeftChild =null;//當(dāng)根節(jié)點(diǎn)不存在的時(shí)候钾麸，執(zhí)行刪除操作會(huì)拋出異常if(root==null) {try{thrownewException("樹中沒有數(shù)據(jù)更振，你刪除空氣啊饭尝！");? ? ? ? ? ? }catch(Exception e) {? ? ? ? ? ? ? ? e.printStackTrace();? ? ? ? ? ? }returnfalse;? ? ? ? }//這里只是移動(dòng)了parent和current的指針肯腕，首先是判斷節(jié)點(diǎn)是在根節(jié)點(diǎn)的左邊還是右邊，確定了之后再慢慢往下找芋肠，最后將current移動(dòng)到被刪除的節(jié)點(diǎn)那里乎芳，//后面我們就可以通過current這個(gè)指針獲取刪除節(jié)點(diǎn)的信息;//如果最后current==null了遵蚜，說明最后沒有找到該節(jié)點(diǎn)帖池，就返回falsewhile(value!=current.key){? ? ? ? ? ? parent = current;if(value

3.關(guān)于刪除數(shù)據(jù)的一點(diǎn)思考

上面的刪除方法可謂是很長(zhǎng)而且邏輯很容易弄混，那有沒有方法避免這種有點(diǎn)坑的東西呢吭净？

于是啊睡汹，我們就想到一個(gè)辦法，我們把刪除節(jié)點(diǎn)不是真的刪除寂殉，是邏輯刪除囚巴；比如相當(dāng)于給這個(gè)節(jié)點(diǎn)添加一個(gè)屬性isDelete，這個(gè)狀態(tài)默認(rèn)為false表示這是一個(gè)正常的節(jié)點(diǎn)，如果我們要?jiǎng)h除某個(gè)節(jié)點(diǎn)彤叉，只需要把isDelete變?yōu)閠rue庶柿，代表著這個(gè)節(jié)點(diǎn)已經(jīng)不屬于這個(gè)樹了，這種做法的好處就是不會(huì)改變這個(gè)樹的結(jié)構(gòu)秽浇，可以想想這種做法和之前刪除的做法的區(qū)別浮庐；但是壞處也很明顯，就是刪除的節(jié)點(diǎn)也會(huì)保存在樹中柬焕，當(dāng)這種刪除的操作很多的時(shí)候审残，樹中就保存了太多垃圾數(shù)據(jù)了，所以看情況使用斑举。搅轿。。

4.關(guān)于節(jié)點(diǎn)中數(shù)據(jù)的一點(diǎn)改進(jìn)

有沒有看到我們上面實(shí)現(xiàn)的樹中的節(jié)點(diǎn)中保存的數(shù)據(jù)都是數(shù)字啊富玷，為什么呢璧坟？因?yàn)楹?jiǎn)單唄，很容易理解赎懦，如果把樹中節(jié)點(diǎn)的數(shù)據(jù)換成對(duì)象其實(shí)也是行的沸柔，比如下面這樣的：

如果是這樣的話，我們添加數(shù)據(jù)就必須要按照User對(duì)象的某個(gè)屬性（比如id）為關(guān)鍵字進(jìn)行比較铲敛，然后向樹中插入數(shù)據(jù)褐澎，其實(shí)跟我們用Integer尅行的差不多，只是寫起來代碼看起來不夠簡(jiǎn)潔伐蒋；

下圖選取部分代碼進(jìn)行修改：

5.總結(jié)

樹這種數(shù)據(jù)結(jié)構(gòu)還是挺厲害的工三，雜糅了數(shù)組和鏈表的有點(diǎn)于一身，查找數(shù)據(jù)很快先鱼，增加和刪除數(shù)據(jù)也很快俭正，但就是特么的理解其中的邏輯需要一點(diǎn)點(diǎn)時(shí)間去慢慢啃。焙畔。掸读。。宏多。后面還有各種樹!

下一篇應(yīng)該是紅黑樹了儿惫，加油加油！.