1

我正在尝试删除我以非递归方式创建的 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);
}
4

2 回答 2

0

我相信您并没有真正删除叶子-您正在递归地删除整个树：对于每个节点，您首先删除叶子，然后检查它是否是叶子((left == NULL) && (right == NULL))-这显然是因为您刚刚删除了它的后代-然后删除它。

第一个问题是，正如 Chris 很快指出的，您没有检查leafParent 是否可以变为NULL。要么检查它，要么将根节点的 parent 设置为自身，这样你就不会取消引用 NULL。另一个（恕我直言）问题是，一旦释放内存，您就不会使指针无效 - 好习惯是在释放指针后立即将指针设置为 NULL。如果您稍后不进行检查，则可以在稍后可能由其他结构分配内存块时使用指针进行段错误但不会静默破坏内存。您甚至可以编写一个包装器来为您执行此操作（它还可以检查释放 NULL 指针的尝试，这实际上是一个有效的操作，只是默默地什么都不做 - 至少在某些平台上）。在这种特殊情况下，

作为一个吹毛求疵的旁注，在代码中它要么是要么int main(void) { ... }不int main(int argc, int **argv) { ... }只是main(). :-)

于 2012-11-01T12:53:32.423 回答
0

在函数 deleteLeaf 中确实存在（注释掉的）leafParent 为 NULL 的情况，然后一旦您使用 leafParent->left 取消引用它，它就会出现段错误。因此，您需要在其中进行检查，如下所示：

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

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

于 2012-11-01T12:01:23.617 回答