如何刪除樹中的節點？

Question

我想在C++中使用指針實現一個簡單的二叉樹。

我已經成功實施的插入和遍歷，但我有一些問題，當我試圖刪除一個節點：

我的主要功能是：

main(){ 
node* root=createNode(1); 
root->left=createNode(2); 
root->right=createNode(3); 
root->left->left=createNode(4); 
root->left->right=createNode(5); 
root->right->left=createNode(6); 
root->right->right=createNode(7); 
inorder(root); 
//till here it works fine 

delete root->left->left;  //problem starts here 
cout<<"\n"; 
inorder(root);    //exception is thrown here... 
return 0; 

} `

序函數是非常基本的遞歸函數：

void inorder(node* root){ 
if(root!=NULL){ 
    inorder(root->left); 
    cout<<root->data<<" "; 
    inorder(root->right); 
} 
} 

任何人都可以告訴我刪除行有什麼問題嗎？

Answer 1

在delete之後，嘗試訪問已刪除的指針將導致此問題。您可能要添加

root->left->left = 0 

刪除後的行。

Answer 2

您必須將root->left->left指針設置爲NULL即它的指向什麼

在你的代碼

main() 
{ 
    node* root=createNode(1); 
    root->left=createNode(2); 
    root->right=createNode(3); 
    root->left->left=createNode(4); 
    root->left->right=createNode(5); 
    root->right->left=createNode(6); 
    root->right->right=createNode(7); 
    inorder(root); 
    //Now, Complete program will work 

    delete root->left->left = 0;  //problem solved 
    cout<<"\n"; 
    inorder(root);    // Do you still face any problem ? 
    return 0; 
} 

Answer 3

節點的刪除後，你需要給母公司左指針歸零。 不這樣做可能會導致不可預知的結果，這取決於如何實施內存管理。一些系統對引用釋放內存不以爲意

Answer 4

Your trying to delete node which has not null nodes in both right and left side, so you to delete node like this .. 

/* deletes a node from the binary search tree */ 
void delete (struct btreenode **root, int num) 
{ 
    int found ; 
    struct btreenode *parent, *x, *xsucc ; 

    /* if tree is empty */ 
if (*root == NULL) 
    { 
     printf ("\nTree is empty") ; 
     return ; 
    } 

    parent = x = NULL ; 

    /* call to search function to find the node to be deleted */ 

    search (root, num, &parent, &x, &found) ; 

    /* if the node to deleted is not found */ 
if (found == FALSE) 
    { 
     printf ("\nData to be deleted, not found") ; 
     return ; 
    } 

    /* if the node to be deleted has two children */ 
if (x -> leftchild != NULL && x -> rightchild != NULL) 
    { 
     parent = x ; 
     xsucc = x -> rightchild ; 

     while (xsucc -> leftchild != NULL) 
     { 
      parent = xsucc ; 
      xsucc = xsucc -> leftchild ; 
     } 

     x -> data = xsucc -> data ; 
     x = xsucc ; 
    } 

    /* if the node to be deleted has no child */ 
if (x -> leftchild == NULL && x -> rightchild == NULL) 
    { 
     if (parent -> rightchild == x) 
      parent -> rightchild = NULL ; 
     else 
      parent -> leftchild = NULL ; 

     free (x) ; 
     return ; 
    } 

    /* if the node to be deleted has only rightchild */ 
if (x -> leftchild == NULL && x -> rightchild != NULL) 
    { 
     if (parent -> leftchild == x) 
      parent -> leftchild = x -> rightchild ; 
     else 
      parent -> rightchild = x -> rightchild ; 

     free (x) ; 
     return ; 
    } 

    /* if the node to be deleted has only left child */ 
if (x -> leftchild != NULL && x -> rightchild == NULL) 
    { 
     if (parent -> leftchild == x) 
      parent -> leftchild = x -> leftchild ; 
     else 
      parent -> rightchild = x -> leftchild ; 

     free (x) ; 
     return ; 
    } 
}