0
C에서 BST를 구현했습니다. 삽입 및 조회가 정상적으로 작동합니다. 그러나 삭제는 루트 노드를 삭제할 때 문제가 있습니다. 루트 노드에 대한 포인터를 해제 할 수 없습니다. 이중 포인터로 전달하면 될 수 있지만 이중 포인터를 사용하지 않고 코드를 간단하게 유지하려고합니다. 여기에는 루트 노드를 가리키는 헤드 포인터가 없습니다. 루트 노드에 헤드 포인터를 사용해야합니까?C에서 이진 검색 트리에서 삭제
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = malloc(sizeof(struct node));
node->data=data;
node->left=NULL;
node->right=NULL;
return(node);
}
static int lookup(struct node* node,int target)
{
if(node==NULL)
{
return(0);
}
else
{
if(target == node->data)
{
return(1);
}
else
{
if(target < node->data)
{
return(lookup(node->left,target));
}
else
{
return(lookup(node->right,target));
}
}
}
}
struct node* insert(struct node* node, int data)
{
if(node==NULL)
{
return(newNode(data));
}
else
{
if(data < node->data)
{
node->left =insert(node->left,data);
}
else
{
node->right=insert(node->right,data);
}
return(node);
}
}
struct node* delete(struct node* node, struct node* pnode, int target)
{
struct node* rchild;
struct node* rchildparent;
if(node==NULL)
{
return(pnode);
}
else
{
if(target == node->data)
{
if(node->left == NULL && node->right == NULL) //leaf node
{
if(pnode == NULL) //special case deleting the root node
{
free(node);
return(NULL);
}
if(pnode->left == node)
{
pnode->left = NULL;
}
else
{
pnode->right = NULL;
}
free(node);
return(pnode);
}
if(node->left ==NULL) //one child
{
if(pnode == NULL) //deleting root having no left child
{
struct node* temp = node;
node = node->right;
free(temp);
return(node);
}
if(pnode->left == node)
{
pnode->left = node->right;
}
else
{
pnode->right = node->right;
}
free(node);
return(pnode);
}
if(node->right ==NULL) //one child
{
if(pnode == NULL) //deleting root having no right child
{
struct node* temp = node;
node = node->left;
free(temp);
return(node);
}
if(pnode->left == node)
{
pnode->left = node->left;
}
else
{
pnode->right = node->left;
}
free(node);
return(pnode);
}
//two children case
rchild = node->right;
rchildparent=node;
while(rchild->left != NULL)
{
rchildparent=rchild;
rchild = rchild->left;
}
node->data=rchild->data;
if(rchildparent == node)
{
//rchildparent->right=rchild->right;
node->right=rchild->right;
}
else
{
//rchildparent->left=NULL;
rchildparent->left=rchild->right;
}
free(rchild);
if(pnode ==NULL) //root node
{
return(node);
}
return(pnode);
}
else
{
if(target < node->data)
{
delete(node->left,node,target);
return(node);
}
else
{
delete(node->right,node,target);
return(node);
}
}
}
}
void printinorder(struct node* node)
{
if(node == NULL)
{
return;
}
printinorder(node->left);
printf("%d\t",node->data);
printinorder(node->right);
}
int main()
{
clock_t start,end;
struct node* root = newNode(3);
insert(root,7);
insert(root,7);
insert(root,7);
printinorder(root);
printf("\n");
root = delete(root,NULL,6);
printinorder(root);
printf("\n");
}
편집 : 이 modifiable lvalue 제안 @에 따라 코드를 수정했습니다. 이제 삭제 논리를 개선 할 수있는 방법이 있습니까?
나는 아무 문제가 newNode''함수에서'malloc'와 함께이없는 것 같아요. 문제는 루트 노드에 대한 포인터의 로컬 사본을 해제하는'delete' 함수에 있습니다. – arunmoezhi
'delete' 함수에 전달되어야하는 특별한 ROOT 포인터가 필요할 것입니다. 또 다른 해결책은 비 재귀적인'delete' 함수를 작성하여 새로운 루트가 될'node *'를 반환하도록하는 것입니다. – uba
@ Koushik 무슨 말씀 이세요? malloc이 실패 할 때 잠재적 인 NULL 역 참조를 제외하고는 newNode가 좋습니다. – Sebivor