在BST Python中删除节点_删除BST中的节点_BST中的删除节点功能 - 腾讯云开发者社区

在二叉搜索树（Binary Search Tree, BST）中删除节点是一个常见的操作。BST是一种特殊的二叉树，其中每个节点的值都大于其左子树中的任何节点值，并且小于其右子树中的任何节点值。

基础概念

删除BST中的节点主要有三种情况：

叶子节点：没有子节点的节点。
单子节点：只有一个子节点的节点。
双子节点：有两个子节点的节点。

类型

叶子节点删除：直接删除。
单子节点删除：用其子节点替换该节点。
双子节点删除：找到右子树中的最小节点或左子树中的最大节点替换该节点，然后删除那个最小/最大节点。

应用场景

BST常用于实现高效的查找、插入和删除操作，广泛应用于数据库索引、编译器符号表、文件系统等。

删除节点的Python实现

以下是一个简单的BST节点删除的Python示例：

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

def minValueNode(node):
    current = node
    while(current.left is not None):
        current = current.left
    return current

def deleteNode(root, key):
    if root is None:
        return root
    
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif(key > root.val):
        root.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp
        
        temp = minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    return root