Python实现二叉搜索树的详细解析及示例

什么是二叉搜索树

二叉搜索树（Binary Search Tree），又称二叉查找树、有序二叉树，是指一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉搜索树；
• 没有键值相等的节点。

Python实现二叉搜索树

Python实现二叉搜索树，可以借助类的概念，定义一个节点类，用来描述每一个节点，并且定义一个根节点类，用来描述整棵树。

# 定义节点类
class Node(object):
    def __init__(self, data, left=None, right=None):
        self.data = data  # 节点数据
        self.left = left  # 左子树
        self.right = right  # 右子树

# 定义根节点类
class BST(object):
    def __init__(self, root=None):
        self.root = root  # 根节点

二叉搜索树的基本操作

二叉搜索树的基本操作有插入、查找、删除和遍历四种。

1. 插入

插入操作是构建二叉搜索树的基础操作，在插入新的节点时，要保证二叉搜索树的性质不变，即要保证插入新节点后，仍然是一棵二叉搜索树。

# 插入操作
def insert(self, data):
    if self.root is None:
        self.root = Node(data)
    else:
        self.__insert(self.root, data)

def __insert(self, node, data):
    if node.data > data:
        if node.left is None:
            node.left = Node(data)
        else:
            self.__insert(node.left, data)
    else:
        if node.right is None:
            node.right = Node(data)
        else:
            self.__insert(node.right, data)

2. 查找

查找操作是查询某一个节点是否存在于二叉搜索树中，要判断根节点是否为空，如果不为空，则进行查找操作，如果为空，则返回False。

# 查找操作
def search(self, data):
    if self.root is None:
        return False
    else:
        return self.__search(self.root, data)

def __search(self, node, data):
    if node.data == data:
        return True
    elif node.data > data:
        if node.left is None:
            return False
        else:
            return self.__search(node.left, data)
    else:
        if node.right is None:
            return False
        else:
            return self.__search(node.right, data)

3. 删除

删除操作是删除某一个节点，同时保证二叉搜索树的性质不变，删除操作可以分为三种情况：删除叶子节点、删除只有一个子节点的节点和删除有两个子节点的节点。

# 删除操作
def delete(self, data):
    if self.root is None:
        return False
    else:
        return self.__delete(self.root, data)

def __delete(self, node, data):
    if node is None:
        return False

    if node.data > data:
        node.left = self.__delete(node.left, data)
    elif node.data < data:
        node.right = self.__delete(node.right, data)
    else:
        # 删除叶子节点
        if node.left is None and node.right is None:
            node = None
        # 删除只有一个子节点的节点
        elif node.left is None:
            node = node.right
        elif node.right is None:
            node = node.left
        # 删除有两个子节点的节点
        else:
            # 找到右子树中的最小值
            min_node = self.__find_min(node.right)
            node.data = min_node.data
            node.right = self.__delete(node.right, min_node.data)
    return node

def __find_min(self, node):
    if node.left is None:
        return node
    else:
        return self.__find_min(node.left)

4. 遍历

遍历操作是按照某