[已解决]二叉搜索树的删除操作

yangzhixiaohuli

给出一棵二叉搜索树（没有相同元素）, 请输出其删除部分元素之后的层序遍历序列。

删除结点的策略如下：

如果一个结点是叶子结点，则直接删除；
如果一个结点的左子树不为空, 则将该结点的值设置为其左子树上各结点中的最大值，并继续删除其左子树上拥有最大值的结点；
如果一个结点的左子树为空但右子树不为空，则将该结点的值设置为其右子树上各结点中的最小值，并继续删除其右子树上拥有最小值的结点。
输入格式:
每个输入文件包含一个测试用例。每个测试用例的第一行包含一个整数 N (0<N<=100)，表示二叉搜索树中结点的个数。
第二行给出该二叉搜索树的先序遍历序列，由 N 个整数构成，以一个空格分隔。第三行给出一个整数K (0<K<N)，表示待删除的结点个数。最后一行给出 K 个整数，表示待删除的各个结点上的值。必须按输入次序删除结点。题目保证结点一定能被删除。

输出格式:
在一行中输出删除结点后的层序遍历序列。序列中的数字以一个空格分隔，行末不得有多余空格。

输入样例:
7
4 2 1 3 6 5 7
2
3 6
输出样例:
4 2 5 1 7

这题用C语言或者C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

6 天前

由于提供的信息不完整，请确保输入完整再试。根据已知内容，以下是处理二叉搜索树删除操作的一些步骤和代码示例：

1. **删除结点（叶子结点）：** 如果结点是叶子结点，直接将其删除。

2. **删除结点（左子树不为空）：** 找到左子树中的最大值替换该结点，并在左子树中删除此最大值结点。

3. **删除结点（右子树不为空）：** 如果左子树为空且右子树不为空，则找到右子树中的最小值替换该结点，并在右子树中删除此最小值结点。

下面是一个简单的Python代码示例，演示了二叉搜索树节点的删除：

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

def insert(root, key):
    if root is None:
        return TreeNode(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

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:
            return root.right
        elif root.right is None:
            return root.left

        temp = findMin(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)

    return root

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

def findMax(node):
    current = node
    while(current.right is not None):
        current = current.right
    return current

def levelOrderTraversal(root):
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        current = queue.pop(0)
        if current:
            result.append(current.val)
            queue.append(current.left)
            queue.append(current.right)
    return result

# 示例使用
root = None
keys = [50, 30, 20, 40, 70, 60, 80]
for key in keys:
    root = insert(root, key)

root = deleteNode(root, 20)
print(levelOrderTraversal(root)) # 输出层序遍历序列

请您确保提供完整的输入数据，以便生成精确的结果。使用上述代码能够帮助理解基本操作。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

由于提供的信息不完整，请确保输入完整再试。根据已知内容，以下是处理二叉搜索树删除操作的一些步骤和代码示例：

1. **删除结点（叶子结点）：** 如果结点是叶子结点，直接将其删除。

2. **删除结点（左子树不为空）：** 找到左子树中的最大值替换该结点，并在左子树中删除此最大值结点。

3. **删除结点（右子树不为空）：** 如果左子树为空且右子树不为空，则找到右子树中的最小值替换该结点，并在右子树中删除此最小值结点。

下面是一个简单的Python代码示例，演示了二叉搜索树节点的删除：

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

def insert(root, key):
    if root is None:
        return TreeNode(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

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:
            return root.right
        elif root.right is None:
            return root.left

        temp = findMin(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)

    return root

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

def findMax(node):
    current = node
    while(current.right is not None):
        current = current.right
    return current

def levelOrderTraversal(root):
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        current = queue.pop(0)
        if current:
            result.append(current.val)
            queue.append(current.left)
            queue.append(current.right)
    return result

# 示例使用
root = None
keys = [50, 30, 20, 40, 70, 60, 80]
for key in keys:
    root = insert(root, key)

root = deleteNode(root, 20)
print(levelOrderTraversal(root)) # 输出层序遍历序列

请您确保提供完整的输入数据，以便生成精确的结果。使用上述代码能够帮助理解基本操作。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。