二叉搜索树是一种特殊的二叉树，其左子树中的所有值均小于根节点，而右子树中的所有值均大于根节点的值。在这篇文章中，我们将深入探讨如何在 Python 中实现二叉搜索树。
目录
什么是二叉搜索树 (BST)？
二叉搜索树 是计算机科学中用于按排序方式组织和存储数据的一种数据结构。二叉搜索树中的每个节点最多有两个子节点，即 左 子节点和 右 子节点。
BST 的性质
- 节点的左侧仅包含比该节点值小的值。
- 节点的右侧仅包含比该节点值大的值。
- 左侧和右侧都遵循相同的规则，从而形成更小的二叉搜索树。
!image二叉搜索树
在这个二叉树中
- 根节点: 8
- 左子树 (3): 值均 < 8
- 右子树 (10): 值均 > 8
- 每个子树都维护相对于各自根节点的相同规则。
在 Python 中创建二叉搜索树 (BST)
下面是创建二叉搜索树 (BST) 的步骤。
- 创建一个 Tree 类
- 在参数化构造函数中，我们有一个默认参数 val = None
- 当在没有任何参数的情况下实例化 Tree 类时，它会创建一个带有左右指针的空节点
- 如果我们在实例化时传递了值，它会创建一个具有该值的节点，并且左右指针被创建为 None 类型。
Python
CODEBLOCK_c7121957
时间复杂度: O(1)
空间复杂度: O(1)
二叉搜索树 (BST) 的基本操作
以下是 Python 中二叉搜索树 (BST) 的一些基本操作。
Python 中的二叉搜索树 (BST) 插入操作
在二叉搜索树中插入节点涉及向树中添加一个新节点，同时要维护二叉搜索树 (BST) 的性质。因此，我们需要遍历所有节点，直到找到一个叶节点，并根据该叶节点的值将该节点作为左子节点或右子节点插入。因此，我们需要在叶节点检查的三个条件如下：
图示说明
> 让我们将 13 插入到下面的二叉搜索树中
>
>
> !Untitled-Diagramdrawio-(1).png)二叉搜索树
>
>
> – 当我们调用 insert 方法时，13 会与根节点 15 进行比较，由于 13 < 15，我们需要将 13 插入到左子树中。所以我们递归调用 leftsubtree.insert(13)
> – 现在 15 的左子节点是 10，所以将 13 与 10 进行比较，由于 13 > 10，我们需要将 13 插入到右子树中。所以我们递归调用 rightsubtree.insert(13)
> – 这里，10 的右子节点是 11，所以将 13 与 11 进行比较，由于 13 > 11，我们需要将 13 插入到 11 的右子节点。再次递归调用 rightsubtree.insert(13)
> – 在这个递归调用中，我们发现没有节点了，这意味着我们到达了叶节点，所以我们创建一个节点并将数据插入其中
>
> 插入 13 后，BST 看起来像这样：
>
>
> !Untitled-Diagramdrawio-(2).png)在二叉搜索树中插入了 13 节点
在 Python 中实现二叉搜索树 (BST) 的插入
Python
Python program to demonstrate
insert operation in binary search tree
class Node:
def init(self, key):
self.left = None
self.right = None
self.val = key
A utility function to insert
a new node with the given key
def insert(root, key):
if root is None:
return Node(key)
if root.val == key:
return root
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
A utility function to do inorder tree traversal
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=" ")
inorder(root.right)
r = Node(15)
r = insert(r, 10)
r = insert(r, 18)
r = insert(r, 4)
r = insert(r, 11)
r = insert(r, 16)
r = insert(r, 20)
r = i