삭제연산!
BSTNode* findMax(BSTNode* rootNode)
{
if (rootNode == NULL)
return (NULL);
else if (rootNode->rightNode == NULL)
return (rootNode);
else
return (findMax(rootNode->rightNode));
}
BSTNode* deleteBSTNode(BSTNode* rootNode, BSTNode element)
{
if (rootNode == NULL)
return (NULL);
if (element.data < rootNode->data)
rootNode->leftNode = deleteBSTNode(rootNode->leftNode, element);
else if (element.data > rootNode->data)
rootNode->rightNode = deleteBSTNode(rootNode->rightNode, element);
else //element.data == rootNode.data 찾은경우
{
if (rootNode->leftNode && rootNode->rightNode) // 자식이 2개인경우
{
BSTNode* canNode;
canNode = findMax(rootNode->leftNode); //left에서 가장 큰 값 찾기
rootNode->data = canNode->data;
rootNode->leftNode = deleteBSTNode(rootNode->leftNode, *canNode);
}
else //자식이 1개 이하
{
BSTNode* temp;
temp = rootNode;
if (rootNode->leftNode == NULL)
rootNode = rootNode->rightNode;
else if (rootNode->rightNode == NULL)
rootNode = rootNode->leftNode;
free(temp);
}
}
return (rootNode);
}