root07 排序二叉树（BST）是一种数据结构，其中每个节点都包含一个键和两个子节点，左子节点包含较小的键，右子节点包含较大的键。删除排序二叉树中的节点是一项重要操作，因为它允许维护树的顺序属性。
二叉排序树中节点删除算法解析
二叉排序树中节点删除算法涉及以下步骤：
1. 找到待删除的节点：使用二叉树搜索算法找到包含待删除键的节点。
2. 检查节点类型：根据待删除节点的子节点数量，分为以下三种情况：
- 叶子节点（没有子节点）：直接删除该节点。
- 只有一个子节点：将父节点的指针指向该子节点，从而绕过待删除的节点。
- 有两个子节点：找到待删除节点的后继或前驱（具有最小或最大键的子节点），将其键复制到待删除的节点，然后删除后继或前驱。
删除叶子节点
如果待删除节点是叶子节点（没有子节点），则直接将其从树中删除即可。
```cpp
void deleteLeaf(BinarySearchTree tree, Node node) {
if (node == tree->root) {
tree->root = NULL;
} else {
Node parent = node->parent;
if (parent->left == node) {
parent->left = NULL;
} else {
parent->right = NULL;
}
}
delete node;
```
删除只有一个子节点的节点
如果待删除节点只有一个子节点，则将其父节点的指针指向该子节点，从而绕过待删除的节点。
```cpp
void deleteNodeWithOneChild(BinarySearchTree tree, Node node) {
Node parent = node->parent;
Node child = node->left ? node->left : node->right;
if (parent == NULL) {
tree->root = child;
} else {
if (parent->left == node) {
parent->left = child;
} else {
parent->right = child;
}
}
child->parent = parent;
delete node;
```
删除有两个子节点的节点（后继法）
如果待删除节点有两个子节点，则使用后继法找到待删除节点的后继（具有最小键的右子节点）。将后继的键复制到待删除的节点，然后删除后继。
```cpp
void deleteNodeWithTwoChildren(BinarySearchTree tree, Node node) {
Node successor = node->right;
while (successor->left != NULL) {
successor = successor->left;
}
node->key = successor->key;
if (successor->parent == node) {
node->right = successor->right;
if (successor->right != NULL) {
successor->right->parent = node;
}
} else {
Node successorParent = successor->parent;
successorParent->left = successor->right;
if (successor->right != NULL) {
successor->right->parent = successorParent;
}
}
delete successor;
```
删除有两个子节点的节点（前驱法）
与后继法类似，也可以使用前驱法找到待删除节点的前驱（具有最大键的左子节点），将其键复制到待删除的节点，然后删除前驱。
递归实现
以下 Java 代码提供了一个递归实现来删除排序二叉树中的节点：
```java
public class DeleteNodeBST {
public static void delete(Node root, int key) {
if (root == null) {
return;
}
if (key < root.key) {
delete(root.left, key);
} else if (key > root.key) {
delete(root.right, key);
} else {
// Found the node to be deleted
if (root.left == null) {
// No left child, replace with right child
transplant(root, root.right);
} else if (root.right == null) {
// No right child, replace with left child
transplant(root, root.left);
} else {
// Two children, replace with successor
Node successor = findMin(root.right);
root.key = successor.key;
delete(root.right, successor.key);
}
}
}
private static void transplant(Node root, Node newChild) {
if (root.parent == null) {
root = newChild;
} else if (root.parent.left == root) {
root.parent.left = newChild;
} else {
root.parent.right = newChild;
}
if (newChild != null) {
newChild.parent = root.parent;
}
}
private static Node findMin(Node root) {
while (root.left != null) {
root = root.left;
}
return root;
}
public static void main(String[] args) {
Node root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(2);
root.left.right = new Node(7);
root.right.left = new Node(12);
root.right.right = new Node(20);
// Delete node with no children
delete(root, 2);
// Delete node with one child
delete(root, 7);
// Delete node with two children
delete(root, 10);
// Display the modified BST
System.out.println(root);
}
```
示例
考虑以下排序二叉树：
```
10
/ \
5 15
/ \ / \
2 7 12 20
```
要删除键为 7 的节点，我们将使用后继法。该节点的后继是键为 12 的节点。我们复制其键并删除后继。
删除后，二叉树变为：
```
10
/ \
5 15
/ / \
2 12 20
```
结论
删除排序二叉树中的节点是一项重要的操作。通过理解算法并使用递归实现，我们可以有效地维护树的顺序属性，从而在各种应用程序中使用排序二叉树。
