二叉搜索树节点删除

我正在实现从二叉搜索树中删除节点的功能。该功能的原型已设置，我无法更改它，它是一个学校作业。我的代码：二叉搜索树节点删除

typedef struct tBSTNode { 
    char Key;                 
    struct tBSTNode * LPtr;         
    struct tBSTNode * RPtr; 
} *tBSTNodePtr; 

void BSTDelete (tBSTNodePtr *RootPtr, char K) { 
    tBSTNodePtr *tmp; 

    if (*RootPtr != NULL) { 
    if (K < (*RootPtr)->Key) 
     BSTDelete(&(* RootPtr)->LPtr, K); 
    else if (K > (*RootPtr)->Key) 
     BSTDelete(&(* RootPtr)->RPtr, K); 
    else { 
      if ((* RootPtr)->LPtr == NULL) { 
       /* there is only right branch or none*/ 
       tmp = RootPtr; 
       *RootPtr = (* RootPtr)->RPtr; 
       free(*tmp); 
       *tmp = NULL; 
      } 
      else if ((* RootPtr)->RPtr == NULL) { 
       /* there is only left branch or none*/ 
       tmp = RootPtr; 
       *RootPtr = (* RootPtr)->LPtr; 
       free(*tmp); 
       *tmp = NULL; 
      } 
      else 
       /* there are both branches, but that is for another topic*/ 
     } 
    } 
}

此代码工作正常，以防万一在没有连接到我删除节点分支。我期望* tmp = NULL;线，我失去了我的地址到其余的分支，但另一方面，如果这条线不包括我得到一个SEGFAULT，我想弄清楚为什么。

编辑：

好的，现在我知道错误在哪里了。这是愚蠢的错误，我应该使用tBSTNodePtr tmp;而不是tBSTNodePtr * tmp;

来源

2012-11-05 skornos

您删除的逻辑是在此代码错误

if ((* RootPtr)->LPtr == NULL) { 
       /* there is only right branch or none*/ 
       tmp = RootPtr; 
       *RootPtr = (* RootPtr)->RPtr; 
       free(*tmp); 
       *tmp = NULL; 
      }

要删除所需的节点，但不能添加节点

if ((* RootPtr)->LPtr == NULL) { 
       /* there is only right branch or none*/ 
       tmp = RootPtr; 
       *RootPtr = (* RootPtr)->RPtr; 
       free(*tmp); 
       *tmp = NULL; 
       insert(RootPtr); //insert the child node again in the tree 
      }

来源

2012-11-05 09:24:31

不幸的是，我不允许调用另一个函数insert（），所以我需要使用我已经显示的代码 – skornos

你有使用指针问题的孩子根本。如果我们有sometype *ptr，并且我们检查这个ptr是否符合我们编写的一些空间(ptr!=NULL)。 *ptr指的是这个值本身，比如你的structre。了解C中指针类型的更多信息。

来源

2012-11-05 09:31:42

是的我知道在C和I中使用指针的概念我正在使用它，因为你可以看到。但是在指针逻辑中有一个问题，你的回答没有清除任何东西 – skornos

哦，对不起。我没有注意到typedef中的'*'。 –

我想我找到了。这是错误的逻辑。如果没有左侧孩子和右侧孩子，则同时输入两个if和free两次。下面说的是非常正确的，这是问题的关键。但我想你应该在条件中加上&&（* RootPtr） - > otherside！= NULL'，以便你的程序工作更加正确。 –

二叉搜索树节点删除

回答

相关问题