廣度優(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應該在右邊，而子樹2-1-3 應該在左邊。
B?是唯一正確的選項。它滿足二叉搜索樹的性質。
C?有一個問題：值為4的那個節(jié)點應該在根節(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é)點，則轉到右子樹。如果當前節(jié)點沒有右孩子，則在那里插入新節(jié)點，否則返回步驟1。如果新節(jié)點的值小于當前節(jié)點，則轉到左子樹。如果當前節(jié)點沒有左孩子，則在那里插入新節(jié)點，否則返回步驟1。這里我們沒有處理特殊情況。當新節(jié)點的值等于節(jié)點的當前值時，使用規(guī)則3?？紤]在子樹的左側插入相等的值。現(xiàn)在我們來編碼。
現(xiàn)在我們想知道是否有一個節(jié)點的值為52。
讓我們把它分解。
我們以根節(jié)點作為當前節(jié)點開始。給定值小于當前節(jié)點值嗎？如果是，那么我將在左子樹上查找它。給定值大于當前節(jié)點值嗎？如果是，那么我們將在右子樹上查找它。如果規(guī)則?#1 和 #2 均為假，我們可以比較當前節(jié)點值和給定值是否相等。如果返回真，那么我們可以說：“是的，我們的樹擁有給定的值?！?否則，我們說： “不，我們的樹沒有給定的值?！?p>代碼如下：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。我們如何測試它？
讓我們通過初始化值為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
查找完畢
刪除：移除和組織
刪除是一個更復雜的算法，因為我們需要處理不同的情況。對于給定值，我們需要刪除具有此值的節(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 是至關重要的。其次: 注意下返回值。我們的算法將會返回一個布爾值。我們的算法在找到并刪除該節(jié)點時返回 true 。否則返回 false 。第2行到第9行：我們開始查找等于我們要查找的給定的 value 的 node 。如果該 value 小于 current node 值，我們進入左子樹，遞歸處理（當且僅當，current node 有左孩子）。如果該值大于，則進入右子樹。遞歸處理。第10行: 我們開始考慮刪除算法。第11行到第13行: 我們處理了沒有孩子、并且是父節(jié)點的左孩子的節(jié)點。我們通過設置父節(jié)點的左孩子為空來刪除該節(jié)點。第14行和第15行: 我們處理了沒有孩子、并且是父節(jié)點的右孩子的節(jié)點。我們通過設置父節(jié)點的右孩子為空來刪除該節(jié)點。清除節(jié)點的方法：我將會在后續(xù)文章中給出 clear_node 的代碼。該函數(shù)將節(jié)點的左孩子、右孩子和值都設置為空。第16行到第18行: 我們處理了只有一個孩子（左孩子）、并且它是其父節(jié)點的左孩子的節(jié)點。我們將父節(jié)點的左孩子設置為當前節(jié)點的左孩子（這是它唯一擁有的孩子）。第19行到第21行: 我們處理了只有一個孩子（左孩子）、并且它是其父節(jié)點的右孩子的節(jié)點。我們將父節(jié)點的右孩子設置為當前節(jié)點的左孩子（這是它唯一擁有的孩子）。第22行到第24行: 我們處理了只有一個孩子（右孩子），并且是其父節(jié)點的左孩子的節(jié)點。我們將父節(jié)點的左孩子設置為當前節(jié)點的右孩子（這是它唯一的孩子）。第25行到第27行: 我們處理了只有一個孩子（右孩子），并且它是其父節(jié)點的右孩子的節(jié)點。我們將父節(jié)點的右孩子設置為當前節(jié)點的右孩子（這是它唯一的孩子）。第28行到第30行: 我們處理了同時擁有左孩子和右孩子的節(jié)點。我們獲取擁有最小值的節(jié)點（代碼隨后給出），并將其值設置給當前節(jié)點。通過刪除最小的節(jié)點完成節(jié)點移除。第32行: 如果我們找到了要查找的節(jié)點，就需要返回 true 。從第11行到第31行，我們處理了這些情況。所以直接返回 true ，這就夠了。clear_node 方法：設置節(jié)點的三個屬性為空——(value,?left_child, and?right_child)
def?clear_node(self):????self.value?=?None????self.left_child?=?None????self.right_child?=?Nonefind_minimum_value方法：一路向下找最左側的。如果我們無法找到任何節(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)檢索技術助力“企宣”向上生長
- IDC：三季度全球以太網(wǎng)交換機收入同比下降7.9%、環(huán)比增長6.6%
- Fortinet李宏凱：2025年在中國大陸啟動SASE PoP節(jié)點部署 助力企業(yè)出海
- Fortinet李宏凱：2024年Fortinet全球客戶已超80萬
- 央國企采購管理升級，合合信息旗下啟信慧眼以科技破局難點
- Apache Struts重大漏洞被黑客利用，遠程代碼執(zhí)行風險加劇
- Crunchbase：2024年AI網(wǎng)絡安全行業(yè)風險投資超過26億美元
- 調查報告：AI與云重塑IT格局，77%的IT領導者視網(wǎng)絡安全為首要挑戰(zhàn)
- 長江存儲發(fā)布聲明：從無“借殼上市”意愿
- 泛微·數(shù)智大腦Xiaoe.AI正式發(fā)布，千人現(xiàn)場體驗數(shù)智化運營場景
- IDC：2024年第三季度北美IT分銷商收入增長至202億美元
免責聲明：本網(wǎng)站內容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準確性及可靠性，但不保證有關資料的準確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負責。本網(wǎng)站對有關資料所引致的錯誤、不確或遺漏，概不負任何法律責任。任何單位或個人認為本網(wǎng)站中的網(wǎng)頁或鏈接內容可能涉嫌侵犯其知識產(chǎn)權或存在不實內容時，應及時向本網(wǎng)站提出書面權利通知或不實情況說明，并提供身份證明、權屬證明及詳細侵權或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關文章源頭核實，溝通刪除相關內容或斷開相關鏈接。
