本篇內(nèi)容主要講解“如何通過(guò)代碼實(shí)現(xiàn)二叉搜索樹(shù)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“如何通過(guò)代碼實(shí)現(xiàn)二叉搜索樹(shù)”吧!

成都創(chuàng)新互聯(lián)于2013年成立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元玉山做網(wǎng)站,已為上家服務(wù),為玉山各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108

首先，二叉搜索樹(shù)到底是什么?

二叉搜索樹(shù)(BST)是一種特殊類型的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)及其子節(jié)點(diǎn)組成，子節(jié)點(diǎn)也被視作“后代”，可以把它想象成一棵倒置的樹(shù)或者是樹(shù)的根部。

每個(gè)節(jié)點(diǎn)最多只能有2個(gè)子節(jié)點(diǎn)：左節(jié)點(diǎn)和右節(jié)點(diǎn)。為了使它成為一個(gè)有效的二叉搜索樹(shù)，左節(jié)點(diǎn)的值必須總是小于母節(jié)點(diǎn)，而右節(jié)點(diǎn)的值必須總是大于母節(jié)點(diǎn)。沒(méi)有任何間隙的BST，即每個(gè)節(jié)點(diǎn)都有一個(gè)左節(jié)點(diǎn)和一個(gè)右節(jié)點(diǎn)的二叉搜索樹(shù)，被稱為“完美”樹(shù)。

在完美樹(shù)中，當(dāng)遍歷樹(shù)時(shí)，每個(gè)級(jí)別中的節(jié)點(diǎn)數(shù)會(huì)翻倍，將前面的所有節(jié)點(diǎn)相加并在該數(shù)字上再添加“1”可以得出底層的節(jié)點(diǎn)總數(shù)。

當(dāng)在平衡二叉搜索樹(shù)中搜索一個(gè)元素時(shí)，平均需要花費(fèi)額的時(shí)間為O(log  n)，在最壞的情況下，需要O(n)。你可以把在二叉搜索樹(shù)中的搜索看作是“選擇你自己的冒險(xiǎn)”模型，從頂部節(jié)點(diǎn)開(kāi)始，然后沿著樹(shù)向下，在到達(dá)的每個(gè)節(jié)點(diǎn)問(wèn)同樣的2個(gè)問(wèn)題。

• 我要找的值是否小于當(dāng)前節(jié)點(diǎn)?如果是，向左走。

• 我要找的值是否大于當(dāng)前節(jié)點(diǎn)?如果是，向右走。

插入和刪除也非常快，平均花費(fèi)O(log n)的時(shí)間。但有一個(gè)缺點(diǎn)就是不能像數(shù)組那樣獲得隨機(jī)元素。

什么時(shí)候可以使用二叉搜索樹(shù)?

假設(shè)你需要為Facebook這樣的社交媒體應(yīng)用程序設(shè)計(jì)一個(gè)數(shù)據(jù)庫(kù)。該數(shù)據(jù)庫(kù)需要處理數(shù)百萬(wàn)個(gè)用戶名，并且需要在登錄期間快速檢索到其中一個(gè)用戶名。由于每天都有新注冊(cè)或刪除的賬戶，你也需要方便進(jìn)行插入和刪除的操作。

通過(guò)一個(gè)排序過(guò)的數(shù)組進(jìn)行二分搜索會(huì)非常快(需要花費(fèi)O(log  n)時(shí)間)，但是插入或刪除一個(gè)用戶名會(huì)導(dǎo)致整個(gè)數(shù)組重新排序，需要花費(fèi)O(n)時(shí)間，這取決于數(shù)組的大小，可能會(huì)相對(duì)慢一些。如果我們使用二叉搜索樹(shù)，插入或刪除的時(shí)間會(huì)快得多(花費(fèi)O(log  n)時(shí)間)。

如果有一個(gè)帶有名字的二叉搜索樹(shù)(比如這個(gè)《海底總動(dòng)員》的樹(shù))，就可以按字母順序排列。

在字母表中，Dory在Marlin之前，所以它是左邊的節(jié)點(diǎn)，而Moonfish在Marlin之后，所以它是右邊的節(jié)點(diǎn)。同樣地，在下一層搜索也遵循這個(gè)規(guī)律。Bruce在Crush之前，也在Dory和Marlin之前。Darla在Crush之后，但在Dory和Marlin之前。

現(xiàn)在準(zhǔn)備好，是時(shí)候?qū)ふ襈emo了!

尋找Nemo!

假設(shè)已經(jīng)有一個(gè)有效的二叉搜索樹(shù)，并且需要找到Nemo。因?yàn)槲覀冎罉?shù)中的節(jié)點(diǎn)是按字母順序排序的，所以這應(yīng)該相當(dāng)簡(jiǎn)單。

從Marlin開(kāi)始，左邊是Dory，右邊是Moonfish。我們知道Nemo在字母表中位于Marlin之后，所以我們將遍歷到正確的節(jié)點(diǎn)(Moonfish)。Nemo按字母順序是排在Moonfish之后的，所以繼續(xù)往下看Moonfish的右子節(jié)點(diǎn)。很幸運(yùn)，那是…Nemo!找到Nemo了!

效率很高。二叉搜索樹(shù)減少了整個(gè)搜索過(guò)程的時(shí)間復(fù)雜性!如果樹(shù)沒(méi)有分類，只是一個(gè)普通的樹(shù)形結(jié)構(gòu)呢?或者要證實(shí)這是個(gè)二叉搜索樹(shù)呢?目前有兩種不同的搜索技術(shù)可以實(shí)現(xiàn)這一點(diǎn)。

什么是廣度優(yōu)先搜索?

廣度優(yōu)先搜索是一種在樹(shù)(或圖形)中一次遍歷一級(jí)的方法，每次都從左到右在節(jié)點(diǎn)之間移動(dòng)。

在《海底總動(dòng)員》的例子中，Marlin首先會(huì)問(wèn)Dory，“你知道我兒子Nemo在哪里嗎?”如果它說(shuō)不，Marlin就會(huì)問(wèn)Moonfish同樣的問(wèn)題。如果它也說(shuō)不，Marlin會(huì)再下一層，問(wèn)Crush、Gill和Mr.  Ray，然后Marlin就找到Nemo了!

廣度優(yōu)先搜索

如果在Mr.  Ray之后沒(méi)有找到Nemo，Marlin會(huì)到下一級(jí)詢問(wèn)Bruce和Darla等等。使用廣度優(yōu)先搜索可以找到起始節(jié)點(diǎn)(Marlin)和目標(biāo)節(jié)點(diǎn)(Nemo)之間的最短距離。時(shí)間復(fù)雜度是O(n)，因?yàn)樵谧顗牡那闆r下，需要檢查每個(gè)節(jié)點(diǎn)才能找到Nemo。

什么是深度優(yōu)先搜索?

深度優(yōu)先搜索(Depth first  search)是一種從頂部節(jié)點(diǎn)一直向下遍歷到其最遠(yuǎn)子節(jié)點(diǎn)的樹(shù)(或圖形)的方法，然后在未找到目標(biāo)節(jié)點(diǎn)時(shí)再回去并嘗試其他路徑。

在《海底總動(dòng)員》的例子中，Marlin首先會(huì)問(wèn)Dory “你知道Nemo在哪里嗎?”  如果她不知道，他就會(huì)問(wèn)Crush同樣的問(wèn)題，因?yàn)镃rush是Dory最左邊的子節(jié)點(diǎn)。如果Crush也說(shuō)沒(méi)有，Marlin將移動(dòng)到下一級(jí)去問(wèn)Bruce，盡管他害怕成為鯊魚(yú)的點(diǎn)心，但也會(huì)問(wèn)問(wèn)他有沒(méi)有見(jiàn)到自己的兒子。

深度優(yōu)先搜索

如果Bruce說(shuō)沒(méi)看到Nemo，并向Marlin保證“魚(yú)是朋友，不是食物”，Marlin就需要回到上級(jí)，尋找另一個(gè)他還沒(méi)有問(wèn)到的節(jié)點(diǎn)。回到Crush那里，他會(huì)發(fā)現(xiàn)下一步應(yīng)該問(wèn)Darla。由于Crush的所有后代現(xiàn)在都被審問(wèn)過(guò)了，Marlin會(huì)回到Dory那里，檢查她其余的“后代”。Marlin需要把每個(gè)角色詢問(wèn)一遍后才能找到Nemo。

深度優(yōu)先搜索順序

與廣度優(yōu)先搜索一樣，深度優(yōu)先搜索也包括時(shí)間復(fù)雜度O(n)，但空間復(fù)雜度可能有所不同。深度優(yōu)先搜索通常占用較少的內(nèi)存或空間，假設(shè)可以在遍歷整個(gè)樹(shù)之前找到目標(biāo)節(jié)點(diǎn)。

由于二叉搜索樹(shù)中的每增加一級(jí)節(jié)點(diǎn)會(huì)加倍(至少對(duì)于平衡樹(shù)而言)，如果丟失的節(jié)點(diǎn)(Nemo)位于樹(shù)的較低位置，則可以使用深度優(yōu)先搜索來(lái)節(jié)省內(nèi)存。在最壞的情況下，兩種方法的空間復(fù)雜度都是O(n)。

關(guān)于二叉搜索樹(shù)以及如何通過(guò)代碼實(shí)現(xiàn)它們還有很多需要學(xué)習(xí)，但這個(gè)有趣的案例會(huì)成為你了解數(shù)據(jù)結(jié)構(gòu)的起點(diǎn)。

到此，相信大家對(duì)“如何通過(guò)代碼實(shí)現(xiàn)二叉搜索樹(shù)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！