刪除二叉搜索樹的葉節點 - 分段錯誤

Question

我想刪除我已經非遞歸地創建的BST中的葉節點。問題是當我試圖刪除葉節點時，我遇到了分段錯誤，並且我不知道爲什麼會發生這種情況。我相信我所評論的代碼導致了這個問題。刪除該節點的想法是否錯誤，或者是否有任何其他方式從BST中刪除任何節點？

 #include <stdio.h> 
    #include <stdlib.h> 

     struct BSTnode 
    { 
    int data; 
    struct BSTnode *left,*right,*parent; 

    }; 

    typedef struct BSTnode node; 

    void insert(node **root,int val) 
    { 
    node *ptr,*newptr; 

    newptr=(node *)malloc(sizeof(node)); 
    newptr->left=NULL; 
    newptr->right=NULL; 
    newptr->parent=NULL; 
    newptr->data=val; 

    if((*root)==NULL) 
    { 
    (*root)=newptr; 
    return; 
    } 

    ptr=(*root); 

    while(ptr!=NULL && ptr->data!=val) 
    { 
     if(ptr->data >val) 
    { 
     if(ptr->left!=NULL) 
     ptr=ptr->left; 
     else 
     { 
     ptr->left=newptr; 
     newptr->parent=ptr; 
     break; 
     } 
    } 
    else 
    { 
     if(ptr->right!=NULL) 
     ptr=ptr->right; 
     else 
    { 
     ptr->right=newptr; 
     newptr->parent=ptr; 
     break; 
     } 
    } 
    } 

    } 

    void deleteLeaf(node **root) 
    { 

     node *leafParent=NULL; 

     if((*root)->left!=NULL) 
     deleteLeaf(&((*root)->left)); 

     if((*root)->right!=NULL) 
     deleteLeaf(&((*root)->right)); 


     if((*root)->left==NULL && (*root)->right==NULL) 
    { 

     /* leafParent=(*root)->parent; 

      if(leafParent->left==(*root)) 
      leafParent->left=NULL; 
      else 
      leafParent->right=NULL; 
     */ 

      free(*root); 
     } 
     } 

void inorder(node *root) 
{ 
    if(root->left!=NULL) 
    inorder(root->left); 

    printf(" %d ", root->data); 

    if(root->right!=NULL) 
    inorder(root->right); 
} 

main() 
{ 
node *root=NULL; 
int i,n,val; 

printf("\n How many elements ?"); 
scanf("%d",&n); 

for(i=0;i<n;++i) 
{ 
scanf("%d",&val); 
insert(&root,val); 

} 

printf("\n Inorder traversal : "); 
inorder(root); 

deleteLeaf(&root); 
printf("\n Inorder traversal : "); 
inorder(root); 
} 

Answer 1

確實有儘快在功能deleteLeaf其中（註釋掉）leafParent是空的情況下，然後當你取消對它的引用與leafParent->離開了，它賽格故障。所以，你需要把支票在那裏如下：

leafParent=(*root)->parent; 
    if (leafParent) 
    { 
     if(leafParent->left==(*root)) 
     { 
      leafParent->left=NULL; 
     } 
     else 
     { 
      leafParent->right=NULL; 
     } 
    } 

這將防止賽格故障，但我並不清楚，如果功能最終會做你想要它做的事情......換句話說你的邏輯可能仍然需要一些調整才能讓它只刪除葉節點（如果這是你正在嘗試做的）。

Answer 2

我相信你不是真的只是刪除葉子 - 你遞歸刪除整棵樹：對於每個節點，你首先刪除葉子，然後檢查它是否是葉子((left == NULL) && (right == NULL)) - 這顯然是自從你剛刪除它的後代 - 然後刪除它。

第一個問題是，正如克里斯很快指出的那樣，您並未檢查leafParent是否可以變爲NULL。請檢查該問題，或者將根節點設置爲自身，以便不取消引用NULL。另一個（imho更糟糕的）問題是，一旦釋放內存，你並不會使指針無效 - 好的習慣是一旦釋放內存就將指針設置爲NULL。如果你稍後不做檢查，你可以segfault，但是不會在稍後使用指針來靜靜地損壞內存，當內存塊可能被其他結構分配時。你甚至可以編寫一個包裝器來爲你做這件事（它也可以檢查嘗試釋放一個NULL指針，這實際上是一個有效的操作，至少在某些平臺上，它只是默默無聞地做任何事情）。在這種特殊情況下，一旦完成刪除整個樹（因爲這是真正發生的情況），您仍然有指向main（）中已刪除的根節點的指針 - 並立即使用它。

作爲一個挑剔的方面，在代碼它是int main(void) { ... }或int main(int argc, int **argv) { ... }不只是main()。 :-)