廣度優(yōu)先搜索（BFS）
BFS是一層層逐漸深入的遍歷算法。
下面這個例子是用來幫我們更好的解釋該算法。
我們來一層一層的遍歷這棵樹。本例中，就是1-2-5-3-4-6-7.
0層/深度0：只有值為1的節(jié)點(diǎn)1層/深度1：有值為2和5的節(jié)點(diǎn)2層/深度2：有值為3、4、6、7的節(jié)點(diǎn)好，下面我們來編寫實(shí)現(xiàn)代碼。
首先用put方法將根節(jié)點(diǎn)添加到隊列中。當(dāng)隊列不為空時迭代。獲取隊列中的第一個節(jié)點(diǎn)，然后輸出其值。將其左孩子和右孩子添加到隊列（如果它有孩子的話）。在隊列的幫助下我們將每一個節(jié)點(diǎn)的值一層層的輸出。以下是上述插圖的詳解：
A?是反的二叉搜索樹。子樹 7-5-8-6應(yīng)該在右邊，而子樹2-1-3 應(yīng)該在左邊。
B?是唯一正確的選項(xiàng)。它滿足二叉搜索樹的性質(zhì)。
C?有一個問題：值為4的那個節(jié)點(diǎn)應(yīng)該在根節(jié)點(diǎn)的左邊，因?yàn)檫@個節(jié)點(diǎn)的值比根節(jié)點(diǎn)的值5小。
讓我們用代碼實(shí)現(xiàn)一個二叉搜索樹！
現(xiàn)在是時候開始寫代碼了！
我們要干點(diǎn)什么？我們會插入一個新的節(jié)點(diǎn)，搜索一個值，刪除一些節(jié)點(diǎn)以及二叉搜索樹的平衡。
讓我們開始吧！
插入：向我們的樹添加新的節(jié)點(diǎn)
現(xiàn)在想像一下我們有一棵空樹，我們想將幾個節(jié)點(diǎn)添加到這棵空樹中，這幾個節(jié)點(diǎn)的值為：50、76、21、4、32、100、64、52。
首先我們需要知道的是，50是不是這棵樹的根節(jié)點(diǎn)。
現(xiàn)在我們開始一個一個的插入節(jié)點(diǎn)。
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é)點(diǎn)值大于當(dāng)前節(jié)點(diǎn)還是小于當(dāng)前節(jié)點(diǎn)？如果新節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)，則轉(zhuǎn)到右子樹。如果當(dāng)前節(jié)點(diǎn)沒有右孩子，則在那里插入新節(jié)點(diǎn)，否則返回步驟1。如果新節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)，則轉(zhuǎn)到左子樹。如果當(dāng)前節(jié)點(diǎn)沒有左孩子，則在那里插入新節(jié)點(diǎn)，否則返回步驟1。這里我們沒有處理特殊情況。當(dāng)新節(jié)點(diǎn)的值等于節(jié)點(diǎn)的當(dāng)前值時，使用規(guī)則3?？紤]在子樹的左側(cè)插入相等的值。現(xiàn)在我們來編碼。
現(xiàn)在我們想知道是否有一個節(jié)點(diǎn)的值為52。
讓我們把它分解。
我們以根節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)開始。給定值小于當(dāng)前節(jié)點(diǎn)值嗎？如果是，那么我將在左子樹上查找它。給定值大于當(dāng)前節(jié)點(diǎn)值嗎？如果是，那么我們將在右子樹上查找它。如果規(guī)則?#1 和 #2 均為假，我們可以比較當(dāng)前節(jié)點(diǎn)值和給定值是否相等。如果返回真，那么我們可以說：“是的，我們的樹擁有給定的值?！?否則，我們說： “不，我們的樹沒有給定的值?！?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。我們?nèi)绾螠y試它？
讓我們通過初始化值為15的根節(jié)點(diǎn)創(chuàng)建二叉查找樹。
bst?=?BinarySearchTree(15)
現(xiàn)在我們將插入許多新節(jié)點(diǎn)。
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é)點(diǎn)，我們測試是否?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ù)雜的算法，因?yàn)槲覀冃枰幚聿煌那闆r。對于給定值，我們需要刪除具有此值的節(jié)點(diǎn)。想象一下這個節(jié)點(diǎn)的以下場景：它沒有孩子，有一個孩子，或者有兩個孩子。
場景 #1：?一個沒有孩子的節(jié)點(diǎn)（葉節(jié)點(diǎn)） 。#????????|50|??????????????????????????????|50|#??????/??????\???????????????????????????/????\#????|30|?????|70|???(DELETE?20)?--->???|30|???|70|#???/????\????????????????????????????????\#?|20|???|40|?????????????????????????????|40|
如果要刪除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們簡單地刪除它。該算法不需要重組樹。
場景 #2：?僅有一個孩子（左或右孩子）的節(jié)點(diǎn)。#????????|50|??????????????????????????????|50|#??????/??????\???????????????????????????/????\#????|30|?????|70|???(DELETE?30)?--->???|20|???|70|#???/????????????#?|20|
在這種情況下，我們的算法需要使節(jié)點(diǎn)的父節(jié)點(diǎn)指向子節(jié)點(diǎn)。如果節(jié)點(diǎn)是左孩子，則使其父節(jié)點(diǎn)指向其子節(jié)點(diǎn)。如果節(jié)點(diǎn)是右孩子，則使其父節(jié)點(diǎn)指向其子節(jié)點(diǎn)。
場景 #3：?有兩個孩子的節(jié)點(diǎn)。#????????|50|??????????????????????????????|50|#??????/??????\???????????????????????????/????\#????|30|?????|70|???(DELETE?30)?--->???|40|???|70|#???/????\?????????????????????????????/#?|20|???|40|????????????????????????|20|
當(dāng)節(jié)點(diǎn)有兩個孩子，則需要從該節(jié)點(diǎn)的右孩子開始，找到具有最小值的節(jié)點(diǎn)。我們將把具有最小值的這個節(jié)點(diǎn)置于被刪除的節(jié)點(diǎn)的位置。
是時候編碼了。
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é)點(diǎn)對于刪除該 node 是至關(guān)重要的。其次: 注意下返回值。我們的算法將會返回一個布爾值。我們的算法在找到并刪除該節(jié)點(diǎn)時返回 true 。否則返回 false 。第2行到第9行：我們開始查找等于我們要查找的給定的 value 的 node 。如果該 value 小于 current node 值，我們進(jìn)入左子樹，遞歸處理（當(dāng)且僅當(dāng)，current node 有左孩子）。如果該值大于，則進(jìn)入右子樹。遞歸處理。第10行: 我們開始考慮刪除算法。第11行到第13行: 我們處理了沒有孩子、并且是父節(jié)點(diǎn)的左孩子的節(jié)點(diǎn)。我們通過設(shè)置父節(jié)點(diǎn)的左孩子為空來刪除該節(jié)點(diǎn)。第14行和第15行: 我們處理了沒有孩子、并且是父節(jié)點(diǎn)的右孩子的節(jié)點(diǎn)。我們通過設(shè)置父節(jié)點(diǎn)的右孩子為空來刪除該節(jié)點(diǎn)。清除節(jié)點(diǎn)的方法：我將會在后續(xù)文章中給出 clear_node 的代碼。該函數(shù)將節(jié)點(diǎn)的左孩子、右孩子和值都設(shè)置為空。第16行到第18行: 我們處理了只有一個孩子（左孩子）、并且它是其父節(jié)點(diǎn)的左孩子的節(jié)點(diǎn)。我們將父節(jié)點(diǎn)的左孩子設(shè)置為當(dāng)前節(jié)點(diǎn)的左孩子（這是它唯一擁有的孩子）。第19行到第21行: 我們處理了只有一個孩子（左孩子）、并且它是其父節(jié)點(diǎn)的右孩子的節(jié)點(diǎn)。我們將父節(jié)點(diǎn)的右孩子設(shè)置為當(dāng)前節(jié)點(diǎn)的左孩子（這是它唯一擁有的孩子）。第22行到第24行: 我們處理了只有一個孩子（右孩子），并且是其父節(jié)點(diǎn)的左孩子的節(jié)點(diǎn)。我們將父節(jié)點(diǎn)的左孩子設(shè)置為當(dāng)前節(jié)點(diǎn)的右孩子（這是它唯一的孩子）。第25行到第27行: 我們處理了只有一個孩子（右孩子），并且它是其父節(jié)點(diǎn)的右孩子的節(jié)點(diǎn)。我們將父節(jié)點(diǎn)的右孩子設(shè)置為當(dāng)前節(jié)點(diǎn)的右孩子（這是它唯一的孩子）。第28行到第30行: 我們處理了同時擁有左孩子和右孩子的節(jié)點(diǎn)。我們獲取擁有最小值的節(jié)點(diǎn)（代碼隨后給出），并將其值設(shè)置給當(dāng)前節(jié)點(diǎn)。通過刪除最小的節(jié)點(diǎn)完成節(jié)點(diǎn)移除。第32行: 如果我們找到了要查找的節(jié)點(diǎn)，就需要返回 true 。從第11行到第31行，我們處理了這些情況。所以直接返回 true ，這就夠了。clear_node 方法：設(shè)置節(jié)點(diǎn)的三個屬性為空——(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é)點(diǎn)，我們找其中最小的。
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é)點(diǎn)。它是一個沒有孩子的節(jié)點(diǎn)。
print(bst.remove_node(8,?None))?#?Truebst.pre_order_traversal()#?????|15|#???/??????\#?|10|?????|20|#????\????/????\#???|12|?|17|?|25|#??????????\#??????????|19|
刪除值為 17 的節(jié)點(diǎn)。它是一個只有一個孩子的節(jié)點(diǎn)。
print(bst.remove_node(17,?None))?#?Truebst.pre_order_traversal()#????????|15|#??????/??????\#????|10|?????|20|#???????\????/????\#??????|12|?|19|?|25|
最后，刪除一個擁有兩個孩子的節(jié)點(diǎn)。它就是我們的樹的根節(jié)點(diǎn)。
print(bst.remove_node(15,?None))?#?Truebst.pre_order_traversal()#????????|19|#??????/??????\#????|10|?????|20|#????????\????????\#????????|12|?????|25|
測試完成。
- 蜜度索驥：以跨模態(tài)檢索技術(shù)助力“企宣”向上生長
- 長江存儲發(fā)布聲明：從無“借殼上市”意愿
- 泛微·數(shù)智大腦Xiaoe.AI正式發(fā)布，千人現(xiàn)場體驗(yàn)數(shù)智化運(yùn)營場景
- IDC：2024年第三季度北美IT分銷商收入增長至202億美元
- AI成為雙刃劍！凱捷調(diào)查：97%組織遭遇過GenAI漏洞攻擊
- openEuler開源五年樹立新里程碑，累計裝機(jī)量突破1000萬
- 創(chuàng)想 華彩新程！2024柯尼卡美能達(dá)媒體溝通會煥新增長之道
- 操作系統(tǒng)大會2024即將在京召開，見證openEuler發(fā)展新里程
- Gartner：AI引領(lǐng)歐洲IT支出激增，2025年將支出1.28萬億美元
- IDC：中國數(shù)字化轉(zhuǎn)型支出五年復(fù)合增長率約為15.6% 高于全球整體增速
- 2028年中國數(shù)字化轉(zhuǎn)型總體市場規(guī)模將超7300億美元
免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請進(jìn)一步核實(shí)，并對任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負(fù)任何法律責(zé)任。任何單位或個人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實(shí)內(nèi)容時，應(yīng)及時向本網(wǎng)站提出書面權(quán)利通知或不實(shí)情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實(shí)情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實(shí)，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。
