C-二进制搜索树节点删除

Question

我正在实现从二进制搜索树中删除节点的函数。设置了该功能的原型，我无法更改它，这是学校的作业。我的代码：

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; line存在问题，并且我将地址丢给了其余的分支我想弄清楚为什么。

编辑：

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

Answer 1

您在使用指针方面存在问题。如果我们有sometype *ptr，并且我们检查此PTR是否会适应一些我们编写(ptr!=NULL)的空间。 *ptr指的是值本身，例如您的Structre。在c。

Answer 2

您的删除逻辑是错误的

 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
            }