广度优先搜索（BFS）
BFS是一层层逐渐深入的遍历算法。
下面这个例子是用来帮我们更好的解释该算法。
我们来一层一层的遍历这棵树。本例中，就是1-2-5-3-4-6-7.
0层/深度0：只有值为1的节点1层/深度1：有值为2和5的节点2层/深度2：有值为3、4、6、7的节点好，下面我们来编写实现代码。
首先用put方法将根节点添加到队列中。当队列不为空时迭代。获取队列中的第一个节点，然后输出其值。将其左孩子和右孩子添加到队列（如果它有孩子的话）。在队列的帮助下我们将每一个节点的值一层层的输出。以下是上述插图的详解：
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。考虑在子树的左侧插入相等的值。现在我们来编码。
现在我们想知道是否有一个节点的值为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 = Nonefind_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|
测试完成。
免责声明：本网站内容主要来自原创、合作伙伴供稿和第三方自媒体作者投稿，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证有关资料的准确性及可靠性，读者在使用前请进一步核实，并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏，概不负任何法律责任。任何单位或个人认为本网站中的网页或链接内容可能涉嫌侵犯其知识产权或存在不实内容时，应及时向本网站提出书面权利通知或不实情况说明，并提供身份证明、权属证明及详细侵权或不实情况证明。本网站在收到上述法律文件后，将会依法尽快联系相关文章源头核实，沟通删除相关内容或断开相关链接。
