使用父指针从二叉搜索树中删除节点

Question

我正在研究从二叉搜索树中删除具有给定密钥的节点的算法。到目前为止，我已经能够想出下面的代码：

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

typedef int ElType; 

typedef struct Tree { 
    ElType key; 
    struct Tree *left; 
    struct Tree *right; 
    struct Tree *parent; 
} Tree; 

Tree* InsertBST(Tree* t, int k) 
{ 
    if (t == NULL) { 
     Tree* w = (Tree*) malloc(sizeof(Tree)); 
     w->key = k; 
     w->left = NULL; 
     w->right = NULL; 
     w->parent = NULL; 
     return w; 
    } 

    if (k <= t->key) { 
     t->left = InsertBST(t->left, k); 
     t->left->parent = t; 
    } 
    else { 
     t->right = InsertBST(t->right, k); 
     t->right->parent = t; 
    } 

    return t; 
} 

Tree* DeleteMaxOfBST(Tree* t, ElType *deleted_value) 
{ 
    if (t == NULL) { 
     *deleted_value = -1; 
     return NULL; 
    } 

    if (t->right == NULL) { 
     *deleted_value = t->key; 
     Tree* w = t->left; 
     w->parent = t->parent; 
     free(t); 
     return w; 
    } 

    t->right = DeleteMaxOfBST(t->right, deleted_value); 
    return t; 
} 

Tree* DeleteNodeOfBST(Tree* t, int k) 
{ 
    if (t == NULL) return NULL; 

    if (k < t->key) { 
     t->left = DeleteNodeOfBST(t->left, k); 
     return t; 
    } 
    else if (k > t->key) { 
     t->right = DeleteNodeOfBST(t->right, k); 
     return t; 
    } 
    else if (t->left == NULL) { 
     Tree* w = t->right; 
     w->parent = t->parent; 
     free(t); 
     return w; 
    } 
    else { 
     ElType max_left; 
     t->left = DeleteMaxOfBST(t->left, &max_left); 
     t->key = max_left; 
     return t; 
    } 
} 

总的想法是，我想用指针与BST合作，父节点，并能删除与哪个键我的一个节点指定的同时保留BST的结构。

我的代码适用于某些树中的某些键，但是对于没有任何明显模式的其他键会崩溃。然后我得到了以下错误：

Segmentation fault (core dumped) 

我倾向于认为我已经搞砸指针指向父节点，但不能完全准确判断故障。我对C相对来说比较陌生，所以我很感激任何评论，指针是否实际上是这里的问题，以及如何解决这个问题。

Answer 1

这里是C程序在二叉搜索树递归插入和删除源代码..................

/* C Program for Insertion and Deletion in Binary Search Tree Recursive */ 

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

struct node 
{ 
    struct node *lchild; 
    int info; 
    struct node *rchild; 
}; 

struct node *insert(struct node *ptr, int ikey); 
void display(struct node *ptr,int level); 
struct node *del(struct node *ptr, int dkey); 

int main() 
{ 
    struct node *root=NULL,*ptr; 
    int choice,k; 
    while(1) 
    { 
     printf("\n"); 
     printf("1.Insert\n"); 
     printf("2.Delete\n"); 
     printf("3.Display\n"); 
     printf("4.Quit\n"); 
     printf("\nEnter your choice : "); 
     scanf("%d",&choice); 

     switch(choice) 
     { 
     case 1: 
      printf("Enter the key to be inserted : "); 
      scanf("%d",&k); 
      root = insert(root, k); 
      break; 
     case 2: 
      printf("Enter the key to be deleted : "); 
      scanf("%d",&k); 
      root = del(root,k); 
      break; 
     case 3: 
      display(root,0); 
      break; 
     case 4: 
      exit(1); 
     default: 
      printf("\nWrong choice\n"); 
     }/*End of switch */ 
    }/*End of while */ 

    return 0; 

}/*End of main()*/ 

struct node *insert(struct node *ptr, int ikey) 
{ 
    if(ptr==NULL) 
    { 
     ptr = (struct node *) malloc(sizeof(struct node)); 
     ptr->info = ikey; 
     ptr->lchild = NULL; 
     ptr->rchild = NULL; 
    } 
    else if(ikey < ptr->info) /*Insertion in left subtree*/ 
     ptr->lchild = insert(ptr->lchild, ikey); 
    else if(ikey > ptr->info) /*Insertion in right subtree */ 
     ptr->rchild = insert(ptr->rchild, ikey); 
    else 
     printf("\nDuplicate key\n"); 
    return ptr; 
}/*End of insert()*/ 

void display(struct node *ptr,int level) 
{ 
    int i; 
    if(ptr == NULL)/*Base Case*/ 
     return; 
    else 
    { 
     display(ptr->rchild, level+1); 
     printf("\n"); 
     for (i=0; i<level; i++) 
      printf(" "); 
     printf("%d", ptr->info); 
     display(ptr->lchild, level+1); 
    } 

     printf("\n"); 

}/*End of display()*/ 


struct node *del(struct node *ptr, int dkey) 
{ 
    struct node *tmp, *succ; 

    if(ptr == NULL) 
    { 
     printf("dkey not found\n"); 
     return(ptr); 
    } 
    if(dkey < ptr->info)/*delete from left subtree*/ 
     ptr->lchild = del(ptr->lchild, dkey); 
    else if(dkey > ptr->info)/*delete from right subtree*/ 
     ptr->rchild = del(ptr->rchild, dkey); 
    else 
    { 
     /*key to be deleted is found*/ 
     if(ptr->lchild!=NULL && ptr->rchild!=NULL) /*2 children*/ 
     { 
      succ=ptr->rchild; 
      while(succ->lchild) 
       succ=succ->lchild; 
      ptr->info=succ->info; 
      ptr->rchild = del(ptr->rchild, succ->info); 
     } 
     else 
     { 
      tmp = ptr; 
      if(ptr->lchild != NULL) /*only left child*/ 
       ptr = ptr->lchild; 
      else if(ptr->rchild != NULL) /*only right child*/ 
       ptr = ptr->rchild; 
      else /* no child */ 
       ptr = NULL; 
      free(tmp); 
     } 
    } 
    return ptr; 
}/*End of del()*/ 

希望它可以帮助您。欲了解更多详情，请访问这里了解更多关于操作二叉搜索树--->C Program for Insertion and Deletion in Binary Search Tree Recursive

和C Program for binary search tree deletion without recursion

Answer 2

所以，没有怎么你的代码运行它很难说究竟在何处分割故障时发生的任何实例你的程序正在运行。当程序遇到分段错误时，意味着程序试图访问内存，无论出于何种原因它都无法访问。这通常意味着你的指针试图指向他们不应该在内存中的地址。

我的建议是逐步运行代码，看看问题出在哪里。或者找到一个调试器，可以显示您的程序正在使用的内存问题。我知道Valgrind程序存在于Ubuntu和其他Linux最好的机器上，但我不确定其他操作系统可以使用哪些程序。你可以在这里阅读关于Valgrind的更多信息：http://valgrind.org/。每当我需要检查我的程序中潜在的内存处理问题时，我都会使用它。

除此之外，只要密切关注您使用malloc创建的空间以及指针指向的位置即可。确保在删除给定节点时正确重新连接树。手动处理记忆可能是一种痛苦，但你会得到它的诀窍。