用c语言编写函数int Delete(BiTreeNode**root,DataType item),在二叉树中删除数据元素item,删除成功返回0,失败返回-1。
时间: 2024-03-12 21:47:52 浏览: 78
c代码-二叉搜索树的删除操作
好的,我可以帮你编写这个函数。
首先,我们需要遍历二叉树来查找数据元素item所在的节点。如果找到了,就需要分情况进行处理:
1. 如果该节点没有左子树和右子树,直接将该节点删除即可。
2. 如果该节点只有左子树或右子树,将该节点的左子树或右子树与该节点的父节点相连,然后将该节点删除即可。
3. 如果该节点既有左子树又有右子树,需要找到该节点的中序遍历的前驱或后继节点,用前驱或后继节点的值替换该节点的值,然后删除前驱或后继节点。
下面是实现这个函数的代码:
```
int Delete(BiTreeNode** root, DataType item) {
BiTreeNode** p = root; // p指向当前节点的指针
BiTreeNode** q = NULL; // q指向p的父节点的指针
while (*p != NULL && (*p)->data != item) {
q = p;
if (item < (*p)->data) {
p = &((*p)->left);
} else {
p = &((*p)->right);
}
}
if (*p == NULL) {
return -1; // 没找到要删除的节点
}
if ((*p)->left == NULL && (*p)->right == NULL) { // 情况1
free(*p);
*p = NULL;
} else if ((*p)->left == NULL || (*p)->right == NULL) { // 情况2
BiTreeNode* child = ((*p)->left != NULL) ? (*p)->left : (*p)->right;
if (q == NULL) {
*root = child;
} else if (*p == q->left) {
q->left = child;
} else {
q->right = child;
}
free(*p);
} else { // 情况3
BiTreeNode** r = &((*p)->left);
while ((*r)->right != NULL) {
r = &((*r)->right);
}
(*p)->data = (*r)->data;
BiTreeNode* tmp = *r;
*r = (*r)->left;
free(tmp);
}
return 0;
}
```
注意,这里的参数root是指向二叉树根节点指针的指针,因为我们可能需要修改根节点指针,所以要传入指向根节点指针的指针。另外,这里的DataType是数据元素的类型,你需要根据实际情况替换成你要删除的数据元素的类型。
阅读全文