二叉查找树完成含两个子节点的删除
时间: 2024-02-26 07:58:37 浏览: 23
当要删除的节点有两个子节点时,可以按照以下步骤进行删除:
1. 找到该节点的右子树中的最小节点(或者左子树中的最大节点),将其值赋给要删除的节点;
2. 删除右子树中的最小节点(或者左子树中的最大节点)。
具体实现可以参考以下代码(以C++为例):
```cpp
// 定义二叉查找树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
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 && !root->right) { // 情况1:要删除的节点是叶子节点
delete root;
return nullptr;
} else if (!root->left || !root->right) { // 情况2:要删除的节点只有一个子节点
TreeNode* child = root->left ? root->left : root->right;
delete root;
return child;
} else { // 情况3:要删除的节点有两个子节点
TreeNode* minNode = root->right;
while (minNode->left) {
minNode = minNode->left;
}
root->val = minNode->val;
root->right = deleteNode(root->right, minNode->val);
}
}
return root;
}
};
```
需要注意的是,虽然这种方法可以保证删除后仍满足二叉查找树的性质,但是并不一定能保证平衡性,因为删除的节点可能是深度较大的节点。至于哪种方法具有最好的平衡性以及在处理整个操作序列过程中花费最少的CPU时间,需要根据具体情况进行评估。