以下是基于题意的一个完整解决方案，使用了Python语言编写了一个二叉搜索树（BST）。该方案支持插入、删除和查询三种基本操作。 ### 程序代码 ```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) if key < root.val: root.left = insert(root.left, key) elif key > root.val: root.right = insert(root.right, key) return root def delete(root, key): if root is None: return root if key < root.val: root.left = delete(root.left, key) elif key > root.val: root.right = delete(root.right, key) else: # Node with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # Node with two children: Get the inorder successor (smallest in the right subtree) temp = minValueNode(root.right) # Copy the inorder successor's content to this node root.val = temp.val # Delete the inorder successor root.right = delete(root.right, temp.val) return root def minValueNode(node): current = node while current.left is not None: current = current.left return current def search(root, key): if root is None or root.val == key: return root is not None if key < root.val: return search(root.left, key) return search(root.right, key) if __name__ == "__main__": n = int(input()) bst_root = None for _ in range(n): operation, value_str = input().strip().split() value = int(value_str[1:]) # 提取出数字部分 if operation.startswith('I'): bst_root = insert(bst_root, value) elif operation.startswith('D'): bst_root = delete(bst_root, value) elif operation.startswith('S'): result = search(bst_root, value) print(1 if result else 0) ``` --- ### 示例解释 #### 输入： ``` 6 I 8 I 4 I 12 S 8 S 9 D 8 ``` #### 输出： ``` 1 0 ``` **解析：** - 插入 `8`, 树变为 `[8]` - 插入 `4`, 树变为 `[4 <- 8 -> null]` - 插入 `12`, 树变为 `[4 <- 8 -> 12]` - 查询 `8`: 存在，输出 `1` - 查询 `9`: 不存在，输出 `0` - 删除 `8`: 新根节点为 `12`，树变为 `[4 <- 12]` --- ###