c - 删除二叉搜索树的叶节点 - segmentation fault

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 为 NULL，然后一旦您使用 leafParent->left 取消引用它，它就会出现错误。因此，您需要按如下方式在其中进行检查:

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

这将防止 seg 错误，但我不清楚该函数是否最终会执行您希望它执行的操作...换句话说，您的逻辑可能仍需要一些调整才能使其仅删除叶节点(如果那是你想要做的)。