廣度優(yōu)先搜索（BFS）
BFS是一層層逐漸深入的遍歷算法。
下面這個例子是用來幫我們更好的解釋該算法。
我們來一層一層的遍歷這棵樹。本例中，就是1-2-5-3-4-6-7.
0層/深度0：只有值為1的節(jié)點1層/深度1：有值為2和5的節(jié)點2層/深度2：有值為3、4、6、7的節(jié)點好，下面我們來編寫實現(xiàn)代碼。
首先用put方法將根節(jié)點添加到隊列中。當隊列不為空時迭代。獲取隊列中的第一個節(jié)點，然后輸出其值。將其左孩子和右孩子添加到隊列（如果它有孩子的話）。在隊列的幫助下我們將每一個節(jié)點的值一層層的輸出。以下是上述插圖的詳解：
A?是反的二叉搜索樹。子樹 7-5-8-6應(yīng)該在右邊，而子樹2-1-3 應(yīng)該在左邊。
B?是唯一正確的選項。它滿足二叉搜索樹的性質(zhì)。
C?有一個問題：值為4的那個節(jié)點應(yīng)該在根節(jié)點的左邊，因為這個節(jié)點的值比根節(jié)點的值5小。
讓我們用代碼實現(xiàn)一個二叉搜索樹！
現(xiàn)在是時候開始寫代碼了！
我們要干點什么？我們會插入一個新的節(jié)點，搜索一個值，刪除一些節(jié)點以及二叉搜索樹的平衡。
讓我們開始吧！
插入：向我們的樹添加新的節(jié)點
現(xiàn)在想像一下我們有一棵空樹，我們想將幾個節(jié)點添加到這棵空樹中，這幾個節(jié)點的值為：50、76、21、4、32、100、64、52。
首先我們需要知道的是，50是不是這棵樹的根節(jié)點。
現(xiàn)在我們開始一個一個的插入節(jié)點。
76比50大，所以76插入在右邊。21比50小，所以21插入在左邊。4比50小。但是50已經(jīng)有了值為21的左孩子。然后，4又比21小，所以將其插入在21的左邊。32比50小。但是50已經(jīng)有了值為21的左孩子。然后，32又比21大，所以將其插入在21的右邊。100比50大。但是50已經(jīng)有了一個值為76的右孩子。然后，100又比76大，所以將其插入在76的右邊。64比50大。但是50已經(jīng)有了一個值為76的右孩子。然后，64又比76小，所以將其插入在76的左邊。52比50大。但是50已經(jīng)有了一個值為76的右孩子。52又比76小，但是76也有一個值為64左孩子。52又比64小，所以將52插入在64的左邊。
你注意到這里的模式了嗎？
讓我們把它分解。
新節(jié)點值大于當前節(jié)點還是小于當前節(jié)點？如果新節(jié)點的值大于當前節(jié)點，則轉(zhuǎn)到右子樹。如果當前節(jié)點沒有右孩子，則在那里插入新節(jié)點，否則返回步驟1。如果新節(jié)點的值小于當前節(jié)點，則轉(zhuǎn)到左子樹。如果當前節(jié)點沒有左孩子，則在那里插入新節(jié)點，否則返回步驟1。這里我們沒有處理特殊情況。當新節(jié)點的值等于節(jié)點的當前值時，使用規(guī)則3?？紤]在子樹的左側(cè)插入相等的值。現(xiàn)在我們來編碼。
現(xiàn)在我們想知道是否有一個節(jié)點的值為52。
讓我們把它分解。
我們以根節(jié)點作為當前節(jié)點開始。給定值小于當前節(jié)點值嗎？如果是，那么我將在左子樹上查找它。給定值大于當前節(jié)點值嗎？如果是，那么我們將在右子樹上查找它。如果規(guī)則?#1 和 #2 均為假，我們可以比較當前節(jié)點值和給定值是否相等。如果返回真，那么我們可以說：“是的，我們的樹擁有給定的值?！?否則，我們說： “不，我們的樹沒有給定的值。”代碼如下：
class?BinarySearchTree:????def?__init__(self,?value):????????self.value?=?value????????self.left_child?=?None????????self.right_child?=?None????def?find_node(self,?value):????????if?value?<?self.value?and?self.left_child:????????????return?self.left_child.find_node(value)????????if?value?>?self.value?and?self.right_child:????????????return?self.right_child.find_node(value)????????return?value?==?self.value
代碼分析：
第8行和第9行歸于規(guī)則#1。第10行和第11行歸于規(guī)則#2。第13行歸于規(guī)則#3。我們?nèi)绾螠y試它？
讓我們通過初始化值為15的根節(jié)點創(chuàng)建二叉查找樹。
bst?=?BinarySearchTree(15)
現(xiàn)在我們將插入許多新節(jié)點。
bst.insert_node(10)bst.insert_node(8)bst.insert_node(12)bst.insert_node(20)bst.insert_node(17)bst.insert_node(25)bst.insert_node(19)
對于每個插入的節(jié)點，我們測試是否?find_node 方法真地管用。
print(bst.find_node(15))?#?Trueprint(bst.find_node(10))?#?Trueprint(bst.find_node(8))?#?Trueprint(bst.find_node(12))?#?Trueprint(bst.find_node(20))?#?Trueprint(bst.find_node(17))?#?Trueprint(bst.find_node(25))?#?Trueprint(bst.find_node(19))?#?True
是的，它對這些給定值管用！讓我們測試一個二叉查找樹中不存在的值。
print(bst.find_node(0))?#?False
查找完畢
刪除：移除和組織
刪除是一個更復(fù)雜的算法，因為我們需要處理不同的情況。對于給定值，我們需要刪除具有此值的節(jié)點。想象一下這個節(jié)點的以下場景：它沒有孩子，有一個孩子，或者有兩個孩子。
場景 #1：?一個沒有孩子的節(jié)點（葉節(jié)點） 。#????????|50|??????????????????????????????|50|#??????/??????\???????????????????????????/????\#????|30|?????|70|???(DELETE?20)?--->???|30|???|70|#???/????\????????????????????????????????\#?|20|???|40|?????????????????????????????|40|
如果要刪除的節(jié)點沒有子節(jié)點，我們簡單地刪除它。該算法不需要重組樹。
場景 #2：?僅有一個孩子（左或右孩子）的節(jié)點。#????????|50|??????????????????????????????|50|#??????/??????\???????????????????????????/????\#????|30|?????|70|???(DELETE?30)?--->???|20|???|70|#???/????????????#?|20|
在這種情況下，我們的算法需要使節(jié)點的父節(jié)點指向子節(jié)點。如果節(jié)點是左孩子，則使其父節(jié)點指向其子節(jié)點。如果節(jié)點是右孩子，則使其父節(jié)點指向其子節(jié)點。
場景 #3：?有兩個孩子的節(jié)點。#????????|50|??????????????????????????????|50|#??????/??????\???????????????????????????/????\#????|30|?????|70|???(DELETE?30)?--->???|40|???|70|#???/????\?????????????????????????????/#?|20|???|40|????????????????????????|20|
當節(jié)點有兩個孩子，則需要從該節(jié)點的右孩子開始，找到具有最小值的節(jié)點。我們將把具有最小值的這個節(jié)點置于被刪除的節(jié)點的位置。
是時候編碼了。
def?remove_node(self,?value,?parent):????if?value?<?self.value?and?self.left_child:????????return?self.left_child.remove_node(value,?self)????elif?value?<?self.value:????????return?False????elif?value?>?self.value?and?self.right_child:????????return?self.right_child.remove_node(value,?self)????elif?value?>?self.value:????????return?False????else:????????if?self.left_child?is?None?and?self.right_child?is?None?and?self?==?parent.left_child:????????????parent.left_child?=?None????????????self.clear_node()????????elif?self.left_child?is?None?and?self.right_child?is?None?and?self?==?parent.right_child:????????????parent.right_child?=?None????????????self.clear_node()????????elif?self.left_child?and?self.right_child?is?None?and?self?==?parent.left_child:????????????parent.left_child?=?self.left_child????????????self.clear_node()????????elif?self.left_child?and?self.right_child?is?None?and?self?==?parent.right_child:????????????parent.right_child?=?self.left_child????????????self.clear_node()????????elif?self.right_child?and?self.left_child?is?None?and?self?==?parent.left_child:????????????parent.left_child?=?self.right_child????????????self.clear_node()????????elif?self.right_child?and?self.left_child?is?None?and?self?==?parent.right_child:????????????parent.right_child?=?self.right_child????????????self.clear_node()????????else:????????????self.value?=?self.right_child.find_minimum_value()????????????self.right_child.remove_node(self.value,?self)????????return?True首先: 注意下參數(shù) value 和 parent 。我們想找到值等于該 value 的 node ，并且該 node 的父節(jié)點對于刪除該 node 是至關(guān)重要的。其次: 注意下返回值。我們的算法將會返回一個布爾值。我們的算法在找到并刪除該節(jié)點時返回 true 。否則返回 false 。第2行到第9行：我們開始查找等于我們要查找的給定的 value 的 node 。如果該 value 小于 current node 值，我們進入左子樹，遞歸處理（當且僅當，current node 有左孩子）。如果該值大于，則進入右子樹。遞歸處理。第10行: 我們開始考慮刪除算法。第11行到第13行: 我們處理了沒有孩子、并且是父節(jié)點的左孩子的節(jié)點。我們通過設(shè)置父節(jié)點的左孩子為空來刪除該節(jié)點。第14行和第15行: 我們處理了沒有孩子、并且是父節(jié)點的右孩子的節(jié)點。我們通過設(shè)置父節(jié)點的右孩子為空來刪除該節(jié)點。清除節(jié)點的方法：我將會在后續(xù)文章中給出 clear_node 的代碼。該函數(shù)將節(jié)點的左孩子、右孩子和值都設(shè)置為空。第16行到第18行: 我們處理了只有一個孩子（左孩子）、并且它是其父節(jié)點的左孩子的節(jié)點。我們將父節(jié)點的左孩子設(shè)置為當前節(jié)點的左孩子（這是它唯一擁有的孩子）。第19行到第21行: 我們處理了只有一個孩子（左孩子）、并且它是其父節(jié)點的右孩子的節(jié)點。我們將父節(jié)點的右孩子設(shè)置為當前節(jié)點的左孩子（這是它唯一擁有的孩子）。第22行到第24行: 我們處理了只有一個孩子（右孩子），并且是其父節(jié)點的左孩子的節(jié)點。我們將父節(jié)點的左孩子設(shè)置為當前節(jié)點的右孩子（這是它唯一的孩子）。第25行到第27行: 我們處理了只有一個孩子（右孩子），并且它是其父節(jié)點的右孩子的節(jié)點。我們將父節(jié)點的右孩子設(shè)置為當前節(jié)點的右孩子（這是它唯一的孩子）。第28行到第30行: 我們處理了同時擁有左孩子和右孩子的節(jié)點。我們獲取擁有最小值的節(jié)點（代碼隨后給出），并將其值設(shè)置給當前節(jié)點。通過刪除最小的節(jié)點完成節(jié)點移除。第32行: 如果我們找到了要查找的節(jié)點，就需要返回 true 。從第11行到第31行，我們處理了這些情況。所以直接返回 true ，這就夠了。clear_node 方法：設(shè)置節(jié)點的三個屬性為空——(value,?left_child, and?right_child)
def?clear_node(self):????self.value?=?None????self.left_child?=?None????self.right_child?=?Nonefind_minimum_value方法：一路向下找最左側(cè)的。如果我們無法找到任何節(jié)點，我們找其中最小的。
def?find_minimum_value(self):????if?self.left_child:????????return?self.left_child.find_minimum_value()????else:????????return?self.value
讓我們測試一下。
我們將使用這個樹來測試我們的 remove_node 算法。
#????????|15|#??????/??????\#????|10|?????|20|#???/????\????/????\#?|8|???|12|?|17|?|25|#??????????????\#??????????????|19|
刪除值為 8 的節(jié)點。它是一個沒有孩子的節(jié)點。
print(bst.remove_node(8,?None))?#?Truebst.pre_order_traversal()#?????|15|#???/??????\#?|10|?????|20|#????\????/????\#???|12|?|17|?|25|#??????????\#??????????|19|
刪除值為 17 的節(jié)點。它是一個只有一個孩子的節(jié)點。
print(bst.remove_node(17,?None))?#?Truebst.pre_order_traversal()#????????|15|#??????/??????\#????|10|?????|20|#???????\????/????\#??????|12|?|19|?|25|
最后，刪除一個擁有兩個孩子的節(jié)點。它就是我們的樹的根節(jié)點。
print(bst.remove_node(15,?None))?#?Truebst.pre_order_traversal()#????????|19|#??????/??????\#????|10|?????|20|#????????\????????\#????????|12|?????|25|
測試完成。
- 蜜度索驥：以跨模態(tài)檢索技術(shù)助力“企宣”向上生長
- 1—8月我國軟件業(yè)務(wù)收入85492億元，同比增長11.2％
- 合合信息啟信寶數(shù)據(jù)產(chǎn)業(yè)洞察：長三角地區(qū)數(shù)據(jù)企業(yè)超48000家，數(shù)量領(lǐng)跑全國
- 2025年全球網(wǎng)絡(luò)安全支出將激增15% | 行業(yè)觀察
- 華為數(shù)據(jù)存儲兩大新品齊發(fā)：全面閃存化，全面向AI
- 數(shù)據(jù)中心太耗電，微軟攜手Constellation Energy探索核能供電新途徑
- 戴爾一周內(nèi)發(fā)生兩起數(shù)據(jù)泄露事件，Atlassian工具成泄露源頭
- 華為ICT學(xué)院年會2024舉辦，ICT學(xué)院3.0計劃正式啟航
- 華為啟動全球金融伙伴“融海計劃”，共創(chuàng)行業(yè)新價值
- 華為聯(lián)合多家伙伴發(fā)布《現(xiàn)代化金融核心系統(tǒng)白皮書：實踐篇》
- 華為發(fā)布數(shù)據(jù)智能解決方案5.0，加速金融大模型應(yīng)用從“賦能”到“產(chǎn)能”
免責聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準確性及可靠性，但不保證有關(guān)資料的準確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負責。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負任何法律責任。任何單位或個人認為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實內(nèi)容時，應(yīng)及時向本網(wǎng)站提出書面權(quán)利通知或不實情況說明，并提供身份證明、權(quán)屬證明及詳細侵權(quán)或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。
