C-带有父指针从二进制搜索树中删除节点

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

因此，没有任何示例关于您的代码如何运行，很难说出程序运行时的分割故障在哪里发生。当您的程序遇到细分故障时，这意味着程序正在尝试访问内存，无论出于何种原因，它都无法。通常这意味着您的指针试图指出记忆中不应该是的地址。

我的建议是逐步运行代码，看看问题发生在哪里。或找到可以向您展示程序的内存问题的调试器。我知道ubuntu和其他Linux最好的机器的程序Valgrind存在，但我不确定其他OS可以使用哪些其他。您可以在此处阅读有关Valgrind的更多信息：http：//valgrind.org/。每当需要检查程序中的潜在内存处理问题时，我都会使用它。

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

Answer 2

这是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.Insertn");
        printf("2.Deleten");
        printf("3.Displayn");
        printf("4.Quitn");
        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 choicen");
        }/*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 keyn");
    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 foundn");
        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程序插入和删除二进制搜索树递归

和C程序，用于二进制搜索树删除无递归