【内部资料】二叉搜索树（排序二叉树)结点删除
排序二叉树（Sorted Binary Tree）和二叉搜索树（Binary Search Tree，BST）实际上是同一种概念，它们都是指一种特定类型的二叉树，具有以下特点：
有序性质： 在排序二叉树或二叉搜索树中，每个节点的左子树中的所有节点都小于或等于该节点，而右子树中的所有节点都大于该节点。
查找操作： 由于有序性质，可以利用二分查找的思想在排序二叉树或二叉搜索树中高效地查找特定元素。
插入和删除操作： 插入和删除元素时，可以通过保持树的有序性来维护它们。插入时将新元素放入合适的位置，删除时通过调整节点来维持有序性。
中序遍历： 中序遍历排序二叉树或二叉搜索树会按升序（从小到大）访问树中的所有元素。
因此，排序二叉树和二叉搜索树是相同的概念，通常可以互换使用。在不同的上下文中，人们可能会更倾向于使用其中一个术语，但它们指的是同一种类型的数据结构。
当要删除的节点在BST中有两个子节点时，可以选择以下两种方法之一来替代它：
方法一：使用中序遍历前驱节点或后继节点替代
找到要删除的节点的中序遍历前驱节点或后继节点。
中序遍历前驱节点是比要删除的节点值略小的节点中的最大值节点。
中序遍历后继节点是比要删除的节点值略大的节点中的最小值节点。
将前驱节点或后继节点的值复制到要删除的节点。
然后，递归地删除前驱节点或后继节点。这是因为前驱节点或后继节点只有一个子节点或没有子节点，因此可以使用上面讨论过的删除单子节点的方法进行删除。
方法二：递归删除左子树中的最大节点或右子树中的最小节点
如果选择递归删除左子树中的最大节点，那么找到要删除节点的左子树中的最大节点（即最右边的节点）。
将最大节点的值复制到要删除的节点。
然后，递归地删除最大节点。这通常是一个较简单的情况，因为最大节点要么没有子节点，要么只有一个左子节点。
或者
如果选择递归删除右子树中的最小节点，那么找到要删除节点的右子树中的最小节点（即最左边的节点）。
将最小节点的值复制到要删除的节点。
然后，递归地删除最小节点。这也是一个较简单的情况，因为最小节点要么没有子节点，要么只有一个右子节点。
这两种方法都是有效的，它们都能够保持BST的有序性质，并成功地删除具有两个子节点的节点。选择哪种方法通常取决于具体的实现偏好。
现在使用的是方法一，即使用中序遍历前驱节点（或后继节点）来替代具有两个子节点的节点。
50 / \\ 30 70 / \\ / \\ 20 40 60 80 / \\ / \\ / \\ / \\ 10 25 35 45 55 65 75 85
#include <iostream>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};
// 查找BST中的最小节点（最左子节点）
TreeNode* findMin(TreeNode* node) {
while (node->left) {
node = node->left;
}
return node;
}
// 删除BST中具有指定值的节点
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) {
return root; // 树为空，返回 NULL
}
// 在左子树中查找要删除的节点
if (key < root->data) {
root->left = deleteNode(root->left, key);
}
// 在右子树中查找要删除的节点
else if (key > root->data) {
root->right = deleteNode(root->right, key);
}
// 找到要删除的节点
else {
// 节点只有一个子节点或没有子节点
if (!root->left) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (!root->right) {
TreeNode* temp = root->left;
delete root;
return temp;
}
// 节点有两个子节点，找到中序遍历的后继节点
TreeNode* temp = findMin(root->right);
// 将后继节点的值复制到要删除的节点
root->data = temp->data;
// 递归删除后继节点
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// 中序遍历BST并输出结果
void inorderTraversal(TreeNode* root) {
if (root) {
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
}
int main() {
TreeNode* root = NULL;
// 构建一个BST
root = new TreeNode(50);
root->left = new TreeNode(30);
root->right = new TreeNode(70);
root->left->left = new TreeNode(20);
root->left->right = new TreeNode(40);
root->left->left->left= new TreeNode(10);
root->left->left->right= new TreeNode(25);
root->left->right->left = new TreeNode(35);
root->left->right->right = new TreeNode(45);
root->right->left = new TreeNode(60);
root->right->right = new TreeNode(80);
root->right->left->left = new TreeNode(55);
root->right->left->right = new TreeNode(65);
root->right->right->left = new TreeNode(75);
root->right->right->right = new TreeNode(85);
// 删除指定值的节点
int key = 30;
root = deleteNode(root, key);
// 中序遍历BST并输出结果
std::cout << "Inorder Traversal after deletion: ";
inorderTraversal(root);
std::cout << std::endl;
return 0;
}