用c语言编写函数int Delete(BiTreeNode**root,DataType item),在二叉树中删除数据元素item,删除成功返回0,失败返回-1。typedef struct node{ DataType data; struct node *leftChild; struct node *rightChild; } BiTreeNode;
时间: 2024-03-12 22:48:17 浏览: 112
数据结构作业:唯一确定一棵二叉树.doc
好的,这是您的问题:用C语言编写函数int Delete(BiTreeNode** root, DataType item),在二叉树中删除数据元素item,删除成功返回0,失败返回-1。typedef struct node{ DataType data; struct node *leftChild; struct node *rightChild; } BiTreeNode;。
以下是函数的实现:
```c
int Delete(BiTreeNode** root, DataType item) {
// 判断根节点是否为空
if (*root == NULL) {
return -1;
}
// 找到要删除的节点
BiTreeNode* current = *root;
BiTreeNode* parent = NULL;
while (current != NULL && current->data != item) {
parent = current;
if (item < current->data) {
current = current->leftChild;
} else {
current = current->rightChild;
}
}
// 如果没有找到要删除的节点,返回-1
if (current == NULL) {
return -1;
}
// 如果要删除的节点是叶子节点,直接删除
if (current->leftChild == NULL && current->rightChild == NULL) {
if (parent == NULL) {
*root = NULL;
} else if (current == parent->leftChild) {
parent->leftChild = NULL;
} else {
parent->rightChild = NULL;
}
free(current);
}
// 如果要删除的节点只有一个子节点,将子节点替换要删除的节点
else if (current->leftChild == NULL || current->rightChild == NULL) {
BiTreeNode* child = current->leftChild == NULL ? current->rightChild : current->leftChild;
if (parent == NULL) {
*root = child;
} else if (current == parent->leftChild) {
parent->leftChild = child;
} else {
parent->rightChild = child;
}
free(current);
}
// 如果要删除的节点有两个子节点,找到右子树中最小的节点,替换要删除的节点
else {
BiTreeNode* minNode = current->rightChild;
BiTreeNode* minParent = current;
while (minNode->leftChild != NULL) {
minParent = minNode;
minNode = minNode->leftChild;
}
current->data = minNode->data;
if (minParent == current) {
current->rightChild = minNode->rightChild;
} else {
minParent->leftChild = minNode->rightChild;
}
free(minNode);
}
return 0;
}
```
函数的实现过程如下:
1. 首先判断根节点是否为空,如果为空,返回-1。
2. 遍历二叉树,找到要删除的节点。如果没有找到要删除的节点,返回-1。
3. 如果要删除的节点是叶子节点,直接删除。
4. 如果要删除的节点只有一个子节点,将子节点替换要删除的节点。
5. 如果要删除的节点有两个子节点,找到右子树中最小的节点,替换要删除的节点。
最后,返回0表示删除成功。
阅读全文