我试图在二叉搜索树中删除一个有2个孩子的节点 . 但是我在这里面临的问题很少 . 在删除带子节点的节点(带有data = 30的节点)时(left-> data = 20,right-> data = 40),我用它的inorder后继(它是data = 40的节点)替换节点,然后删除继承人 . 删除后,节点的数据被成功替换(新值为40),但是inorder后继未被正确删除/释放 .
预期输出[inorder遍历]:20-> 40-> 50-> 60-> 70-> 80->
输出[inorder遍历]:20-> 40-> 0-> 50-> 60-> 70-> 80->
40后,为什么值0出现?
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *left;
struct Node *right;
};
struct Node* temp = NULL,*temp1 = NULL;
struct Node *newNode(int data)
{
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
struct Node* insert(struct Node* root,int data)
{
if(root == NULL)
{
return newNode(data);
}
if(data < root->data)
root->left = insert(root->left,data);
else
root->right = insert(root->right,data);
}
void inorder(struct Node* root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d->",root->data);
inorder(root->right);
}
else
{
return;
}
}
/*to find the inorder successor*/
struct Node *minVal(struct Node *root)
{
while(root->left !=NULL)
{
temp = root;
root = root->left;
}
return root;
}
void deleteNode(struct Node *root,int data)
{
if(data < root->data)
{
temp = root;
deleteNode(root->left,data);
}
else if(data > root->data)
{
temp = root;
deleteNode(root->right,data);
}
else if(data == root->data)
{ /*deleting leaf nodes*/
if(root->left == NULL && root->right == NULL)
{
if(temp->left == root)
temp->left = NULL;
else
if(temp->right == root)
temp->right = NULL;
free(root);
root = NULL;
return;
}
/*deleting nodes having single child*/
else if(root->left !=NULL && root->right == NULL)
{
temp1 = root->left;
temp->left = temp1;
free(root);
root = NULL;
}
else if(root->left ==NULL && root->right != NULL)
{
temp1 = root->right;
temp->right = temp1;
free(root);
root = NULL;
}
/*deleting nodes having 2 children*/
else if(root->left !=NULL && root->right !=NULL)
{
struct Node *temp2 = minVal(root->right);
root->data = temp2->data;
deleteNode(root->right,temp2->data);
}
}
}
int main()
{
struct Node *root = NULL;
printf("\n\n");
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
inorder(root);
//deleteNode(root,40);
deleteNode(root,30);
printf("\n\n");
inorder(root);
printf("\n\n");
}