设计一个C++算法,它从二叉检索树中删除一个结点,并仍然保持二叉检索树的特性不变。
时间: 2024-03-07 07:50:11 浏览: 85
以下是一个C++算法,用于从二叉搜索树中删除给定的节点,并仍然保持二叉搜索树的性质:
```c++
//定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
//从二叉搜索树中删除节点
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return root; // 如果根节点为空,返回空指针
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) { // 如果左子树为空,将右子树升为根节点
TreeNode* temp = root->right;
delete root;
return temp;
} else if (!root->right) { // 如果右子树为空,将左子树升为根节点
TreeNode* temp = root->left;
delete root;
return temp;
}
// 如果左右子树都不为空,找到右子树中最小值的节点
TreeNode* temp = root->right;
while (temp->left) {
temp = temp->left;
}
// 将右子树中最小值的节点的值复制到当前节点
root->val = temp->val;
// 在右子树中删除最小值的节点
root->right = deleteNode(root->right, temp->val);
}
return root;
}
```
这个算法首先在二叉搜索树中查找要删除的节点。如果找到了节点,就根据它的左右子树来选择如何删除它。如果节点只有一个子树,就将该子树作为新的子树。如果节点有两个子树,就在右子树中找到最小值的节点,并将其复制到当前节点,然后删除右子树中最小值的节点。
阅读全文