數據結構中你需要知道的關於樹的一切

廣度優先搜索（BFS）

BFS是一層層逐漸深入的遍歷演算法。

下面這個例子是用來幫我們更好的解釋該演算法。

我們來一層一層的遍歷這棵樹。本例中，就是1-2-5-3-4-6-7.

0層/深度0：只有值為1的節點

1層/深度1：有值為2和5的節點

2層/深度2：有值為3、4、6、7的節點

好，下面我們來編寫實現代碼。

defbfs(self):queue = Queue() queue.put(self)whilenotqueue.empty(): current_node = queue.get() print(current_node.value)ifcurrent_node.left_child: queue.put(current_node.left_child)ifcurrent_node.right_child: queue.put(current_node.right_child)

為了實現BFS演算法，我們需要用到一個數據結構，那就是隊列。

隊列具體是用來幹什麼的呢？

請看下面解釋。

首先用put方法將根節點添加到隊列中。

當隊列不為空時迭代。

獲取隊列中的第一個節點，然後輸出其值。

將其左孩子和右孩子添加到隊列（如果它有孩子的話）。

在隊列的幫助下我們將每一個節點的值一層層的輸出。

二叉搜索樹

二叉搜索樹有時候被稱為二叉有序樹或二叉排序樹，二叉搜索樹的值存儲在有序的順序中，因此，查找表和其他的操作可以使用折半查找原理。——Wikipedia

二叉搜索樹中的一個重要性質是，二叉搜索樹中一個節點的值大於其左子樹任一節點的值，但是小於其右子樹任一節點的值。

以下是上述插圖的詳解：

A 是反的二叉搜索樹。子樹 7-5-8-6應該在右邊，而子樹2-1-3 應該在左邊。

B 是唯一正確的選項。它滿足二叉搜索樹的性質。

C 有一個問題：值為4的那個節點應該在根節點的左邊，因為這個節點的值比根節點的值5小。

讓我們用代碼實現一個二叉搜索樹！

現在是時候開始寫代碼了！

我們要干點什麼？我們會插入一個新的節點，搜索一個值，刪除一些節點以及二叉搜索樹的平衡。

讓我們開始吧！

插入：向我們的樹添加新的節點

現在想像一下我們有一棵空樹，我們想將幾個節點添加到這棵空樹中，這幾個節點的值為：50、76、21、4、32、100、64、52。

首先我們需要知道的是，50是不是這棵樹的根節點。

現在我們開始一個一個的插入節點。

76比50大，所以76插入在右邊。

21比50小，所以21插入在左邊。

4比50小。但是50已經有了值為21的左孩子。然後，4又比21小，所以將其插入在21的左邊。

32比50小。但是50已經有了值為21的左孩子。然後，32又比21大，所以將其插入在21的右邊。

100比50大。但是50已經有了一個值為76的右孩子。然後，100又比76大，所以將其插入在76的右邊。

64比50大。但是50已經有了一個值為76的右孩子。然後，64又比76小，所以將其插入在76的左邊。

52比50大。但是50已經有了一個值為76的右孩子。52又比76小，但是76也有一個值為64左孩子。52又比64小，所以將52插入在64的左邊。

你注意到這裡的模式了嗎？

讓我們把它分解。

新節點值大於當前節點還是小於當前節點？

如果新節點的值大於當前節點，則轉到右子樹。如果當前節點沒有右孩子，則在那裡插入新節點，否則返回步驟1。

如果新節點的值小於當前節點，則轉到左子樹。如果當前節點沒有左孩子，則在那裡插入新節點，否則返回步驟1。

這裡我們沒有處理特殊情況。當新節點的值等於節點的當前值時，使用規則3。考慮在子樹的左側插入相等的值。

現在我們來編碼。

class BinarySearchTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None def insert_node(self, value): if value

看起來很簡單。

該演算法的強大之處是其遞歸部分，即第9行和第13行。這兩行代碼均調用 insert_node 方法，並分別為其左孩子和右孩子使用它。第11行和第15行則在子節點處插入新節點。

我們來搜索節點值

我們現在要構建的演算法是關於搜索的。對於給定的值（整數），我們會搜索出我們的二叉查找樹有或者沒有這個值。

需要注意的一個重要事項是我們如何定義樹的插入演算法。 首先我們有根節點。所有左子樹的節點值都比根節點小。所有右子樹的節點值都比根節點大。

讓我們看一個例子。

假設我們有這棵樹。

現在我們想知道是否有一個節點的值為52。

讓我們把它分解。

我們以根節點作為當前節點開始。給定值小於當前節點值嗎？如果是，那麼我將在左子樹上查找它。

給定值大於當前節點值嗎？如果是，那麼我們將在右子樹上查找它。

如果規則 #1 和 #2 均為假，我們可以比較當前節點值和給定值是否相等。如果返回真，那麼我們可以說：「是的，我們的樹擁有給定的值。」 否則，我們說： 「不，我們的樹沒有給定的值。」

代碼如下：

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行歸於規則#1。

第10行和第11行歸於規則#2。

第13行歸於規則#3。

我們如何測試它？

讓我們通過初始化值為15的根節點創建二叉查找樹。

bst = BinarySearchTree(15)

現在我們將插入許多新節點。

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)

對於每個插入的節點，我們測試是否 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

查找完畢

刪除：移除和組織

刪除是一個更複雜的演算法，因為我們需要處理不同的情況。對於給定值，我們需要刪除具有此值的節點。想像一下這個節點的以下場景：它沒有孩子，有一個孩子，或者有兩個孩子。

場景 #1： 一個沒有孩子的節點（葉節點） 。

# |50| |50|# / / # |30| |70| (DELETE 20) ---> |30| |70|# / # |20| |40| |40|

如果要刪除的節點沒有子節點，我們簡單地刪除它。該演算法不需要重組樹。

場景 #2： 僅有一個孩子（左或右孩子）的節點。

# |50| |50|# / / # |30| |70| (DELETE 30) ---> |20| |70|# / # |20|

在這種情況下，我們的演算法需要使節點的父節點指向子節點。如果節點是左孩子，則使其父節點指向其子節點。如果節點是右孩子，則使其父節點指向其子節點。

場景 #3： 有兩個孩子的節點。

# |50| |50|# / / # |30| |70| (DELETE 30) ---> |40| |70|# / /# |20| |40| |20|

當節點有兩個孩子，則需要從該節點的右孩子開始，找到具有最小值的節點。我們將把具有最小值的這個節點置於被刪除的節點的位置。

是時候編碼了。

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

首先: 注意下參數 value 和 parent 。我們想找到值等於該 value 的 node ，並且該 node 的父節點對於刪除該 node 是至關重要的。

其次: 注意下返回值。我們的演算法將會返回一個布爾值。我們的演算法在找到並刪除該節點時返回 true 。否則返回 false 。

第2行到第9行：我們開始查找等於我們要查找的給定的 value 的 node 。如果該 value 小於 current node 值，我們進入左子樹，遞歸處理（當且僅當，current node 有左孩子）。如果該值大於，則進入右子樹。遞歸處理。

第10行: 我們開始考慮刪除演算法。

第11行到第13行: 我們處理了沒有孩子、並且是父節點的左孩子的節點。我們通過設置父節點的左孩子為空來刪除該節點。

第14行和第15行: 我們處理了沒有孩子、並且是父節點的右孩子的節點。我們通過設置父節點的右孩子為空來刪除該節點。

清除節點的方法：我將會在後續文章中給出 clear_node 的代碼。該函數將節點的左孩子、右孩子和值都設置為空。

第16行到第18行: 我們處理了只有一個孩子（左孩子）、並且它是其父節點的左孩子的節點。我們將父節點的左孩子設置為當前節點的左孩子（這是它唯一擁有的孩子）。

第19行到第21行: 我們處理了只有一個孩子（左孩子）、並且它是其父節點的右孩子的節點。我們將父節點的右孩子設置為當前節點的左孩子（這是它唯一擁有的孩子）。

第22行到第24行: 我們處理了只有一個孩子（右孩子），並且是其父節點的左孩子的節點。我們將父節點的左孩子設置為當前節點的右孩子（這是它唯一的孩子）。

第25行到第27行: 我們處理了只有一個孩子（右孩子），並且它是其父節點的右孩子的節點。我們將父節點的右孩子設置為當前節點的右孩子（這是它唯一的孩子）。

第28行到第30行: 我們處理了同時擁有左孩子和右孩子的節點。我們獲取擁有最小值的節點（代碼隨後給出），並將其值設置給當前節點。通過刪除最小的節點完成節點移除。

第32行: 如果我們找到了要查找的節點，就需要返回 true 。從第11行到第31行，我們處理了這些情況。所以直接返回 true ，這就夠了。

clear_node 方法：設置節點的三個屬性為空——(value, left_child, and right_child)

def clear_node(self): self.value = None self.left_child = None self.right_child = None

find_minimum_value方法：一路向下找最左側的。如果我們無法找到任何節點，我們找其中最小的。

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 的節點。它是一個沒有孩子的節點。

print(bst.remove_node(8, None)) # Truebst.pre_order_traversal()# |15|# / # |10| |20|# / # |12| |17| |25|# # |19|

刪除值為 17 的節點。它是一個只有一個孩子的節點。

print(bst.remove_node(17, None)) # Truebst.pre_order_traversal()# |15|# / # |10| |20|# / # |12| |19| |25|

最後，刪除一個擁有兩個孩子的節點。它就是我們的樹的根節點。

print(bst.remove_node(15, None)) # Truebst.pre_order_traversal()# |19|# / # |10| |20|# # |12| |25|

測試完成。

End

閱讀排行榜/精華推薦

1

入門學習

2

進階修鍊

3

數據源爬取/收集

4

乾貨教程

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！

請您繼續閱讀更多來自 36大數據 的精彩文章: