删除值为d的二叉树节点 BTNode* Delete_bitTree(BTNode* root,ElemType d)
时间: 2024-03-17 17:42:36 浏览: 57
好的,针对你的问题,我可以给出以下的代码实现:
```
BTNode* Delete_bitTree(BTNode* root, ElemType d) {
if (root == NULL) {
return NULL;
}
if (root->data == d) {
if (root->left == NULL && root->right == NULL) {
delete root;
return NULL;
}
else if (root->left == NULL) {
BTNode* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
BTNode* temp = root->left;
delete root;
return temp;
}
else {
BTNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = Delete_bitTree(root->right, temp->data);
return root;
}
}
else if (root->data > d) {
root->left = Delete_bitTree(root->left, d);
return root;
}
else {
root->right = Delete_bitTree(root->right, d);
return root;
}
}
```
该函数的作用是删除二叉树中值为 `d` 的节点。函数首先检查当前节点是否为 `NULL`,如果是,直接返回 `NULL`。如果当前节点的值等于 `d`,则根据其子节点的情况进行删除操作。如果当前节点没有子节点,直接删除并返回 `NULL`;如果只有一边有子节点,将该子节点替换当前节点并删除当前节点;如果两边都有子节点,找到当前节点右子树中最小的节点,将其值替换到当前节点中,再递归删除右子树中的最小节点。如果当前节点的值大于 `d`,则递归到左子树中查找;否则递归到右子树中查找。
阅读全文