如何实现二叉排序树的删除操作?
时间: 2023-12-03 18:36:39 浏览: 44
二叉排序树的删除操作分为三种情况:
1. 被删除节点没有子节点,直接删除即可。
2. 被删除节点只有一个子节点,将其子节点替换为被删除节点即可。
3. 被删除节点有两个子节点,需要找到其右子树中最小的节点(或左子树中最大的节点),将其值替换到被删除节点中,然后再删除该最小(或最大)节点。
具体实现可以参考以下代码:
```python
def delete(root, key):
if not root:
return root
if key < root.val:
root.left = delete(root.left, key)
elif key > root.val:
root.right = delete(root.right, key)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
else:
min_node = find_min(root.right)
root.val = min_node.val
root.right = delete(root.right, min_node.val)
return root
def find_min(node):
while node.left:
node = node.left
return node
```