二叉搜索樹節點刪除

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;線，我失去了我的地址到其餘的分支，但另一方面，如果這條線不包括我得到一個SEGFAULT，我想弄清楚爲什麼。

編輯：

好的，現在我知道錯誤在哪裏了。這是愚蠢的錯誤，我應該使用tBSTNodePtr tmp;而不是tBSTNodePtr * tmp;

Answer 1

您刪除的邏輯是在此代碼錯誤

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 
      } 

Answer 2

你有使用指針問題的孩子根本。如果我們有sometype *ptr，並且我們檢查這個ptr是否符合我們編寫的一些空間(ptr!=NULL)。 *ptr指的是這個值本身，比如你的structre。 瞭解C中指針類型的更多信息。