c-deleteWord中的BinarySearchTree-保留对从树中删除的元素的引用

Question

我被要求为学校做一个项目，这是一个使用二进制搜索树的词典。我在使用removeWord函数时遇到了一个大问题。我需要释放我需要删除的单词，但当我删除词根时，我无法保留指向它的指针。这是我的代码（我只保留了一个案例，因为我怀疑你需要更多，所以它会更容易阅读。但如果你告诉我的话）

void removeWord(BST* tree, char* word)
{
    BST* matchWord = getWord(tree, word); //point to the node matching the word to delete
    if (matchWord->rightSon == NULL)
    {
        *tree = *(transplant(tree, matchWord, matchWord->leftSon));
    }
    free(matchWord); //matchWord point to the new root of the tree so iznogoud
}
BST* transplant(BST* tree, BST* first, BST* second)
{
    if (first->parent == NULL)
    {
        tree = second; //here wordMatch becomes second as well and I don't want to
    }
    return tree;
}

有人能告诉我怎么做吗？

Answer 1

找到以下可以帮助您完成项目的解决方案：

void removeWord(BST* tree, char* word)
{
   //point to the node matching the word to delete
   BST* matchWord = getWord(tree, word);
   //If word matches then it's not NULL
   if (NULL != matchWord)
   {
      //Find right son if NULL then 
      //we need to transplant left son to parent position
      Transplant(tree, matchWord);
      //Remove memory of removed node
      free(matchWord);
      matchWord = NULL;
   }
}
int transplant(BST* tree, BST* matchWord)
{
   if (NULL != matchWord->leftSon)
   {
      //Here you need to apply logic which saves matchWord's leftSon to parent's son location where matchWord is present.
      //And also have to check if matchWord is having rightSon then rightSon branch is also need to be saved at right position of matchWord.
   }
   else if (NULL != matchWord->rightSon)
   {
      //Here you need to apply logic which saves matchWord's rightSon to parent's son location where matchWord is present.
      //And also have to check if matchWord is having leftSon then leftSon branch is also need to be saved at left position of matchWord.
   }
   else
   {
      //Here you need to remove matchWord's location from it's parent branches.
   }
}

如果有任何疑问，请告诉我。在做BST的程序之前，你可能需要先彻底了解它，这对你有很大帮助。您可以从中找到详细信息http://en.wikipedia.org/wiki/Binary_search_tree