我正在研究一个C程序,它将以下格式的学生记录扫描并存储到二进制搜索树中。对于BST,我已定义:
struct student
int id
char firstname[20]
char lastname[20]
float score
char zipcode[10]
struct node
struct student data
struct node* leftChild
struct node* rightChild
程序的功能之一应该是能够从树中删除记录。该程序要求用户提供将被删除的学生的姓氏。
以下是遍历BST以查找要删除的目标姓氏的方法:
void traverse(node* root,student data)
if(root != NULL)
traverse(root->leftChild,data)
if(strcmp(root->data.lastname,data.lastname) == 0)
root = delete(root,data)
traverse(root->rightChild,data)
传递给遍历函数的示例学生结构为:
struct student John
int id = 1000
char firstname = John
char lastname = Adams
float score = 90.00
char zipcode = 92121
我与findmin一起使用的delete函数,因为我知道我需要在根(目标节点)的正确子树中找到最小值,以便用它替换目标节点:
struct node* findmin(struct node* root)
while(root->leftChild != NULL)
root = root->leftChild
return root
struct node* delete(node* root,student data)
if(root == NULL) // check if empty tree
return root
// traverse towards left if ID is less
else if(data.iD < root->data.iD)
root->leftChild = delete(root->leftChild,data)
// towards right if greater than ID
else if(data.iD > root->data.iD)
root->rightChild = delete(root->rightChild,data)
/* else would mean target last name found */
else
/* if found node has no child */
if(root->leftChild == NULL && root->rightChild == NULL)
free(root)
root = NULL
// 1 child
else if(root->leftChild == NULL) // if left child is NULL
struct node* temp = root
root = root->rightChild
free(temp)
temp = NULL
else if(root->rightChild == NULL) // if right child is NULL
struct node* temp = root
root = root->leftChild
free(temp)
temp = NULL
// 2 children
else
struct node* temp = findmin(root->rightChild)
root->data = temp->data
root->rightChild = delete(root->rightChild,temp->data)
return root;
我希望在这里发生的事情是,student John
将与BST的全局根一起传递到遍历中,并且在打印BST时,student John
将被删除并且不再存在。但是,当我通过包含目标姓氏的学生时,该名称仍将存在于树中。此外,当我测试代码并传递要删除的记录时,有时,程序将不删除目标节点,而是删除具有最大学生ID的节点(树中最右边的节点)和/或进行分段问候。故障11.我看不到的代码有缺陷吗?让我知道您是否需要我提供任何进一步的信息来帮助您。