数据结构之二叉搜索树（BST）
1. 二叉搜索树定义
二叉搜索树(Binary Search Tree)，又名二叉排序树(Binary Sort Tree)。
二叉搜索树是具有有以下性质的二叉树：
（1）若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
（2）若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
（3）左、右子树也分别为二叉搜索树。
2. 二叉搜索树的相关操作
2.1 插入操作
从根节点开始，若插入的值比根节点的值小，则将其插入根节点的左子树；若比根节点的值大，则将其插入根节点的右子树。
示例代码：
def insert(self, item):
"""
二叉树搜索树的插入
:param item:
:return:
"""
node = TreeNode(item)
print('插入结点：', node.val)
# 如果为空树，则直接将item给根节点
if self.root is None:
self.root = node
return
# 通过队列的结构来实现二叉搜索树的插入
queue = [self.root]
while queue:
cur_node = queue.pop(0)
# 在左子树中进行插入
if cur_node.val > node.val:
if cur_node.left is None:
cur_node.left = node
return
else:
queue.append(cur_node.left)
# 在右子树中进行插入
else:
if cur_node.right is None:
cur_node.right = node
return
else:
queue.append(cur_node.right)2.2 查询操作
从根节点开始查找，待查找的值是否与根节点的值相同，若相同则返回True；否则，判断待寻找的值是否比根节点的值小，若是则进入根节点左子树进行查找，否则进入右子树进行查找。该操作使用递归实现。
示例代码：
def query(self, root, item):
"""
二叉搜索树的查找
:param item:
:return:
"""
if root is None:
return False
if root.val == item:
return True
elif item < root.val:
return self.query(root.left, item)
else:
return self.query(root.right, item)2.3 查找二叉搜索树中的最大（小值）
（1）查找最小值：从根节点开始，沿着左子树一直往下，直到找到最后一个左子树节点，按照定义可知，该节点一定是该二叉搜索树中的最小值节点。
示例代码：
def search_min(self, root):
"""
查找最小值
:return:
"""
if not root:
return
if root.left:
return self.search_min(root.left)
else:
return root.val（2）查找最大值：从根节点开始，沿着右子树一直往下，直到找到最后一个右子树节点，按照定义可知，该节点一定是该二叉搜索树中的最大值节点。
示例代码：
def search_max(self, root):
"""
查找最大值
:return:
"""
if not root:
return
if root.right:
return self.search_max(root.right)
else:
return root.val2.4 删除节点操作
对二叉搜索树节点的删除操作分为以下三种情况：
（1）待删除节点既无左子树也无右子树：直接删除该节点即可
（2）待删除节点只有左子树或者只有右子树：将其左子树或右子树根节点代替待删除节点
（3）待删除节点既有左子树也有右子树：找到该节点右子树中最小值节点，使用该节点代替待删除节点，然后在右子树中删除最小值节点。
示例代码：
def del_node(self, root, item):
"""
删除二叉搜索树中值为item的节点
:param root:
:param item:
:return:
"""
if not root:
return
if item < root.val:
root.left = self.del_node(root.left, item)
elif item > root.val:
root.right = self.del_node(root.right, item)
# 当item == root.val时，分为三种情况：只有左子树或者只有右子树、有左右子树、既无左子树又无右子树
else:
# 既有左子树又有右子树，则需要找到右子树中最小的节点
if root.left and root.right:
tmp = self.search_min(root.right)
root.val = tmp
# 再把右子树中最小值节点删除
self.del_node(root.right, tmp)
# 左右子树都为空
elif root.left is None and root.right is None:
root = None
# 只有左子树
elif root.right is None:
root = root.left
# 只有右子树
elif root.left is None:
root = root.right
return root
2.5 打印操作
实现二叉搜索树的中序遍历，并打印出来。该方法打印出来的数列将是按照递增顺序排列。
示例代码：
def print_node(self, root):
"""
打印二叉搜索树（中序打印，有序数列）
:param root:
:return:
"""
if root is None:
return
self.print_node(root.left)
print(root.val, end=" ")
self.print_node(root.right)全部代码：
class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinarySearchTree(object):
def __init__(self):
self.root = None # 根节点
def insert(self, item):
"""
二叉树搜索树的插入
:param item:
:return:
"""
node = TreeNode(item)
print('插入结点：', node.val)
# 如果为空树，则直接将item给根节点
if self.root is None:
self.root = node
return
# 通过队列的结构来实现二叉搜索树的插入
queue = [self.root]
while queue:
cur_node = queue.pop(0)
# 在左子树中进行插入
if cur_node.val > node.val:
if cur_node.left is None:
cur_node.left = node
return
else:
queue.append(cur_node.left)
# 在右子树中进行插入
else:
if cur_node.right is None:
cur_node.right = node
return
else:
queue.append(cur_node.right)
def query(self, root, item):
"""
二叉搜索树的查找
:param item:
:return:
"""
if root is None:
return False
if root.val == item:
return True
elif item < root.val:
return self.query(root.left, item)
else:
return self.query(root.right, item)
def search_min(self, root):
"""
查找最小值
:return:
"""
if not root:
return
if root.left:
return self.search_min(root.left)
else:
return root.val
def search_max(self, root):
"""
查找最大值
:return:
"""
if not root:
return
if root.right:
return self.search_max(root.right)
else:
return root.val
def del_node(self, root, item):
"""
删除二叉搜索树中值为item的节点
:param root:
:param item:
:return:
"""
if not root:
return
if item < root.val:
root.left = self.del_node(root.left, item)
elif item > root.val:
root.right = self.del_node(root.right, item)
# 当item == root.val时，分为三种情况：只有左子树或者只有右子树、有左右子树、既无左子树又无右子树
else:
# 既有左子树又有右子树，则需要找到右子树中最小的节点
if root.left and root.right:
tmp = self.search_min(root.right)
root.val = tmp
# 再把右子树中最小值节点删除
self.del_node(root.right, tmp)
# 左右子树都为空
elif root.left is None and root.right is None:
root = None
# 只有左子树
elif root.right is None:
root = root.left
# 只有右子树
elif root.left is None:
root = root.right
return root
def print_node(self, root):
"""
打印二叉搜索树（中序打印，有序数列）
:param root:
:return:
"""
if root is None:
return
self.print_node(root.left)
print(root.val, end=" ")
self.print_node(root.right)
# test
obj = BinarySearchTree()
obj.insert(9)
obj.insert(7)
obj.insert(8)
obj.insert(5)
obj.insert(11)
obj.insert(10)
obj.insert(15)
print("中序遍历二叉搜索树：", end=" ")
obj.print_node(obj.root)
print('\n查询节点5：', obj.query(obj.root, 5))
print('查询节点5.1：', obj.query(obj.root, 5.1))
print('二叉搜索树中最小值：', obj.search_min(obj.root))
print('二叉搜索树中最大值：', obj.search_max(obj.root))
# 删除节点10
root_node = obj.del_node(obj.root, 10)
print("中序遍历二叉搜索树：", end=" ")
obj.print_node(root_node)
print('\n查询节点10：', obj.query(root_node, 10))
print("中序遍历二叉搜索树：", end=" ")
obj.print_node(obj.root)
print('\n查询节点10：', obj.query(obj.root, 10))
运行结果：
