7-1 二叉搜索树的删除操作
时间: 2023-11-27 15:05:43 浏览: 49
二叉搜索树的删除操作是将二叉搜索树中某个节点删除,并保证删除后的二叉搜索树仍然满足二叉搜索树的性质。
删除操作的实现分为以下几步:
1. 找到要删除的节点。如果要删除的节点是根节点,则直接删除;否则,先找到要删除的节点的父节点。
2. 判断要删除的节点有几个子节点,分为以下三种情况:
a. 要删除的节点没有子节点,即为叶子节点。直接删除,并将其父节点中指向该节点的指针置为 null。
b. 要删除的节点有一个子节点。将该节点的子节点替换为该节点,并将其父节点中指向该节点的指针指向该节点的子节点。
c. 要删除的节点有两个子节点。找到该节点的后继节点,将该节点的值替换为后继节点的值,并将后继节点删除。
3. 如果要删除的节点是根节点,则删除后需要更新根节点。否则,删除后需要更新该节点的父节点指向该节点的指针。
以下是 Java 代码实现:
```java
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null && root.right == null) {
root = null;
} else if (root.left == null) {
root = root.right;
} else if (root.right == null) {
root = root.left;
} else {
TreeNode successor = getSuccessor(root);
root.val = successor.val;
root.right = deleteNode(root.right, successor.val);
}
}
return root;
}
private TreeNode getSuccessor(TreeNode node) {
node = node.right;
while (node.left != null) {
node = node.left;
}
return node;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)