BST節點刪除功能在遞歸調用失敗

void search(struct node **root, struct node **cursor, 
      struct node **parent, int data, int *found) { 
    struct node *iterator = *root; 

    *cursor = NULL, *parent = NULL; 
    *found = FALSE; 

    while (iterator != NULL) { 
     if (data == iterator->data) { 
      *found = TRUE; 
      *cursor = iterator; 
      break; 
     } else 
     if (data <= iterator->data) { 
      *parent = iterator; 
      iterator = iterator->left; 
     } else { 
      *parent = iterator; 
      iterator = iterator->right; 
     } 
    } 
} 

void delete(struct node **root, int data) { 
    int found; 
    struct node *cursor, *parent; 

    if (*root == NULL) { 
     printf("ERROR! Binary Search Tree Empty!\n"); 
     exit(0); 
    } 
    search(root, &cursor, &parent, data, &found); 
    if (found == FALSE) { 
     printf("ERROR! Element not found in Binary Tree!\n"); 
     exit(0); 
    } 
    // If the Node has No Children 
    if (cursor->left == NULL && cursor->right == NULL) { 
     if (parent->left == cursor) { 
      parent->left = NULL; 
     } else { 
      parent->right = NULL; 
     } 
     free(cursor); 
    } 
    if (cursor->left == NULL && cursor->right != NULL) { 
     if (parent->left == cursor) { 
      parent->left = cursor->right; 
     } else { 
      parent->right = cursor->right; 
     } 
     free(cursor); 
    } 
    if (cursor->left != NULL && cursor->right == NULL) { 
     if (parent->left == cursor) { 
      parent->left = cursor->left; 
     } else { 
      parent->right = cursor->left; 
     } 
     free(cursor); 
    } 
    // If node has two children 
    if (cursor->left != NULL && cursor->right != NULL) { 
     struct node *iterator = cursor; 
     iterator = iterator->right; 
     while (iterator->left != NULL) { 
      iterator = iterator->left; 
     } 
     cursor->data = iterator->data; 
     printf("\n%i\n", iterator->data); 
     delete(&iterator, iterator->data); 
    } 
}

我想實現一個二叉搜索樹刪除功能。我已經測試了許多BST，但是當我刪除有兩個孩子的節點時，它失敗了。它在遞歸調用失敗。它給出了分段錯誤11。我該怎麼辦？BST節點刪除功能在遞歸調用失敗

來源

2016-08-16 Danish Amjad Alvi

您的程序在其生命週期結束後出現未定義的訪問對象的行爲。 – EOF

對象的生命期如何結束？ '迭代器'仍然存在，它是如何消失的？ –

C11標準草案n1570：* 6.2.4對象的存儲持續時間2對象的生命週期是程序執行的一部分，在此期間保證爲其保留存儲器 [...] 34）如果對象被引用在其生命週期外，其行爲未定義。指針的值在它指向的對象（或剛剛過去）達到其生命週期結束時變爲不確定。 7.22.3內存管理功能1 [...]分配對象的生命週期從分配擴展到釋放。[...] * – EOF

您的delete函數的問題是您在每個free(cursor);之後都不會返回。相反，您繼續測試下一個案例，取消引用剛纔釋放的cursor。問題主要是當cursor有1個孩子或沒有孩子。

來源

2016-08-16 23:51:16 chqrlie

考慮函數recurses * until * the 'cursor'有les而不是兩個孩子，這種不確定的行爲是不可避免的。 – EOF

BST節點刪除功能在遞歸調用失敗

回答

相關問題