C二叉搜索树删除节点
时间: 2024-06-19 12:04:30 浏览: 10
C语言中的二叉搜索树是一种非常常用的数据结构,其插入和查找的时间复杂度都是O(logn)。当然,在使用二叉搜索树时,我们也需要注意它的删除操作,否则会影响它的性能。
二叉搜索树的删除操作可以分为以下三种情况:
1. 被删除节点为叶子节点:直接将其删除即可。
2. 被删除节点只有一个子节点:将其子节点替代被删除节点即可。
3. 被删除节点有两个子节点:需要找到其右子树中的最小值或左子树中的最大值来替代被删除节点。
具体实现时,我们可以使用递归或者迭代的方式进行实现。下面是一个使用递归的实现方式:
```
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
if (root == NULL) 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 == NULL) {
struct TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct TreeNode* temp = root->left;
free(root);
return temp;
} else {
struct TreeNode* temp = findMin(root->right);
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
}
return root;
}
struct TreeNode* findMin(struct TreeNode* node) {
while (node->left != NULL) node = node->left;
return node;
}
```
以上代码中,deleteNode函数使用递归实现了删除操作,findMin函数则是用来找到右子树中的最小值。在deleteNode函数中,我们首先判断了要删除的节点是否为空,然后再根据二叉搜索树的性质来判断要删除的节点在左子树还是右子树中。如果要删除的节点为叶子节点或只有一个子节点,则直接将其替换即可;如果要删除的节点有两个子节点,则需要找到右子树中的最小值(或左子树中的最大值),将其赋值给被删除节点,并在右子树中删除该最小值。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.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)