Python数据结构之二叉排序树的定义、查找、插入、构造、删除

Python数据结构之二叉排序树

一、定义

二叉排序树（Binary Search Tree，BST），也称为二叉查找树或二叉搜索树，是一种基于二叉树的数据结构，其中每个节点都包含一个键值，且满足：

• 左子树中所有节点的键值均小于当前节点；
• 右子树中所有节点的键值均大于当前节点；

这是一种自平衡的数据结构，可以快速地进行查找、插入、删除等操作。

二、查找

查找操作是在二叉排序树中查找某个键值对应的节点。查找过程可以用递归或循环实现。

递归实现

class TreeNode:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def search(self, val, node):
        if node is None or node.val == val:
            return node
        elif node.val > val:
            return self.search(val, node.left)
        else:
            return self.search(val, node.right)

这里在BST类中定义了一个search方法，采用了递归的方式。如果当前节点为空或者当前节点的值等于要查找的值，则返回当前节点。否则，如果当前节点的值大于要查找的值，则向左子树递归查找；如果当前节点的值小于要查找的值，则向右子树递归查找。

循环实现

class BST:
    def __init__(self):
        self.root = None

    def search(self, val):
        node = self.root
        while node is not None and node.val != val:
            if node.val > val:
                node = node.left
            else:
                node = node.right
        return node

这里在BST类中定义了一个search方法，采用了循环的方式。首先将node指向BST的根节点，然后在循环中判断node是否为空或者node的值是否等于要查找的值。如果是，则返回node；否则，如果node的值大于要查找的值，则将node指向node的左子节点；如果node的值小于要查找的值，则将node指向node的右子节点。

三、插入

插入操作是在二叉排序树中插入一个键值对应的节点。插入过程可以用递归或循环实现。

递归实现

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val, node):
        if node is None:
            node = TreeNode(val)
        elif node.val > val:
            node.left = self.insert(val, node.left)
        elif node.val < val:
            node.right = self.insert(val, node.right)
        return node

这里在BST类中定义了一个insert方法，采用了递归的方式。首先判断当前节点是否为空，如果是，则创建一个新的节点并返回；否则，如果当前节点的值大于要插入的值，则递归插入到左子树；如果当前节点的值小于要插入的值，则递归插入到右子树。

示例：

tree = BST()
tree.root = tree.insert(2, tree.root)
tree.insert(1, tree.root)
tree.insert(3, tree.root)

这里创建了一棵二叉排序树，然后依次插入了3个节点，其值分别为2、1、3。

循环实现

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        node = self.root
        prev = None
        while node is not None:
            prev = node
            if node.val > val:
                node = node.left
            elif node.val < val:
                node = node.right
            else:
                return self.root
        new_node = TreeNode(val)
        if prev is None:
            self.root = new_node
        elif prev.val > val:
            prev.left = new_node
        else:
            prev.right = new_node
        return self.root

这里在BST类中定义了一个insert方法，采用了循环的方式。首先将node指向BST的根节点，prev指向node的父节点，然后在循环中判断node是否为空。如果是，则创建一个新的节点并根据val的大小插入到prev的左子节点或右子节点。

示例：

tree = BST()
tree.insert(2)
tree.insert(1)
tree.insert(3)

这里创建了一棵二叉排序树，然后依次插入了3个节点，其值分别为2、1、3。

四、构造

构造操作是从一个键值的列表中构造出一棵二叉排序树。构造过程可以用递归或循环实现。

递归实现

class BST:
    def __init__(self):
        self.root = None

    def construct(self, values):
        for val in values:
            self.root = self.insert(val, self.root)

这里在BST类中定义了一个construct方法，采用了递归的方式。首先遍历values中的每一个值，然后递归插入到BST中。

示例：

tree = BST()
tree.construct([2, 1, 3])

这里创建了一棵二叉排序树，其值分别为2、1、3。

循环实现

class BST:
    def __init__(self):
        self.root = None

    def construct(self, values):
        for val in values:
            new_node = TreeNode(val)
            node = self.root
            prev = None
            while node is not None:
                prev = node
                if node.val > val:
                    node = node.left
                elif node.val < val:
                    node = node.right
                else:
                    break
            if prev is None:
                self.root = new_node
            elif prev.val > val:
                prev.left = new_node
            else:
                prev.right = new_node

这里在BST类中定义了一个construct方法，采用了循环的方式。首先遍历values中的每一个值，然后依次插入到BST中。

示例：

tree = BST()
tree.construct([2, 1, 3])

这里创建了一棵二叉排序树，其值分别为2、1、3。

五、删除

删除操作是在二叉排序树中删除某个键值对应的节点。主要包含3种情况：

• 要删除的节点没有子节点；
• 要删除的节点只有一个子节点；
• 要删除的节点有两个子节点；

情况一和情况二

情况一和情况二的解决方法相同。如果要删除的节点没有子节点，则直接将其删除；如果要删除的节点只有一个子节点，则将其子节点移到其原来的位置。这里的代码实现比较简单，这里只展示递归实现。

class BST:
    def __init__(self):
        self.root = None

    def delete(self, val, node):
        if node is None:
            return node
        if node.val > val:
            node.left = self.delete(val, node.left)
        elif node.val < val:
            node.right = self.delete(val, node.right)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                min_node = self.find_min(node.right)
                node.val = min_node.val
                node.right = self.delete(min_node.val, node.right)
        return node

    def find_min(self, node):
        while node.left is not None:
            node = node.left
        return node

这里在BST类中定义了一个delete方法，采用了递归的方式。如果当前节点为空，则返回；如果当前节点的值大于要删除的值，则继续递归删除它的左子节点；如果当前节点的值小于要删除的值，则继续递归删除它的右子节点；如果当前节点的值等于要删除的值，则判断当前节点是否有左右子节点。如果没有子节点，则直接返回None；如果只有一个子节点，则返回这个子节点；如果有两个子节点，则找到右子树中最小的节点替换当前节点的值，并递归删除这个最小节点。

情况三

情况三需要特殊处理。首先找到要删除的节点的右子树中最小的节点代替要删除的节点，并从右子树中递归删除这个最小节点。这里的代码实现比较复杂，这里只展示递归实现。

class BST:
    def __init__(self):
        self.root = None

    def delete(self, val, node):
        if node is None:
            return node
        if node.val > val:
            node.left = self.delete(val, node.left)
        elif node.val < val:
            node.right = self.delete(val, node.right)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                min_node = self.find_min(node.right)
                node.val = min_node.val
                node.right = self.delete(min_node.val, node.right)
        return node

    def find_min(self, node):
        while node.left is not None:
            node = node.left
        return node

这里在BST类中定义了一个delete方法，采用了递归的方式。如果当前节点为空，则返回；如果当前节点的值大于要删除的值，则继续递归删除它的左子节点；如果当前节点的值小于要删除的值，则继续递归删除它的右子节点；如果当前节点的值等于要删除的值，则判断当前节点是否有左右子节点。如果没有子节点，则直接返回None；如果只有一个子节点，则返回这个子节点；如果有两个子节点，则找到右子树中最小的节点替换当前节点的值，并递归删除这个最小节点。