二叉搜索树的删除算法伪代码
时间: 2023-12-01 16:39:08 浏览: 38
二叉搜索树的删除算法伪代码如下:
1. 如果要删除的节点是叶子节点,直接删除即可。
2. 如果要删除的节点只有一个子节点,将该子节点替换要删除的节点即可。
3. 如果要删除的节点有两个子节点,找到该节点右子树中的最小节点,将该节点的值替换要删除的节点的值,然后删除该最小节点。
具体实现可以参考以下代码:
```
void deleteNode(Node* root, int key) {
if (root == NULL) return;
if (key < root->val) {
deleteNode(root->left, key);
} else if (key > root->val) {
deleteNode(root->right, key);
} else {
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
Node* temp = minValueNode(root->right);
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
}
Node* minValueNode(Node* node) {
Node* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
```