嘗試從二叉搜索樹中刪除節點時得到SEGFAULT

我在C中實現了二叉搜索樹。下面的代碼正常工作，除了當我嘗試從我的樹中刪除子樹時得到SEGFAULT：嘗試從二叉搜索樹中刪除節點時得到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

普萊斯e注意我想從整棵樹中刪除子樹（儘管我的代碼也適用於整棵樹）。

來源

2014-03-26 syntagma

節點的父節點在刪除節點後引用已刪除的節點。這就是爲什麼你會遇到段錯誤，將父母設置爲空或者爲空。 – thumbmunkeys

當你調用deleteTree的說法&tmp1，該deleteTree函數設置tmp1指向NULL。但是，這對實際樹中的相應指針（即指向包含值15的節點的樹中節點的left或right指針）沒有影響。該指針仍然指向現在被刪除的節點。

更改搜索條件如下：

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);

來源

2014-03-26 11:47:17 jlahd

爲什麼會得到段錯誤的原因是，你指向一個沒有任何意義的地址。在釋放指向15的節點之後，將tmp1設置爲NULL。除非您沒有將父級的右側子指針設置爲NULL，否則您現在所做的所有操作都是正確的，現在它仍然指向原始地址。但是這個地址現在毫無意義。在我的電腦上，它並沒有產生SEGFAULT，而是打印出一些隨機數字。

來源

2014-03-26 12:27:13

嘗試從二叉搜索樹中刪除節點時得到SEGFAULT

回答

相關問題