二叉排序树的删除算法c++
时间: 2023-07-23 07:18:50 浏览: 41
二叉排序树的删除操作需要考虑三种情况:
1. 被删除节点没有子节点:直接删除即可。
2. 被删除节点有一个子节点:将其子节点代替该节点。
3. 被删除节点有两个子节点:找到该节点右子树的最小值节点,用该节点来代替被删除节点。
以下是二叉排序树的删除算法的C++实现:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
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) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
delete root;
return temp;
}
TreeNode* minNode = root->right;
while (minNode->left != NULL) {
minNode = minNode->left;
}
root->val = minNode->val;
root->right = deleteNode(root->right, minNode->val);
}
return root;
}
```
其中,deleteNode函数的输入参数为二叉排序树的根节点和待删除的节点值。该函数返回删除节点后的二叉排序树的根节点。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)