【Python 数据结构 11.二叉搜索树】
人永远在原谅自己，以为这样就可以有重来的余地
—— 25.3.9
一、二叉搜索树的基本概念
1.二叉搜索树的概念
Ⅰ、定义
二叉搜索树(又称为二叉排序树，二叉查找树)，它满足如下四点性质:
1) 空树是二叉搜索树;
2) 若它的左子树不为空，则左子树上所有结点的值均小于它根结点的值;
3) 若它的右子树不为空，则右子树上所有结点的值均大于它根结点的值;
4) 它的左右子树均为二叉搜索树;
如图所示，对于任何一颗子树而言，它的根结点的值一定大于左子树所有结点的值，且一定小于右子树所有结点的值
Ⅱ、用途
从二叉搜索树的定义可知，它的前提是二叉树，并且采用了递归的方式进行定义，它的结点间满足一个偏序关系：左子树根结点的值一定比父结点小，右子树根结点的值一定比父结点大。
正如它的名字所说，构造这样一棵树的目的是为了提高搜索的速度，如果对二叉搜索树进行中序遍历，我们可以发现，得到的序列是一个递增序列。
2.二叉搜索树的链式存储
我们一般用孩子表示法来定义一棵二叉搜索树的结点。
(1) 二叉搜索树需要有一个结点值，也就是数据域，注意：这里的类型其实可以是任意类型，只要这种类型支持 关系运算符 的比较即可
(2) 二叉搜索树结点的左儿子结点的指针，没有左儿子结点时，置为空;
(3) 二叉搜索树结点的右儿子结点的指针，没有右儿子结点时，置为空;
3.二叉搜索树的结点查找
Ⅰ、节点查找的概念
二叉搜索树的查找指的是：在树上查找某个数是否存在，存在返回 true ，不存在返回 false
如图所示，代表的是从一个二叉搜索树中查找出一个值为 3 的结点。一开始，3 比根节点 5 小，于是递归访问左子树；并且比子树的根节点 4 小，于是继续递归访问左子树；这时候比根节点 2 大，于是递归访问右子树，正好找到值为 3 的查找，回溯结束查找
Ⅱ、结点查找的步骤
对于要查找的数 val，从根结点出发，总共四种情况依次判断：
第1步：若为空树，直接返回 false;
第2步：val 的值 小于 树根结点的值，说明 val 对应的结点不在根结点，也不在右子树上，则递归返回左子树的 查找 结果;
第3步：val 的值 大于 树根结点的值，说明 val 对应的结点不在根结点，也不在左子树上，则递归返回右子树的 查找 结果;
第4步：直接返回 true(无须等于判定，因为不小于、不大于必然是等于);
4.二叉搜索树的结点插入
Ⅰ、结点插入的概念
二叉搜索树的插入指的是将给定的值生成结点后，插入到树上的某个位置，并且保持这棵树还是二叉搜索树。
如图所示，代表将一个值为 3 的结点插入到一个二叉搜索树中。一开始，3 比 根节点 5 小，于是递归插入左子树；还是比子树的根节点 4 小，于是继续递归插入左子树；这时候比根节点 2 大，于是递归插入右子树，右子树为空，则直接生成一个值为 3 的结点，回溯结束插入
Ⅱ、结点插入的步骤
对于要插入的数 val ，从根结点出发，总共四种情况依次判断：
第1步：若为空树，则创建一个值为 val 的结点并且返回；
第2步：val 的值 小于 树根结点的值，那么插入位置一定在 左子树，递归执行插入左子树的过程，并且返回插入结果作为新的左子树;
第3步：val 的值 大于 树根结点的值，那么插入位置一定在 右子树，递归执行插入右子树的过程，并且返回插入结果作为新的右子树;
第4步：直接返回当前树的根结点;
5.二叉搜索树的结点删除
Ⅰ、结点删除的概念
二叉搜索树的删除指的是在树上删除给定值的结点
如图所示，从这棵树删除根节点 5 的过程。首先，由于它有左右儿子结点，所以这个过程，根结点并不是真正地删除。而是从右子树中找到最小的结点 6，替换根结点，并且从根节点为 7 的子树中删除 6 的过程，由于 6 没有子节点，所以这个过程结束了
Ⅱ、结点删除的步骤
删除值为 val 的结点的过程，从根结点出发，总共七种情况依次判断：
第1步：如果当前结点为空，则直接返回空树
第2步：如果要删除的值小于当前结点的值，则递归调用左子树进行结点的删除
第3步：如果要删除的值大于当前结点的值，则递归调用右子树进行结点的删除
第4步：如果当前结点是一个叶子结点，即它没有左子树和右子树，那么删除该结点，并且返
回空树
第5步：如果当前结点只有右子树而没有左子树，那么删除当前结点并将右子树返回
第6步：如果当前结点只有左子树而没有右子树，那么删除当前结点并将左子树返回
第7步：如果当前结点既有左子树又有右子树，那么找到当前结点右子树中的最小值结点(即最左边的结点)，将当前结点的值替换为这个最小值结点的值，然后递归地删除右子树中该最小值结点。
6.二叉搜索树的总结
纵观二叉搜索树的查找、插入 和 删除。完全取决于二叉搜索树的形状，如果是完全二叉树或者接近完全二叉树，则这三个过程都是 (logn) 的，如果是斜树，则三个过程近似操作线性表为 O(n)
二、Python中的二叉搜索树
1.定义二叉搜索树结点类
val：存储树结点的索引
left：存储树结点的左孩子
right：存储树结点的右孩子
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right2.定义二叉搜索树类
Ⅰ、树初始化
只需要初始化一个根结点为空值 None
class BinarySearchTree:
def __init__(self):
self.root = None
Ⅱ、 添加结点
传入根结点和要添加结点的val，比较二者大小关系，递归插入
# 增
def insertNode(self, node, val):
# 递归终止条件
if node is None:
return TreeNode(val)
if val < node.val:
node.left = self.insertNode(node.left, val)
elif val > node.val:
node.right = self.insertNode(node.right, val)
return node
def insert(self, val):
self.root = self.insertNode(self.root, val)Ⅲ、删除结点
递归删除，递归过程如下图：
# 删
def removeNode(self, node, val):
if node is None:
return None
if val < node.val:
node.left = self.removeNode(node.left, val)
elif val > node.val:
node.right = self.removeNode(node.right, val)
else:
if node.left is None and node.right is None:
return None
elif node.left is None:
return node.right
elif node.right is None:
return node.left
else:
replacement = node.right
while replacement.left:
replacement = replacement.left
node.val = replacement.val
node.right = self.removeNode(node.right, replacement.val)
return node
def remove(self, val):
self.root = self.removeNode(self.root, val)Ⅳ、查找结点
判断传入结点的val值与要查找的val值大小关系，已知二叉搜索树结点间的相互关系，遍历推断所查找结点的位置
# 查
def searchNode(self, node, val):
if node is None:
return False
if val < node.val:
return self.searchNode(node.left, val)
elif val > node.val:
return self.searchNode(node.right, val)
return True
def search(self, val):
return self.searchNode(self.root, val)Ⅴ、中序遍历
已知中序遍历的顺序是：左 - 根 - 右，而结合二叉搜索树结点间的相互关系，进行中序遍历的结果恰好应该是一个递增序列
# 中序遍历
def inOrder(self, node):
if node is None:
return
self.inOrder(node.left)
print(node.val, end=",")
self.inOrder(node.right)
def inOrderTraversal(self):
self.inOrder(self.root)
print("")Ⅵ、代码测试
添加结点后的二叉搜索树： 
删除结点 5 后的二叉搜索树：
def Test():
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)
bst.insert(6)
bst.insert(8)
bst.inOrderTraversal()
bst.remove(5)
bst.inOrderTraversal()
print(bst.search(4))
print(bst.search(9))
Test()
三、实战
1.108. 将有序数组转换为二叉搜索树
给你一个整数数组
nums，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums按 严格递增 顺序排列
方法一、递归
思路与算法
递归终止条件：如果左边界 l 大于右边界 r，说明当前子数组为空，返回 None。
选择根节点：计算当前子数组的中间位置 mid = (l + r) // 2。以 nums[mid] 作为根节点的值，创建一个 TreeNode。
递归构建左子树和右子树：左子树的范围是 [l, mid - 1]，递归调用 inOrder 构建左子树。右子树的范围是 [mid + 1, r]，递归调用 inOrder 构建右子树。
返回根节点：返回当前构建的根节点。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inOrder(self, nums, l, r):
if l > r:
return None
mid = (l + r) // 2
root = TreeNode(nums[mid])
root.left = self.inOrder(nums, l, mid - 1)
root.right = self.inOrder(nums, mid + 1, r)
return root
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
root = nums[0]
return self.inOrder(nums, 0, len(nums) - 1)
2.98. 验证二叉搜索树
给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。提示：
- 树中节点数目范围在
[1, 104]内-231 <= Node.val <= 231 - 1
方法一 根据二叉搜索树中序遍历的性质判断
思路与算法
中序遍历：使用递归方法 inorder 对二叉树进行中序遍历，将节点值按顺序存储在 self.list 中。
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
检查递增性：遍历 self.list，检查每个元素是否大于前一个元素。如果发现某个元素小于或等于前一个元素，则返回 False，说明不是有效的二叉搜索树。
返回结果：如果列表严格递增，返回 True，说明是有效的二叉搜索树。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorder(self, root):
if root:
self.inorder(root.left)
self.list.append(root.val)
self.inorder(root.right)
def isValidBST(self, root: Optional[TreeNode]) -> bool:
self.list = []
self.inorder(root)
for i in range(1, len(self.list)):
if self.list[i] <= self.list[i - 1]:
return False
return True
3.面试题 04.05. 合法二叉搜索树
实现一个函数，检查一棵二叉树是否为二叉搜索树。
示例 1：
输入： 2 / \ 1 3 输出：true示例 2：
输入： 5 / \ 1 4 / \ 3 6 输出：false 解释：输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。
方法一 递归
思路与算法
递归终止条件：如果当前节点为空，返回 True，因为空树是有效的二叉搜索树。
检查当前节点：如果当前节点的值不在 (min, max) 范围内，返回 False。
递归检查左子树和右子树：左子树的范围是 (min, root.val)，因为左子树的所有节点值必须小于当前节点的值。右子树的范围是 (root.val, max)，因为右子树的所有节点值必须大于当前节点的值。
返回结果：如果左子树和右子树都满足条件，返回 True，否则返回 False。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def checkTree(self, root, min, max):
if not root:
return True
if root.val >= max or root.val <= min:
return False
return self.checkTree(root.left, min, root.val) and self.checkTree(root.right, root.val, max)
def isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.checkTree(root, -inf, inf)