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