資訊專欄INFORMATION COLUMN
摘要：在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)?yīng)樹(shù)結(jié)構(gòu)來(lái)說(shuō)二叉樹(shù)是最常用的一種樹(shù)結(jié)構(gòu)，二叉樹(shù)具有一個(gè)唯一的根節(jié)點(diǎn)，也就是最上面的節(jié)點(diǎn)。二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子，一個(gè)孩子都沒(méi)有的節(jié)點(diǎn)通常稱之為葉子節(jié)點(diǎn)，二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有一個(gè)父親，根節(jié)點(diǎn)是沒(méi)有父親節(jié)點(diǎn)的。
前言
【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)，全部文章大概的內(nèi)容如下：
Arrays(數(shù)組)、Stacks(棧)、Queues(隊(duì)列)、LinkedList(鏈表)、Recursion(遞歸思想)、BinarySearchTree(二分搜索樹(shù))、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(優(yōu)先隊(duì)列)、SegmentTree(線段樹(shù))、Trie(字典樹(shù))、UnionFind(并查集)、AVLTree(AVL 平衡樹(shù))、RedBlackTree(紅黑平衡樹(shù))、HashTable(哈希表)
源代碼有三個(gè)：ES6（單個(gè)單個(gè)的 class 類型的 js 文件） | JS + HTML（一個(gè) js 配合一個(gè) html）| JAVA (一個(gè)一個(gè)的工程)
全部源代碼已上傳 github，點(diǎn)擊我吧，光看文章能夠掌握兩成，動(dòng)手敲代碼、動(dòng)腦思考、畫(huà)圖才可以掌握八成。
本文章適合 對(duì)數(shù)據(jù)結(jié)構(gòu)想了解并且感興趣的人群，文章風(fēng)格一如既往如此，就覺(jué)得手機(jī)上看起來(lái)比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時(shí)間跨度也算將近半年時(shí)間了，希望對(duì)想學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人或者正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人群有幫助。
樹(shù)結(jié)構(gòu)
線性數(shù)據(jù)結(jié)構(gòu)是把所有的數(shù)據(jù)排成一排
樹(shù)結(jié)構(gòu)是倒立的樹(shù)，由一個(gè)根節(jié)點(diǎn)延伸出很多新的分支節(jié)點(diǎn)。
樹(shù)結(jié)構(gòu)本身是一個(gè)種天然的組織結(jié)構(gòu)
如 電腦中文件夾目錄結(jié)構(gòu)就是樹(shù)結(jié)構(gòu)
這種結(jié)構(gòu)來(lái)源于生活，
比如 圖書(shū)館整體分成幾個(gè)大館，
如 數(shù)理館、文史館等等，
到了數(shù)理館還要分成 很多的子類，
如 數(shù)學(xué)類的圖書(shū)、物理類的圖書(shū)、化學(xué)類的圖書(shū)，計(jì)算機(jī)類的圖書(shū)，
到了計(jì)算機(jī)類的圖書(shū)還要再分成各種不同的子類，
如 按語(yǔ)言分類 c++、java、c#、php、python 等等，
如 按領(lǐng)域分類 網(wǎng)站編程、app 開(kāi)發(fā)、游戲開(kāi)發(fā)、前端、后端等等，
每一個(gè)子領(lǐng)域可能又要分成很多領(lǐng)域，
一直到最后索引到一本一本的書(shū)，
這就是一個(gè)典型的樹(shù)結(jié)構(gòu)。
還有 一個(gè)公司的組織架構(gòu)也是這樣的一種樹(shù)結(jié)構(gòu)，
從 CEO 開(kāi)始下面可能有不同的部門(mén)，
如財(cái)務(wù)部門(mén)(Marketing Head)、人事部門(mén)(HR Head)、
技術(shù)部門(mén)(Finance Head)、市場(chǎng)部門(mén)(Audit Officer)等等，
每個(gè)部門(mén)下面還有不同的職能分工，最后才到具體的一個(gè)一個(gè)人。
還有家譜，他本身也是一個(gè)樹(shù)結(jié)構(gòu)，
其實(shí)樹(shù)結(jié)構(gòu)并不抽象，在生活中隨處可見(jiàn)。
樹(shù)結(jié)構(gòu)非常的高效
比如文件管理，
不可能將所有的文件放到一個(gè)文件夾中，
然后用一個(gè)線性的結(jié)構(gòu)進(jìn)行存儲(chǔ)，
那樣的話查找文件太麻煩了，
但是如果給它做成樹(shù)機(jī)構(gòu)的話，
那么就可以很容易的檢索到目標(biāo)文件，
比如說(shuō)我想檢索到我的照片，
直接找到個(gè)人文件夾，然后找到圖片文件夾，
最后找到自己的照片，這樣就很快速很高效的找到了目標(biāo)文件。
在公司使用這種樹(shù)形的組織架構(gòu)也是這個(gè)原因，
CEO 想就技術(shù)開(kāi)發(fā)的一些問(wèn)題進(jìn)行一些討論，
他肯定要找相應(yīng)職能的一些人，
他不需要去市場(chǎng)部門(mén)、營(yíng)銷部門(mén)、人事部門(mén)、財(cái)務(wù)部門(mén)、行政部門(mén)找人，
他直接去技術(shù)部這樣的開(kāi)發(fā)部門(mén)去找人就好了，
一下子就把查詢的范圍縮小了。
在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域設(shè)計(jì)樹(shù)結(jié)構(gòu)的本質(zhì)也是如此。
在計(jì)算機(jī)科學(xué)領(lǐng)域很多問(wèn)題的處理
當(dāng)你將數(shù)據(jù)使用樹(shù)結(jié)構(gòu)進(jìn)行存儲(chǔ)后，出奇的高效。
二分搜索樹(shù)（Binary Search Tree）
二分搜索樹(shù)有它的局限性
平衡二叉樹(shù)：AVL;紅黑樹(shù)，
平衡二叉樹(shù)還有很多種
算法需要使用一些特殊的操作的時(shí)候?qū)?shù)據(jù)組織成樹(shù)結(jié)構(gòu)
會(huì)針對(duì)某一類特殊的操作產(chǎn)生非常高效的結(jié)果，
使用堆以及并查集，
都是為了滿足對(duì)數(shù)據(jù)某一個(gè)類特殊的操作進(jìn)行高效的處理，
同時(shí)對(duì)于某些特殊的數(shù)據(jù)，很多時(shí)候可以另辟蹊徑，
將他們以某種形式存儲(chǔ)成樹(shù)結(jié)構(gòu)，
結(jié)果就是會(huì)對(duì)這類特殊的數(shù)據(jù)
它們所在的那個(gè)領(lǐng)域的問(wèn)題
相應(yīng)的解決方案提供極其高效的結(jié)果。
線段樹(shù)、Trie(字典樹(shù)、前綴樹(shù))
線段樹(shù)主要用來(lái)處理線段這種特殊的數(shù)據(jù)，
Trie 主要用于處理字符串這類特殊的數(shù)據(jù)，
要想實(shí)現(xiàn)快速搜索的算法，
它的本質(zhì)依然是需要使用樹(shù)結(jié)構(gòu)的，
樹(shù)結(jié)構(gòu)不見(jiàn)得是顯式的展示在你面前，
它同時(shí)也可以用來(lái)處理很多抽象的問(wèn)題，
這就像棧的應(yīng)用一樣，
從用戶的角度看只看撤銷這個(gè)操作或者只看括號(hào)匹配的操作，
用戶根本想不到這背后使用了一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)，
但是為了組建出這樣的功能是需要使用這種數(shù)據(jù)結(jié)構(gòu)的，
同理樹(shù)也是如此，很多看起來(lái)非常高效的運(yùn)算結(jié)果，
它的背后其實(shí)是因?yàn)橛袠?shù)這種數(shù)據(jù)結(jié)構(gòu)作為支撐的，
這也是數(shù)據(jù)結(jié)構(gòu)、包括數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)領(lǐng)域非常重要的意義，
數(shù)據(jù)結(jié)構(gòu)雖然解決的是數(shù)據(jù)存儲(chǔ)的問(wèn)題，
但是在使用的層面上不僅僅是因?yàn)橐鎯?chǔ)數(shù)據(jù)，
更重要的是在你使用某些特殊的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)后，
可以幫助你輔助你更加高效的解決某些算法問(wèn)題
甚至對(duì)于某些問(wèn)題來(lái)說(shuō)如果沒(méi)有這些數(shù)據(jù)結(jié)構(gòu)，
那么根本無(wú)從解決。
二分搜索樹(shù)(Binary Search Tree)
二叉樹(shù)
和鏈表一樣，也屬于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，
不需要?jiǎng)?chuàng)建這個(gè)數(shù)據(jù)結(jié)構(gòu)的時(shí)候就定好存儲(chǔ)的容量，
如果要添加元素，直接 new 一個(gè)新的空間，
然后把它添加到這個(gè)數(shù)據(jù)結(jié)構(gòu)中，刪除也是同理，
每一個(gè)元素也是存到一個(gè)節(jié)點(diǎn)中，
這個(gè)節(jié)點(diǎn)和鏈表不同，它除了要存放這個(gè)元素 e，
它還有兩個(gè)指向其它節(jié)點(diǎn)的變量，分別叫做 left、right，
class Node {
E e;
Node left;
Node right;
}
二叉樹(shù)也叫多叉樹(shù)，
它每一個(gè)節(jié)點(diǎn)最多只能分成兩個(gè)叉，
根據(jù)這個(gè)定義也能定義出多叉樹(shù)，
如果每個(gè)節(jié)點(diǎn)可以分出十個(gè)叉，
那就可以叫它十叉樹(shù)，能分多少叉就叫多少叉樹(shù)，
Trie 字典書(shū)本身就是一個(gè)多叉樹(shù)。
在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)?yīng)樹(shù)結(jié)構(gòu)來(lái)說(shuō)
二叉樹(shù)是最常用的一種樹(shù)結(jié)構(gòu)，
二叉樹(shù)具有一個(gè)唯一的根節(jié)點(diǎn)，
也就是最上面的節(jié)點(diǎn)。
每一個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，
這兩個(gè)子節(jié)點(diǎn)分別叫做這個(gè)節(jié)點(diǎn)的左孩子和右孩子，
子節(jié)點(diǎn)指向左邊的那個(gè)節(jié)點(diǎn)就是左孩子，
子節(jié)點(diǎn)指向右邊的那個(gè)節(jié)點(diǎn)就是右孩子。
二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子，
一個(gè)孩子都沒(méi)有的節(jié)點(diǎn)通常稱之為葉子節(jié)點(diǎn)，
二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有一個(gè)父親，
根節(jié)點(diǎn)是沒(méi)有父親節(jié)點(diǎn)的。
二叉樹(shù)和鏈表一樣具有天然遞歸的結(jié)構(gòu)
鏈表本身是線性的，
它的操作既可以使用循環(huán)也可以使用遞歸。
和樹(shù)相關(guān)的很多操作，
使用遞歸的方式去寫(xiě)要比使用非遞歸的方式簡(jiǎn)單很多。
二叉樹(shù)每一個(gè)節(jié)點(diǎn)的左孩子同時(shí)也是一個(gè)二叉樹(shù)的根節(jié)點(diǎn)，
通常叫管這棵二叉樹(shù)做左子樹(shù)。
二叉樹(shù)每一個(gè)節(jié)點(diǎn)的右孩子同時(shí)也是一個(gè)二叉樹(shù)的根節(jié)點(diǎn)，
通常叫管這棵二叉樹(shù)做右子樹(shù)。
也就是說(shuō)每一個(gè)二叉樹(shù)它的左側(cè)和右側(cè)右分別連接了兩個(gè)二叉樹(shù)，
這兩個(gè)二叉樹(shù)都是節(jié)點(diǎn)個(gè)數(shù)更小的二叉樹(shù)，
這就是二叉樹(shù)所具有的天然的遞歸結(jié)構(gòu)。
二叉樹(shù)不一定是“滿”的
滿二叉樹(shù)就是除了葉子節(jié)點(diǎn)之外，
每一個(gè)節(jié)點(diǎn)都有兩個(gè)孩子。
就算你整個(gè)二叉樹(shù)上只有一個(gè)節(jié)點(diǎn)，
它也是一個(gè)二叉樹(shù)，只不過(guò)它的左右孩子都是空，
這棵二叉樹(shù)只有一個(gè)根節(jié)點(diǎn)，
甚至 NULL(空)也是一棵二叉樹(shù)。
就像鏈表中，只有一個(gè)節(jié)點(diǎn)它也是一個(gè)鏈表，
也可以把 NULL(空)看作是一個(gè)鏈表。
二分搜索樹(shù)是一棵二叉樹(shù)
在二叉樹(shù)定義下所有其它的術(shù)語(yǔ)在二分搜索樹(shù)中也適用，
如 根節(jié)點(diǎn)、葉子節(jié)點(diǎn)、左孩子右孩子、左子樹(shù)、右子樹(shù)、
父親節(jié)點(diǎn)等等，這些在二分搜索樹(shù)中也一樣。
二分搜索樹(shù)的每一個(gè)節(jié)點(diǎn)的值
都要大于其左子樹(shù)的所有節(jié)點(diǎn)的值，
都要小于其右子樹(shù)的所有節(jié)點(diǎn)的值。
在葉子節(jié)點(diǎn)上沒(méi)有左右孩子，
那就相當(dāng)于也滿足這個(gè)條件。
二分搜索樹(shù)的每一棵子樹(shù)也是二分搜索樹(shù)
對(duì)于每一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，
它的左子樹(shù)所有的節(jié)點(diǎn)都比這個(gè)節(jié)點(diǎn)小，
它的右子樹(shù)所有的節(jié)點(diǎn)都比這個(gè)節(jié)點(diǎn)大，
那么用二分搜索樹(shù)來(lái)存儲(chǔ)數(shù)據(jù)的話，
那么再來(lái)查找一個(gè)數(shù)據(jù)就會(huì)變得非常簡(jiǎn)單，
可以很快的知道從左側(cè)找還是右側(cè)找，
甚至可以不用看另外一側(cè)，
所以就大大的加快了查詢速度。
在生活中使用樹(shù)結(jié)構(gòu)，本質(zhì)也是如此，
例如我要找一本 java 編程的書(shū)，
那么進(jìn)入圖書(shū)館我直接進(jìn)入計(jì)算機(jī)科學(xué)這個(gè)區(qū)域找這本書(shū)，
其它的類的圖書(shū)我根本不用去管，
這也是樹(shù)這種結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)之后再對(duì)數(shù)據(jù)進(jìn)行操作時(shí)
才能夠非常高效的核心原因。
為了能夠達(dá)到二分搜索樹(shù)的性質(zhì)
必須讓存儲(chǔ)的元素具有可比較性，
你要定義好 元素之間如何進(jìn)行比較，
因?yàn)楸容^的方式是具有多種的，
必須保證元素之間可以進(jìn)行比較。
在鏈表和數(shù)組中則沒(méi)有這個(gè)要求，
這個(gè)就是二分搜索樹(shù)存儲(chǔ)數(shù)據(jù)的一個(gè)局限性，
也說(shuō)明了凡事都是有代價(jià)的，
如果想加快搜索的話就必須對(duì)數(shù)據(jù)有一定的要求。
代碼示例
二分搜索樹(shù)其實(shí)不是支持所有的類型
所以應(yīng)該對(duì)元素的類型有所限制，
這個(gè)限制就是 這個(gè)類型必須擁有可比較性，
所以在 java 里面的表示就是 對(duì)泛型進(jìn)行約束，
泛型 E 必須滿足 Comparable
也就是這個(gè)類型 E 必須具有可比較性。
代碼實(shí)現(xiàn)
public class MyBinarySearchTree向二分搜索樹(shù)中添加元素> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } }
如果二分搜索樹(shù)的根節(jié)點(diǎn)為空的話
第一個(gè)添加的元素就會(huì)成為根節(jié)點(diǎn)，
如果再添加一個(gè)元素，那么就因該從根節(jié)點(diǎn)出發(fā)，
根據(jù)二分搜索樹(shù)的定義，
每個(gè)節(jié)點(diǎn)的值要比它的左子樹(shù)上所有節(jié)點(diǎn)的值大，
假設(shè)第二個(gè)添加的元素的值小于第一個(gè)添加的元素的值，
那么很顯然第二個(gè)添加的元素要被添加到根節(jié)點(diǎn)的左子樹(shù)上去，
根節(jié)點(diǎn)的左子樹(shù)上只有一個(gè)節(jié)點(diǎn)，
那么這個(gè)節(jié)點(diǎn)就是左子樹(shù)上的根節(jié)點(diǎn)，
這個(gè)左子樹(shù)上的根節(jié)點(diǎn)就是頂層根節(jié)點(diǎn)的左孩子。
按照這樣的規(guī)則，每來(lái)一個(gè)新元素從根節(jié)點(diǎn)開(kāi)始，
如果小于根節(jié)點(diǎn)，那么就插入到根節(jié)點(diǎn)的左子樹(shù)上去，
如果大于根節(jié)點(diǎn)，那么就插入到根節(jié)點(diǎn)的右子樹(shù)上去，
由于不管是左子樹(shù)還是右子樹(shù)，它們又是一棵二分搜索樹(shù)，
那么這個(gè)過(guò)程就是依此類推下去，
一層一層向下比較新添加的節(jié)點(diǎn)的值，
大的向右，小的向左，不停的向下比較，
如果這個(gè)位置沒(méi)有被占住，那么就可以在這個(gè)位置上添加進(jìn)去，
如果這個(gè)位置被占了，那就不停的向下比較，
直到找到一個(gè)合適的位置添加進(jìn)去。
如果遇到兩個(gè)元素的值相同，那暫時(shí)先不去管，
也就是不添加進(jìn)去，因?yàn)橐呀?jīng)有了，
自定義二分搜索樹(shù)不包含重復(fù)元素，
如果想包含重復(fù)元素，
只需要定義左子樹(shù)小于等于節(jié)點(diǎn)、或者右子樹(shù)大于等于節(jié)點(diǎn)，
只要把“等于”這種關(guān)系放進(jìn)定義里就可以了。
二分搜索樹(shù)添加元素的非遞歸寫(xiě)法，和鏈表很像
但是在二分搜索樹(shù)方面的實(shí)現(xiàn)盡量使用遞歸來(lái)實(shí)現(xiàn)，
就是要鍛煉遞歸算法的書(shū)寫(xiě)，
因?yàn)檫f歸算法的很多細(xì)節(jié)和內(nèi)容需要不斷去體會(huì)，
但是非遞歸的寫(xiě)法也很實(shí)用的，
因?yàn)檫f歸本身是具有更高的開(kāi)銷的，
雖然在現(xiàn)代計(jì)算機(jī)上這些開(kāi)銷并不明顯，
但是在一些極端的情況下還是可以看出很大的區(qū)別，
尤其是對(duì)于二分搜索樹(shù)來(lái)說(shuō)，
在最壞的情況下它有可能會(huì)退化成一個(gè)鏈表，
那么在這種情況下使用遞歸的方式很容易造成系統(tǒng)棧的溢出，
二分搜索樹(shù)一些非遞歸的實(shí)現(xiàn)你可以自己練習(xí)一下。
在二分搜索樹(shù)方面，遞歸比非遞歸實(shí)現(xiàn)起來(lái)更加簡(jiǎn)單。
代碼示例
代碼
public class MyBinarySearchTree> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索樹(shù)中添加一個(gè)元素 e public void add (E e) { if (root == null) { root = new Node(e); size ++; } else { add(root, e); } } // 向以node為根的二分搜索樹(shù)種插入元素E，遞歸算法 private void add (Node node, E e) { // node 是對(duì)用戶屏蔽的，用戶不用知道二分搜索樹(shù)中有怎樣一個(gè)節(jié)點(diǎn)結(jié)構(gòu) // 如果出現(xiàn)相同的元素就不進(jìn)行操作了 if (e.equals(node.e)) { return; } else if (e.compareTo(node.e) < 0 && node.left == null) { // 給左孩子賦值 node.left = new Node(e); size ++; return; } else if (e.compareTo(node.e) > 0 && node.right == null) { // 給右海子賦值 node.right = new Node(e); size ++; return; } // 這里是處理節(jié)點(diǎn)被占了，那就進(jìn)入下一個(gè)層的二叉樹(shù)中 if (e.compareTo(node.e) < 0) { // 去左子樹(shù) add(node.left, e); } else { // e.compareTo(node.e) > 0 // 去右子樹(shù) add(node.right, e); } } }
對(duì)于二分搜索的插入操作
上面的代碼是相對(duì)比較復(fù)雜的，
可以進(jìn)行改進(jìn)一下，
讓代碼整體簡(jiǎn)潔一些，
因?yàn)檫f歸算法是有很多不同的寫(xiě)法的，
而且遞歸的終止條件也是有不同的考量。
深入理解遞歸終止條件
改進(jìn)添加操作
遞歸算法有很多不同的寫(xiě)法，
遞歸的終止條件也有不同的考量。
之前的算法
向以 node 為根的二分搜索樹(shù)中插入元素 e，
其實(shí)將新的元素插入至 node 的左孩子或者右孩子，
如果 node 的左或右孩子為空，那可以進(jìn)行相應(yīng)的賦值操作，
如果是 node 的左右孩子都不為空的話，
那就只能遞歸的插入到相應(yīng) node 的左或右孩子中，
因?yàn)檫@一層節(jié)點(diǎn)已經(jīng)滿了，只能考慮下一層了，
下一層符合要求并且節(jié)點(diǎn)沒(méi)有滿，就可以進(jìn)行相應(yīng)的賦值操作了。
但是有對(duì)根節(jié)點(diǎn)做出了特殊的處理，要防止根節(jié)點(diǎn)為空的情況發(fā)生，
如果根節(jié)點(diǎn)為空，那么就將第一個(gè)元素賦值為根節(jié)點(diǎn)，
但是除了根節(jié)點(diǎn)以外，其它節(jié)點(diǎn)不需要做這種特殊處理，
所以導(dǎo)致邏輯上并不統(tǒng)一，并且遞歸的終止條件非常的臃腫，
代碼示例
代碼
public class MyBinarySearchTree> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索樹(shù)中添加一個(gè)元素 e // 改進(jìn)：直接調(diào)用add public void add (E e) { root = add(root, e); } // 向以node為根的二分搜索樹(shù)種插入元素E，遞歸算法 // 改進(jìn)：返回插入的新節(jié)點(diǎn)后二分搜索樹(shù)的根 private Node add (Node node, E e) { // 處理最基本的問(wèn)題 if (node == null) { size ++; return new Node(e); } // 空的二叉樹(shù)也是叉樹(shù)。 if (e.compareTo(node.e) < 0) { // 將處理后的結(jié)果賦值給node的左子樹(shù) node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 將處理后的結(jié)果賦值給node的右子樹(shù) node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回這個(gè)node return node; } // // 向二分搜索樹(shù)中添加一個(gè)元素 e // public void add (E e) { // if (root == null) { // root = new Node(e); // size ++; // } else { // add(root, e); // } // } // // 向以node為根的二分搜索樹(shù)種插入元素E，遞歸算法 // private void add (Node node, E e) { // // node 是對(duì)用戶屏蔽的，用戶不用知道二分搜索樹(shù)中有怎樣一個(gè)節(jié)點(diǎn)結(jié)構(gòu) // // // 如果出現(xiàn)相同的元素就不進(jìn)行操作了 // if (e.equals(node.e)) { // return; // } else if (e.compareTo(node.e) < 0 && node.left == null) { // // 給左孩子賦值 // node.left = new Node(e); // return; // } else if (e.compareTo(node.e) > 0 && node.right == null) { // // 給右海子賦值 // node.right = new Node(e); // return; // } // // // 這里是處理節(jié)點(diǎn)被占了，那就進(jìn)入下一個(gè)層的二叉樹(shù)中 // if (e.compareTo(node.e) < 0) { // // 去左子樹(shù) // add(node.left, e); // } else { // e.compareTo(node.e) > 0 // // 去右子樹(shù) // add(node.right, e); // } // } }
雖然代碼量更少了，但是也更難理解的了一些
首先從宏觀的語(yǔ)意的角度去理解定義這個(gè)函數(shù)的語(yǔ)意后
整個(gè)遞歸函數(shù)處理的邏輯如何成立的，
其次從微觀的角度上可以寫(xiě)一些輔助代碼來(lái)幫助你一點(diǎn)一點(diǎn)的查看，
從一個(gè)空的二分搜索樹(shù)開(kāi)始，往里添加三五個(gè)元素，
看看每個(gè)元素是如何逐步的添加進(jìn)去。
可以嘗試一些鏈表這個(gè)程序插入操作的遞歸算法，
其實(shí)這二者之間是擁有非常高的相似度的，
只不過(guò)在二分搜索樹(shù)中需要判斷一下是需要插入到左子樹(shù)還是右子樹(shù)而已，
對(duì)于鏈表來(lái)說(shuō)直接插入到 next 就好了，
通過(guò)二者的比較就可以更加深入的理解這個(gè)程序。
二分搜索樹(shù)的查詢操作
查詢操作非常的容易
只需要不停的看每一個(gè) node 里面存的元素，
不會(huì)牽扯到整個(gè)二分搜索樹(shù)的添加操作
和添加元素一樣需要使用遞歸的進(jìn)行實(shí)現(xiàn)
在遞歸的過(guò)程中就需要從二分搜索樹(shù)的根開(kāi)始，
逐漸的轉(zhuǎn)移在二分搜索樹(shù)的子樹(shù)中縮小問(wèn)題的規(guī)模，
縮小查詢的樹(shù)的規(guī)模，直到找到這個(gè)元素 e 或者發(fā)現(xiàn)找不到這個(gè)元素 e。
在數(shù)組和鏈表中有索引這個(gè)概念，
但是在二分搜索樹(shù)中沒(méi)有索引這個(gè)概念。
代碼示例
代碼
public class MyBinarySearchTree二分搜索樹(shù)的遍歷-前序遍歷> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索樹(shù)中添加一個(gè)元素 e // 改進(jìn)：直接調(diào)用add public void add (E e) { root = add(root, e); } // 向以node為根的二分搜索樹(shù)中插入元素E，遞歸算法 // 改進(jìn)：返回插入的新節(jié)點(diǎn)后二分搜索樹(shù)的根 private Node add (Node node, E e) { // 處理最基本的問(wèn)題 if (node == null) { size ++; return new Node(e); } // 空的二叉樹(shù)也是叉樹(shù)。 if (e.compareTo(node.e) < 0) { // 將處理后的結(jié)果賦值給node的左子樹(shù) node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 將處理后的結(jié)果賦值給node的右子樹(shù) node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回這個(gè)node return node; } // 查詢二分搜索數(shù)中是否包含某個(gè)元素 public boolean contains (E e) { return contains(root, e); } // 向以node為根的二分搜索樹(shù) 進(jìn)行查找 遞歸算法 public boolean contains (Node node, E e) { // 解決最基本的問(wèn)題 也就是遍歷完所有節(jié)點(diǎn)都沒(méi)有找到 if (node == null) { return false; } // 如果 e 小于當(dāng)前節(jié)點(diǎn)的e 則向左子樹(shù)進(jìn)發(fā) if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當(dāng)前節(jié)點(diǎn)的e 則向右子樹(shù)進(jìn)發(fā) return contains(node.right, e); } else { // 如果e 等于 當(dāng)前節(jié)點(diǎn) e 則直接返回true return true; } } }
遍歷操作就是把這個(gè)數(shù)據(jù)結(jié)構(gòu)中所有的元素都訪問(wèn)一遍
在二分搜索樹(shù)中就是把所有節(jié)點(diǎn)都訪問(wèn)一遍，
訪問(wèn)數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)的所有元素是因?yàn)榕c業(yè)務(wù)相關(guān)，
例如 給所有的同學(xué)加兩分，給所有的員工發(fā)補(bǔ)貼等等，
由于你的數(shù)據(jù)結(jié)構(gòu)是用來(lái)存儲(chǔ)數(shù)據(jù)的，
不僅可以查詢某些特定的數(shù)據(jù)，
還應(yīng)該有相關(guān)的方式將所有的數(shù)據(jù)都進(jìn)行訪問(wèn)。
在線性結(jié)構(gòu)下，遍歷是極其容易的
無(wú)論是數(shù)組還是鏈表只要使用一下循環(huán)就好了，
但是這件事在樹(shù)結(jié)構(gòu)下沒(méi)有那么簡(jiǎn)單，
但是也沒(méi)有那么難：）。
在樹(shù)結(jié)構(gòu)下遍歷操作并沒(méi)有那么難
如果你對(duì)樹(shù)結(jié)構(gòu)不熟悉，那么可能就有點(diǎn)難，
但是如果你熟悉了樹(shù)結(jié)構(gòu)，那么并非是那么難的操作，
尤其是你在掌握遞歸操作之后，遍歷樹(shù)就更加不難了。
對(duì)于遍歷操作，兩個(gè)子樹(shù)都要顧及
即要訪問(wèn)左子樹(shù)中所有的節(jié)點(diǎn)又要訪問(wèn)右子樹(shù)中所有的節(jié)點(diǎn)，
下面的代碼中的遍歷方式也稱為二叉樹(shù)的前序遍歷，
先訪問(wèn)這個(gè)節(jié)點(diǎn)，再訪問(wèn)左右子樹(shù)，
訪問(wèn)這個(gè)節(jié)點(diǎn)放在了訪問(wèn)左右子樹(shù)的前面所以就叫前序遍歷。
要從宏觀與微觀的角度去理解這個(gè)代碼，
從宏觀的角度來(lái)看，
定義好了遍歷的這個(gè)語(yǔ)意后整個(gè)邏輯是怎么組建的，
從微觀的角度來(lái)看，真正的有一個(gè)棵二叉樹(shù)的時(shí)候，
這個(gè)代碼是怎樣怎樣一行一行去執(zhí)行的。
當(dāng)你熟練的掌握遞歸的時(shí)候，
有的時(shí)候你可以不用遵守 那種先寫(xiě)遞歸終止的條件，
再寫(xiě)遞歸組成的的邏輯 這樣的一個(gè)過(guò)程，如寫(xiě)法二，
雖然什么都不干，但是也是 return 了，
和寫(xiě)法一中寫(xiě)的邏輯其實(shí)是等價(jià)的，
也就是在遞歸終止條件這部分可以靈活處理。
寫(xiě)法一看起來(lái)邏輯比較清晰，遞歸終止在前，遞歸組成的邏輯在后。
// 遍歷以node為根的二分搜索樹(shù) 遞歸算法
function traverse(node) {
if (node === null) {
return;
}
// ... 要做的事情
// 訪問(wèn)該節(jié)點(diǎn) 兩邊都要顧及
// 訪問(wèn)該節(jié)點(diǎn)的時(shí)候就去做該做的事情，
// 如 給所有學(xué)生加兩分
traverse(node.left);
traverse(node.right);
}
// 寫(xiě)法二 這種邏輯也是可以的
function traverse(node) {
if (node !== null) {
// ... 要做的事情
// 訪問(wèn)該節(jié)點(diǎn) 兩邊都要顧及
// 訪問(wèn)該節(jié)點(diǎn)的時(shí)候就去做該做的事情，
// 如 給所有學(xué)生加兩分
traverse(node.left);
traverse(node.right);
}
}
代碼示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索樹(shù)中添加一個(gè)元素 e // 改進(jìn)：直接調(diào)用add public void add (E e) { root = add(root, e); } // 向以node為根的二分搜索樹(shù)中插入元素E，遞歸算法 // 改進(jìn)：返回插入的新節(jié)點(diǎn)后二分搜索樹(shù)的根 private Node add (Node node, E e) { // 處理最基本的問(wèn)題 if (node == null) { size ++; return new Node(e); } // 空的二叉樹(shù)也是叉樹(shù)。 if (e.compareTo(node.e) < 0) { // 將處理后的結(jié)果賦值給node的左子樹(shù) node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 將處理后的結(jié)果賦值給node的右子樹(shù) node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回這個(gè)node return node; } // 查詢二分搜索數(shù)中是否包含某個(gè)元素 public boolean contains (E e) { return contains(root, e); } // 向以node為根的二分搜索樹(shù) 進(jìn)行查找 遞歸算法 public boolean contains (Node node, E e) { // 解決最基本的問(wèn)題 也就是遍歷完所有節(jié)點(diǎn)都沒(méi)有找到 if (node == null) { return false; } // 如果 e 小于當(dāng)前節(jié)點(diǎn)的e 則向左子樹(shù)進(jìn)發(fā) if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當(dāng)前節(jié)點(diǎn)的e 則向右子樹(shù)進(jìn)發(fā) return contains(node.right, e); } else { // 如果e 等于 當(dāng)前節(jié)點(diǎn) e 則直接返回true return true; } } // 二分搜索樹(shù)的前序遍歷 public void preOrder () { preOrder(root); } // 前序遍歷以node為根的二分搜索樹(shù) 遞歸算法 public void preOrder (Node node) { if (node == null) { return; } // 輸出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 這種邏輯也是可以的 // if (node != null) { // // 輸出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } }
Main
public class Main {
public static void main(String[] args) {
MyBinarySearchTree mbst = new MyBinarySearchTree();
int [] nums = {5, 3, 6, 8, 4, 2};
for (int i = 0; i < nums.length ; i++) {
mbst.add(nums[i]);
}
/////////////////
// 5 //
// / //
// 3 6 //
// / //
// 2 4 8 //
/////////////////
mbst.preOrder();
}
}
二分搜索樹(shù)的遍歷調(diào)試-前序遍歷
遍歷輸出二分搜索樹(shù)
可以寫(xiě)一個(gè)輔助函數(shù)自動(dòng)遍歷所有節(jié)點(diǎn)生成字符串，
輔助函數(shù)叫做 generateBSTString，
這個(gè)函數(shù)的作用是，生成以 node 為根節(jié)點(diǎn)，
深度為 depth 的描述二叉樹(shù)的字符串，
這樣一來(lái)要新增一個(gè)輔助函數(shù)，
這個(gè)函數(shù)的作用是，根據(jù)遞歸深度生成字符串，
這個(gè)輔助函數(shù)叫做 generateDepthString。
代碼示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索樹(shù)中添加一個(gè)元素 e // 改進(jìn)：直接調(diào)用add public void add (E e) { root = add(root, e); } // 向以node為根的二分搜索樹(shù)中插入元素E，遞歸算法 // 改進(jìn)：返回插入的新節(jié)點(diǎn)后二分搜索樹(shù)的根 private Node add (Node node, E e) { // 處理最基本的問(wèn)題 if (node == null) { size ++; return new Node(e); } // 空的二叉樹(shù)也是叉樹(shù)。 if (e.compareTo(node.e) < 0) { // 將處理后的結(jié)果賦值給node的左子樹(shù) node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 將處理后的結(jié)果賦值給node的右子樹(shù) node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回這個(gè)node return node; } // 查詢二分搜索數(shù)中是否包含某個(gè)元素 public boolean contains (E e) { return contains(root, e); } // 向以node為根的二分搜索樹(shù) 進(jìn)行查找 遞歸算法 public boolean contains (Node node, E e) { // 解決最基本的問(wèn)題 也就是遍歷完所有節(jié)點(diǎn)都沒(méi)有找到 if (node == null) { return false; } // 如果 e 小于當(dāng)前節(jié)點(diǎn)的e 則向左子樹(shù)進(jìn)發(fā) if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當(dāng)前節(jié)點(diǎn)的e 則向右子樹(shù)進(jìn)發(fā) return contains(node.right, e); } else { // 如果e 等于 當(dāng)前節(jié)點(diǎn) e 則直接返回true return true; } } // 二分搜索樹(shù)的前序遍歷 public void preOrder () { preOrder(root); } // 前序遍歷以node為根的二分搜索樹(shù) 遞歸算法 public void preOrder (Node node) { if (node == null) { return; } // 輸出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 這種邏輯也是可以的 // if (node != null) { // // 輸出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } @Override public String toString () { StringBuilder sb = new StringBuilder(); generateBSTString(root, 0, sb); return sb.toString(); } // 生成以node為根節(jié)點(diǎn)，深度為depth的描述二叉樹(shù)的字符串 private void generateBSTString (Node node, int depath, StringBuilder sb) { if (node == null) { sb.append(generateDepthString(depath) + "null "); return; } sb.append(generateDepthString(depath) + node.e + " "); generateBSTString(node.left, depath + 1, sb); generateBSTString(node.right, depath + 1, sb); } // 生成路徑字符串 private String generateDepthString (int depth) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append("-- "); } return sb.toString(); } }
Main
public class Main {
public static void main(String[] args) {
MyBinarySearchTree mbst = new MyBinarySearchTree();
int [] nums = {5, 3, 6, 8, 4, 2};
for (int i = 0; i < nums.length ; i++) {
mbst.add(nums[i]);
}
/////////////////
// 5 //
// / //
// 3 6 //
// / //
// 2 4 8 //
/////////////////
mbst.preOrder();
System.out.println();
// 輸出 調(diào)試字符串
System.out.println(mbst.toString());
}
}
二分搜索樹(shù)的遍歷-中序、后序遍歷
前序遍歷
前序遍歷是最自然的一種遍歷方式，
同時(shí)也是最常用的一種遍歷方式，
如果沒(méi)有特殊情況的話，
在大多數(shù)情況下都會(huì)使用前序遍歷。
先訪問(wèn)這個(gè)節(jié)點(diǎn)，
然后訪問(wèn)這個(gè)節(jié)點(diǎn)的左子樹(shù)，
再訪問(wèn)這個(gè)節(jié)點(diǎn)的右子樹(shù)，
整個(gè)過(guò)程循環(huán)往復(fù)。
前序遍歷的前表示先訪問(wèn)的這個(gè)節(jié)點(diǎn)。
function preOrder(node) {
if (node == null) return;
// ... 要做的事情
// 訪問(wèn)該節(jié)點(diǎn)
// 先一直往左，然后不斷返回上一層 再向左、終止，
// 最后整個(gè)操作循環(huán)往復(fù)，直到全部終止。
preOrder(node.left);
preOrder(node.right);
}
中序遍歷
先訪問(wèn)左子樹(shù)，再訪問(wèn)這個(gè)節(jié)點(diǎn)，
最后訪問(wèn)右子樹(shù)，整個(gè)過(guò)程循環(huán)往復(fù)。
中序遍歷的中表示先訪問(wèn)左子樹(shù)，
然后再訪問(wèn)這個(gè)節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)，
訪問(wèn)這個(gè)節(jié)點(diǎn)的操作放到了訪問(wèn)左子樹(shù)和右子樹(shù)的中間。
function inOrder(node) {
if (node == null) return;
inOrder(node.left);
// ... 要做的事情
// 訪問(wèn)該節(jié)點(diǎn)
inOrder(node.right);
}
中序遍歷后輸出的結(jié)果是排序后的結(jié)果。
中序遍歷的結(jié)果是二分搜索樹(shù)中
存儲(chǔ)的所有的元素從小到大進(jìn)行排序后的結(jié)果，
這是二分搜索樹(shù)一個(gè)很重要的一個(gè)性質(zhì)。
二分搜索樹(shù)任何一個(gè)節(jié)點(diǎn)的左子樹(shù)上所有的節(jié)點(diǎn)值都比當(dāng)前節(jié)點(diǎn)的小，
二分搜索樹(shù)任何一個(gè)節(jié)點(diǎn)的右子樹(shù)上所有的節(jié)點(diǎn)值都比當(dāng)前節(jié)點(diǎn)的大，
每一個(gè)節(jié)點(diǎn)的遍歷都是從左往自己再往右，
先遍歷這個(gè)節(jié)點(diǎn)的左子樹(shù)，先把比自己節(jié)點(diǎn)小的所有元素都遍歷了，
再遍歷這個(gè)節(jié)點(diǎn)，然后再遍歷比這個(gè)節(jié)點(diǎn)大的所有元素，這個(gè)過(guò)程是遞歸完成的，
以 小于、等于、大于的順序遍歷得到的結(jié)果自然就是一個(gè)從小到大的排序的，
你也可以 使用大于 等于 小于的順序遍歷，那樣結(jié)果就是從大到小排序了。
也正是因?yàn)檫@個(gè)原因，二分搜索樹(shù)有的時(shí)候也叫做排序樹(shù)，
這是二分搜索樹(shù)額外的效能，
當(dāng)你使用數(shù)組、鏈表時(shí)如果想讓你的元素是順序的話，
必須做額外的工作，否則沒(méi)有辦法保證一次遍歷得到的元素都是順序排列的，
但是對(duì)于二分搜索樹(shù)來(lái)說(shuō)，你只要遵從他的定義，
然后使用中序遍歷的方式遍歷整棵二分搜索樹(shù)就能夠得到順序排列的結(jié)果。
后序遍歷
先訪問(wèn)左子樹(shù)，再訪問(wèn)右子樹(shù)，
最后訪問(wèn)這個(gè)節(jié)點(diǎn)，整個(gè)過(guò)程循環(huán)往復(fù)。
后序遍歷的后表示先訪問(wèn)左子樹(shù)，
然后再訪問(wèn)右子樹(shù)，最后訪問(wèn)這個(gè)節(jié)點(diǎn)，
訪問(wèn)這個(gè)節(jié)點(diǎn)的操作放到了訪問(wèn)左子樹(shù)和右子樹(shù)的后邊。
function inOrder(node) {
if (node == null) return;
inOrder(node.left);
inOrder(node.right);
// ... 要做的事情
// 訪問(wèn)該節(jié)點(diǎn)
}
二分搜索樹(shù)的前序遍歷和后序遍歷并不像中序遍歷那樣進(jìn)行了排序
后續(xù)遍歷的應(yīng)用場(chǎng)景是那些必須先處理完左子樹(shù)的所有節(jié)點(diǎn)，
然后再處理完右子樹(shù)的所有節(jié)點(diǎn)，最后再處理當(dāng)前的節(jié)點(diǎn)，
也就是處理完這個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)之后再去處理當(dāng)前這個(gè)節(jié)點(diǎn)。
一個(gè)典型的應(yīng)用是在內(nèi)存釋放方面，如果需要你手動(dòng)的釋放內(nèi)存，
那么就需要先把這個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)全都釋放完然后再來(lái)釋放這個(gè)節(jié)點(diǎn)本身，
這種情況使用二叉樹(shù)的后序遍歷的方式，
先處理左子樹(shù)、再處理右子樹(shù)、最后處理自己。
但是例如java、c#這樣的語(yǔ)言都有垃圾回收機(jī)制，
所以不需要你對(duì)內(nèi)存管理進(jìn)行手動(dòng)的控制，
c++ 語(yǔ)言中需要手動(dòng)的控制內(nèi)存，
那么在二分搜索樹(shù)內(nèi)存釋放這方面就需要使用后序遍歷。
對(duì)于一些樹(shù)結(jié)構(gòu)的問(wèn)題，
很多時(shí)候也是需要先針對(duì)一個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)求解出答案，
最終再由這些答案組合成針對(duì)這個(gè)節(jié)點(diǎn)的答案，
樹(shù)形問(wèn)題有分治算法、回溯算法、動(dòng)態(tài)規(guī)劃算法等等。
二分搜索樹(shù)的前中后序遍歷
主要從程序的角度進(jìn)行分析，
很多時(shí)候?qū)σ恍﹩?wèn)題的分析，如果直接給你一個(gè)樹(shù)結(jié)構(gòu)，
然后你能夠直接看出來(lái)對(duì)于這棵樹(shù)來(lái)說(shuō)它的前中后序遍歷的結(jié)果是怎樣的，
那就可以大大加快解決問(wèn)題的速度，
同時(shí)這樣的一個(gè)問(wèn)題也是和計(jì)算機(jī)相關(guān)的考試的題目，
對(duì)于這樣的一個(gè)問(wèn)題的更加深入的理解
也可以幫助你理解二分搜索樹(shù)這種數(shù)據(jù)結(jié)構(gòu)。
代碼示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索樹(shù)中添加一個(gè)元素 e // 改進(jìn)：直接調(diào)用add public void add (E e) { root = add(root, e); } // 向以node為根的二分搜索樹(shù)中插入元素E，遞歸算法 // 改進(jìn)：返回插入的新節(jié)點(diǎn)后二分搜索樹(shù)的根 private Node add (Node node, E e) { // 處理最基本的問(wèn)題 if (node == null) { size ++; return new Node(e); } // 空的二叉樹(shù)也是叉樹(shù)。 if (e.compareTo(node.e) < 0) { // 將處理后的結(jié)果賦值給node的左子樹(shù) node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 將處理后的結(jié)果賦值給node的右子樹(shù) node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回這個(gè)node return node; } // 查詢二分搜索數(shù)中是否包含某個(gè)元素 public boolean contains (E e) { return contains(root, e); } // 向以node為根的二分搜索樹(shù) 進(jìn)行查找 遞歸算法 private boolean contains (Node node, E e) { // 解決最基本的問(wèn)題 也就是遍歷完所有節(jié)點(diǎn)都沒(méi)有找到 if (node == null) { return false; } // 如果 e 小于當(dāng)前節(jié)點(diǎn)的e 則向左子樹(shù)進(jìn)發(fā) if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當(dāng)前節(jié)點(diǎn)的e 則向右子樹(shù)進(jìn)發(fā) return contains(node.right, e); } else { // 如果e 等于 當(dāng)前節(jié)點(diǎn) e 則直接返回true return true; } } // 二分搜索樹(shù)的前序遍歷 public void preOrder () { preOrder(root); } // 前序遍歷以node為根的二分搜索樹(shù) 遞歸算法 private void preOrder (Node node) { if (node == null) { return; } // 輸出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 這種邏輯也是可以的 // if (node != null) { // // 輸出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } // 二分搜索樹(shù)的中序遍歷 public void inOrder () { inOrder(root); } // 中序遍歷以node為根的二分搜索樹(shù) 遞歸算法 private void inOrder (Node node) { if (node == null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); } // 二分搜索樹(shù)的后序遍歷 public void postOrder () { postOrder(root); } // 后續(xù)遍歷以node為根的二分搜索樹(shù) 遞歸算法 private void postOrder (Node node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); } @Override public String toString () { StringBuilder sb = new StringBuilder(); generateBSTString(root, 0, sb); return sb.toString(); } // 生成以node為根節(jié)點(diǎn)，深度為depth的描述二叉樹(shù)的字符串 private void generateBSTString (Node node, int depath, StringBuilder sb) { if (node == null) { sb.append(generateDepthString(depath) + "null "); return; } sb.append(generateDepthString(depath) + node.e + " "); generateBSTString(node.left, depath + 1, sb); generateBSTString(node.right, depath + 1, sb); } // 生成路徑字符串 private String generateDepthString (int depth) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append("-- "); } return sb.toString(); } }
Main
public class Main {
public static void main(String[] args) {
MyBinarySearchTree mbst = new MyBinarySearchTree();
int [] nums = {5, 3, 6, 8, 4, 2};
for (int i = 0; i < nums.length ; i++) {
mbst.add(nums[i]);
}
/////////////////
// 5 //
// / //
// 3 6 //
// / //
// 2 4 8 //
/////////////////
// 前序遍歷
mbst.preOrder(); // 5 3 2 4 6 8
System.out.println();
// 中序遍歷
mbst.inOrder(); // 2 3 4 5 6 8
System.out.println();
// 后序遍歷
mbst.postOrder(); // 2 4 3 8 6 5
System.out.println();
// // 輸出 調(diào)試字符串
// System.out.println(mbst.toString());
}
}
二分搜索樹(shù)的遍歷-深入理解前中后序遍歷
再看二分搜索樹(shù)的遍歷
對(duì)每一個(gè)節(jié)點(diǎn)都有三次的訪問(wèn)機(jī)會(huì)，
在遍歷左子樹(shù)之前會(huì)去訪問(wèn)一下這個(gè)節(jié)點(diǎn)然后才能遍歷它的左子樹(shù)，
在遍歷完左子樹(shù)之后才能夠回到這個(gè)節(jié)點(diǎn)，之后才會(huì)去遍歷它的右子樹(shù)，
在遍歷右子樹(shù)之后又回到了這個(gè)節(jié)點(diǎn)。
這就是每一個(gè)節(jié)點(diǎn)使用這種遞歸遍歷的方式其實(shí)會(huì)訪問(wèn)它三次，
對(duì)二分搜索樹(shù)前中后這三種順序的遍歷
其實(shí)就對(duì)應(yīng)于這三個(gè)訪問(wèn)機(jī)會(huì)是在哪里進(jìn)行真正的那個(gè)訪問(wèn)操作，
在哪里輸出訪問(wèn)的這個(gè)節(jié)點(diǎn)的值，
是先訪問(wèn)這個(gè)節(jié)點(diǎn)后再遍歷它的左右子樹(shù)，
還是先遍歷左子樹(shù)然后訪問(wèn)這個(gè)節(jié)點(diǎn)最后遍歷右子樹(shù)，
再或者是 先遍歷左右子樹(shù)再訪問(wèn)這個(gè)節(jié)點(diǎn)。
function traverse(node) {
if (node === null) return;
// 1. 第一個(gè)訪問(wèn)的機(jī)會(huì) 前
traverse(node.left);
// 2. 第二個(gè)訪問(wèn)的機(jī)會(huì) 中
traverse(node.right);
// 3. 第三個(gè)訪問(wèn)的機(jī)會(huì) 后
}
二叉樹(shù)前中后序遍歷訪問(wèn)節(jié)點(diǎn)的不同
前序遍歷訪問(wèn)節(jié)點(diǎn)都是在第一個(gè)訪問(wèn)機(jī)會(huì)的位置才去訪問(wèn)節(jié)點(diǎn)，
中序遍歷訪問(wèn)節(jié)點(diǎn)都是在第二個(gè)訪問(wèn)機(jī)會(huì)的位置才去訪問(wèn)節(jié)點(diǎn)，
后序遍歷訪問(wèn)節(jié)點(diǎn)都是在第三個(gè)訪問(wèn)機(jī)會(huì)的位置才去訪問(wèn)節(jié)點(diǎn)，
二分搜索樹(shù)的遍歷-非遞歸寫(xiě)法
前序遍歷的遞歸寫(xiě)法
前序遍歷是最自然的一種遍歷方式，
同時(shí)也是最常用的一種遍歷方式，
如果沒(méi)有特殊情況的話，
在大多數(shù)情況下都會(huì)使用前序遍歷。
先訪問(wèn)這個(gè)節(jié)點(diǎn)，
然后訪問(wèn)這個(gè)節(jié)點(diǎn)的左子樹(shù)，
再訪問(wèn)這個(gè)節(jié)點(diǎn)的右子樹(shù)，
整個(gè)過(guò)程循環(huán)往復(fù)。
前序遍歷的前表示先訪問(wèn)的這個(gè)節(jié)點(diǎn)。
function preOrder(node) {
if (node == null) return;
// ... 要做的事情
// 訪問(wèn)該節(jié)點(diǎn)
// 先一直往左，然后不斷返回上一層 再向左、終止，
// 最后整個(gè)操作循環(huán)往復(fù)，直到全部終止。
preOrder(node.left);
preOrder(node.right);
}
前序遍歷的非遞歸寫(xiě)法
使用另外一個(gè)數(shù)據(jù)結(jié)構(gòu)棧來(lái)模擬遞歸調(diào)用時(shí)的系統(tǒng)棧。
先訪問(wèn)根節(jié)點(diǎn)，將根節(jié)點(diǎn)壓入棧，
然后把棧頂元素拿出來(lái)，對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行操作，
這個(gè)節(jié)點(diǎn)操作完畢之后，再訪問(wèn)這個(gè)節(jié)點(diǎn)的兩個(gè)子樹(shù)，
也就是把這個(gè)節(jié)點(diǎn)的左右兩個(gè)孩子壓入棧中，
壓入棧的順序是先壓入右孩子、再壓入左孩子，
這是因?yàn)闂Ｊ呛笕胂瘸龅模砸葔喝牒罄m(xù)要訪問(wèn)的那個(gè)節(jié)點(diǎn)，
再讓棧頂?shù)脑爻鰲?，?duì)這個(gè)節(jié)點(diǎn)進(jìn)行操作，
這個(gè)節(jié)點(diǎn)操作完畢之后，再訪問(wèn)這個(gè)節(jié)點(diǎn)的兩個(gè)子樹(shù)，
但是這個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)，它的兩個(gè)孩子都為空，
那么什么都不用壓入了， 再去取棧頂?shù)脑兀?/p>
對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行操作，這個(gè)節(jié)點(diǎn)操作完畢之后，
再訪問(wèn)這個(gè)節(jié)點(diǎn)的兩個(gè)子樹(shù)，但是這個(gè)節(jié)點(diǎn)也是葉子節(jié)點(diǎn)，
那么什么都不用壓入了，棧中也為空了，整個(gè)訪問(wèn)操作結(jié)束。
無(wú)論是非遞歸還是遞歸的寫(xiě)法，結(jié)果都是一致的
非遞歸的寫(xiě)法中，棧的應(yīng)用是幫助你記錄你下面要訪問(wèn)的哪些節(jié)點(diǎn)，
這個(gè)過(guò)程非常像使用棧模擬了一下在系統(tǒng)棧中相應(yīng)的一個(gè)調(diào)用，
相當(dāng)于在系統(tǒng)棧中記錄下一步依次要訪問(wèn)哪些節(jié)點(diǎn)。
將遞歸算法轉(zhuǎn)換為非遞歸算法
是棧這種數(shù)據(jù)結(jié)構(gòu)非常重要的一種應(yīng)用。
二分搜索樹(shù)遍歷的非遞歸實(shí)現(xiàn)比遞歸實(shí)現(xiàn)復(fù)雜很多
因?yàn)槟闶褂昧艘粋€(gè)輔助的數(shù)據(jù)結(jié)構(gòu)才能完成這個(gè)過(guò)程，
使用了棧這種數(shù)據(jù)結(jié)構(gòu)模擬了系統(tǒng)調(diào)用棧，
在算法語(yǔ)意解讀上遠(yuǎn)遠(yuǎn)比遞歸實(shí)現(xiàn)的算法語(yǔ)意解讀要難很多。
二分搜索樹(shù)的中序遍歷和后序遍歷的非遞歸實(shí)現(xiàn)更復(fù)雜
尤其是對(duì)于后序遍歷來(lái)說(shuō)難度更大，
但是中序遍歷和后序遍歷的非遞歸實(shí)現(xiàn)，實(shí)際應(yīng)用并不廣泛。
但是你可以嘗試實(shí)現(xiàn)中序、后序遍歷的非遞歸實(shí)現(xiàn)，
主要是鍛煉你算法實(shí)現(xiàn)、思維邏輯實(shí)現(xiàn)思路，
在解決這個(gè)問(wèn)題的過(guò)程中可能會(huì)遇到一些困難，
可以通過(guò)查看網(wǎng)上的資料來(lái)解決這個(gè)問(wèn)題，
這樣的問(wèn)題有可能會(huì)在面試題及考試中出現(xiàn)，
也就是中序和后序遍歷相應(yīng)的非遞歸實(shí)現(xiàn)。
在經(jīng)典的教科書(shū)中一般都會(huì)有這三種遍歷的非遞歸實(shí)現(xiàn)，
通過(guò)二分搜索樹(shù)的前序遍歷非遞歸的實(shí)現(xiàn)方式中可以看出，
完全可以使用模擬系統(tǒng)的棧來(lái)完成遞歸轉(zhuǎn)成非遞歸這樣的操作，
在慕課上 有一門(mén)課《玩轉(zhuǎn)算法面試》中完全模擬了系統(tǒng)棧的寫(xiě)法，
也就是將前中后序的遍歷都轉(zhuǎn)成了非遞歸的算法，
這與經(jīng)典的教科書(shū)上的實(shí)現(xiàn)不一樣，
但是這種方式對(duì)你進(jìn)一步理解棧這種數(shù)據(jù)結(jié)構(gòu)還是二分搜索樹(shù)的遍歷
甚至是系統(tǒng)調(diào)用的過(guò)程都是很有意義的。
對(duì)于前序遍歷來(lái)說(shuō)無(wú)論是遞歸寫(xiě)法還是非遞歸寫(xiě)法
對(duì)于這棵樹(shù)來(lái)說(shuō)都是在遍歷的過(guò)程中一直到底，
這樣的一種遍歷方式也叫深度優(yōu)先遍歷，
最終的遍歷結(jié)果都會(huì)先來(lái)到整顆樹(shù)最深的地方，
直到不能再深了才會(huì)開(kāi)始返回到上一層，
所以這種遍歷就叫做深度優(yōu)先遍歷。
與深度優(yōu)先遍歷相對(duì)應(yīng)的就是廣度優(yōu)先遍歷，
廣度優(yōu)先遍歷遍歷出來(lái)的結(jié)果它的順序其實(shí)是
整個(gè)二分搜索樹(shù)的一個(gè)層序遍歷的順序。
代碼示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.Stack;
public class MyBinarySearchTree> {
private class Node {
public E e;
public Node left, right;
public Node (E e) {
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public MyBinarySearchTree () {
root = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty () {
return size == 0;
}
// 向二分搜索樹(shù)中添加一個(gè)元素 e
// 改進(jìn)：直接調(diào)用add
public void add (E e) {
root = add(root, e);
}
// 向以node為根的二分搜索樹(shù)中插入元素E，遞歸算法
// 改進(jìn)：返回插入的新節(jié)點(diǎn)后二分搜索樹(shù)的根
private Node add (Node node, E e) {
// 處理最基本的問(wèn)題
if (node == null) {
size ++;
return new Node(e);
}
// 空的二叉樹(shù)也是叉樹(shù)。
if (e.compareTo(node.e) < 0) {
// 將處理后的結(jié)果賦值給node的左子樹(shù)
node.left = add(node.left, e);
} else if (e.compareTo(node.e) > 0) {
// 將處理后的結(jié)果賦值給node的右子樹(shù)
node.right = add(node.right, e);
} // 如果相同 就什么都不做
// 最后返回這個(gè)node
return node;
}
// 查詢二分搜索數(shù)中是否包含某個(gè)元素
public boolean contains (E e) {
return contains(root, e);
}
// 向以node為根的二分搜索樹(shù) 進(jìn)行查找 遞歸算法
private boolean contains (Node node, E e) {
// 解決最基本的問(wèn)題 也就是遍歷完所有節(jié)點(diǎn)都沒(méi)有找到
if (node == null) {
return false;
}
// 如果 e 小于當(dāng)前節(jié)點(diǎn)的e 則向左子樹(shù)進(jìn)發(fā)
if (e.compareTo(node.e) < 0) {
return contains(node.left, e);
} else if (e.compareTo(node.e) > 0) { // 如果 e 大于當(dāng)前節(jié)點(diǎn)的e 則向右子樹(shù)進(jìn)發(fā)
return contains(node.right, e);
} else { // 如果e 等于 當(dāng)前節(jié)點(diǎn) e 則直接返回true
return true;
}
}
// 二分搜索樹(shù)的前序遍歷
public void preOrder () {
preOrder(root);
}
// 前序遍歷以node為根的二分搜索樹(shù) 遞歸算法
private void preOrder (Node node) {
if (node == null) {
return;
}
// 輸出
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
// // 這種邏輯也是可以的
// if (node != null) {
// // 輸出
// System.out.println(node.e);
//
// preOrder(node.left);
// preOrder(node.right);
// }
}
// 二分搜索樹(shù)的前序遍歷 非遞歸算法
public void preOrderNonRecursive () {
Stack stack = new Stack();
stack.push(root);
Node node = null;
while (!stack.isEmpty()) {
node = stack.pop();
// // 第一種寫(xiě)法 不符合要求也可以壓入棧，但是不符合要求的在出棧后不處理它
// if (node != null) {
// System.out.println(node.e);
// stack.push(node.right);
// stack.push(node.left);
// }
// // 第二種寫(xiě)法 不符合要求也可以壓入棧，但是不符合要求的在出棧后不處理它
// if (node == null) continue;
//
// System.out.println(node.e);
// stack.push(node.right);
// stack.push(node.left);
// 寫(xiě)法三 不符合要求就不壓入棧
System.out.println(node.e);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
// 二分搜索樹(shù)的中序遍歷
public void inOrder () {
inOrder(root);
}
// 中序遍歷以node為根的二分搜索樹(shù) 遞歸算法
private void inOrder (Node node) {
if (node == null) return;
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
// 二分搜索樹(shù)的中序遍歷 非遞歸算法
public void inOrderNonRecursive () {
}
// 二分搜索樹(shù)的后序遍歷
public void postOrder () {
postOrder(root);
}
// 后續(xù)遍歷以node為根的二分搜索樹(shù) 遞歸算法
private void postOrder (Node node) {
if (node == null) return;
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
@Override
public String toString () {
StringBuilder sb = new StringBuilder();
generateBSTString(root, 0, sb);
return sb.toString();
}
// 生成以node為根節(jié)點(diǎn)，深度為depth的描述二叉樹(shù)的字符串
private void generateBSTString (Node node, int depath, StringBuilder sb) {
if (node == null) {
sb.append(generateDepthString(depath) + "null
");
return;
}
sb.append(generateDepthString(depath) + node.e + "
");
generateBSTString(node.left, depath + 1, sb);
generateBSTString(node.right, depath + 1, sb);
}
// 生成路徑字符串
private String generateDepthString (int depth) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < depth; i++) {
sb.append("-- ");
}
return sb.toString();
}
}
Main
public class Main {
public static void main(String[] args) {
MyBinarySearchTree mbst = new MyBinarySearchTree();
int [] nums = {5, 3, 6, 8, 4, 2};
for (int i = 0; i < nums.length ; i++) {
mbst.add(nums[i]);
}
/////////////////
// 5 //
// / //
// 3 6 //
// / //
// 2 4 8 //
/////////////////
// 前序遍歷
mbst.preOrder(); // 5 3 2 4 6 8
System.out.println();
// 中序遍歷
mbst.inOrder(); // 2 3 4 5 6 8
System.out.println();
// 后序遍歷
mbst.postOrder(); // 2 4 3 8 6 5
System.out.println();
// 前序遍歷 非遞歸
mbst.preOrderNonRecursive(); // 5 3 2 4 6 8
System.out.println();
// // 輸出 調(diào)試字符串
// System.out.println(mbst.toString());
}
}
二分搜索樹(shù)的層序遍歷
二分搜索樹(shù)的 前序、中序、后序遍歷
它們本質(zhì)上都是深度優(yōu)先遍歷。
對(duì)于二分搜索樹(shù)來(lái)說(shuō)
每一個(gè)節(jié)點(diǎn)都有一個(gè)相應(yīng)的深度的值，
根節(jié)點(diǎn)作為深度為 0 相應(yīng)的節(jié)點(diǎn)，
有一些教科書(shū) 會(huì)把根節(jié)點(diǎn)作為深度為 1 相
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/102901.html
摘要：在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)?yīng)樹(shù)結(jié)構(gòu)來(lái)說(shuō)二叉樹(shù)是最常用的一種樹(shù)結(jié)構(gòu)，二叉樹(shù)具有一個(gè)唯一的根節(jié)點(diǎn)，也就是最上面的節(jié)點(diǎn)。二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子，一個(gè)孩子都沒(méi)有的節(jié)點(diǎn)通常稱之為葉子節(jié)點(diǎn)，二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有一個(gè)父親，根節(jié)點(diǎn)是沒(méi)有父親節(jié)點(diǎn)的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
摘要：鏈表與遞歸已經(jīng)從底層完整實(shí)現(xiàn)了一個(gè)單鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，并且也依托鏈表這樣的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了棧和隊(duì)列，在實(shí)現(xiàn)隊(duì)列的時(shí)候?qū)︽湵磉M(jìn)行了一些改進(jìn)。計(jì)算這個(gè)區(qū)間內(nèi)的所有數(shù)字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)，全部文...
摘要：鏈表與遞歸已經(jīng)從底層完整實(shí)現(xiàn)了一個(gè)單鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，并且也依托鏈表這樣的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了棧和隊(duì)列，在實(shí)現(xiàn)隊(duì)列的時(shí)候?qū)︽湵磉M(jìn)行了一些改進(jìn)。計(jì)算這個(gè)區(qū)間內(nèi)的所有數(shù)字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)，全部文...
摘要：棧的實(shí)現(xiàn)棧這種數(shù)據(jù)結(jié)構(gòu)非常有用但其實(shí)是非常簡(jiǎn)單的。其實(shí)棧頂元素反映了在嵌套的層級(jí)關(guān)系中，最新的需要匹配的元素。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)，全部文章大概的內(nèi)容如下：Arrays(數(shù)組)、Stacks(棧)...
摘要：棧的實(shí)現(xiàn)棧這種數(shù)據(jù)結(jié)構(gòu)非常有用但其實(shí)是非常簡(jiǎn)單的。其實(shí)棧頂元素反映了在嵌套的層級(jí)關(guān)系中，最新的需要匹配的元素。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)，全部文章大概的內(nèi)容如下：Arrays(數(shù)組)、Stacks(棧)...
閱讀 1451·2023-04-25 16:31
閱讀 2054·2021-11-24 10:33
閱讀 2755·2021-09-23 11:33
閱讀 2545·2021-09-23 11:31
閱讀 2926·2021-09-08 09:45
閱讀 2350·2021-09-06 15:02
閱讀 2658·2019-08-30 14:21
閱讀 2323·2019-08-30 12:56
