二叉排序树的删除操作
时间: 2023-10-21 18:26:14 浏览: 564
二叉排序树的删除操作可以分为三种情况:
1. 要删除的节点是叶子节点:直接将该节点删除即可。
2. 要删除的节点只有一个子节点:将该节点的子节点与其父节点连接,并删除该节点。
3. 要删除的节点有两个子节点:找到该节点的中序遍历的前驱(或后继)节点,将前驱(或后继)节点的值替换到要删除的节点中,然后再递归地删除前驱(或后继)节点。
具体的实现步骤如下:
1. 首先查找要删除的节点,并记录其父节点。
2. 根据要删除的节点的情况进行处理:
- 如果要删除的节点是叶子节点,直接删除即可。
- 如果要删除的节点只有一个子节点,将子节点与其父节点连接,并删除该节点。
- 如果要删除的节点有两个子节点,找到其中序遍历的前驱(或后继)节点,将前驱(或后继)节点的值替换到要删除的节点中,然后再递归地删除前驱(或后继)节点。
下面是一个示例代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def deleteNode(root, key):
if not root:
return root
# 查找要删除的节点及其父节点
parent = None
node = root
while node and node.val != key:
parent = node
if key < node.val:
node = node.left
else:
node = node.right
if not node:
# 没有找到要删除的节点
return root
if not node.left and not node.right:
# 要删除的节点是叶子节点
if not parent:
# 删除的是根节点
return None
if parent.left == node:
parent.left = None
else:
parent.right = None
elif not node.left or not node.right:
# 要删除的节点只有一个子节点
child = node.left if node.left else node.right
if not parent:
# 删除的是根节点
return child
if parent.left == node:
parent.left = child
else:
parent.right = child
else:
# 要删除的节点有两个子节点,找到其中序遍历的前驱或后继节点
successor_parent = node
successor = node.right
while successor.left:
successor_parent = successor
successor = successor.left
node.val = successor.val
if successor_parent.left == successor:
successor_parent.left = None
else:
successor_parent.right = None
return root
```
请注意,这只是一个简单的示例代码,实际使用时可能需要考虑更多的情况和异常处理。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)