c - 尝试从二叉搜索树中删除节点时获取 SEGFAULT

Question

我正在用 C 实现二叉搜索树。下面的代码工作正常，只是当我尝试从树中删除子树时得到 SEGFAULT:

源代码:

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

struct node {
    int data;
    struct node * right, * left;
};

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

 void deltree(struct node* node)
{
    if (node == NULL) return;

    struct node *r = node->right;

    deltree(node->left);
    free(node);
    deltree(r);
}

node* search(node ** tree, int val)
{
    if(!(*tree))
        return NULL;

    if(val < (*tree)->data)
    {
        return search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        return search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return *tree;
    }
    return NULL;
}

void _deleteTree(struct node* node)
{
    if (node == NULL) return;

    _deleteTree(node->left);
    _deleteTree(node->right);

    printf("\nDeleting node: %d", node->data);
    free(node);
}

void deleteTree(struct node** node_ref)
{
  _deleteTree(*node_ref);
  *node_ref = NULL;
}


int  main()
{
    node *root;
    node *tmp;
    node *tmp1;

    root = NULL;
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    printf("\nPrinting tree before deletion...\n");
    print_postorder(root);

    tmp1 = search(&root, 15);

    printf("Deleting subtree...\n");
    deleteTree(&tmp1);

    printf("\nPrinting tree after deletion...\n");
    print_postorder(root);
}

输出:

Printing tree before deletion...
2
6
4
12
17
15
9

Deleting subtree...

Deleting node: 12
Deleting node: 17
Deleting node: 15
Printing tree after deletion...
2
6
4
Segmentation fault: 11

请注意，我想从整个树中删除子树(尽管我的代码也应该适用于整个树)。

Answer 1

当您使用参数 &tmp1 调用 deleteTree 时，deleteTree 函数会将 tmp1 设置为指向 空。但是，这对实际树中的相应指针(即树中指向包含该节点的节点的 left 或 right 指针没有影响)值 15)。该指针仍然指向现在已删除的节点。

按如下方式更改搜索:

node** search(node ** tree, int val)
{
    if(!(*tree))
        return NULL;

    if(val < (*tree)->data)
    {
        return search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        return search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return tree;
    }
    return NULL;
}

主要功能如下:

node** tmp1;
...
printf("Deleting subtree...\n");
deleteTree(tmp1);