트리에서 노드를 삭제하는 방법은 무엇입니까?

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

당신은 노드의 삭제 후 코드

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

에서 즉

아무것도

에의 관점 NULL에 root->left->left 포인터를 설정해야합니다, 당신은 제로에 부모의 왼쪽 포인터를 다시 설정해야합니다. 이렇게하지 않으면 메모리 관리 방법에 따라 예기치 않은 결과가 발생할 수 있습니다. 일부 시스템은 해제 된 메모리에 대한 참조를 제외합니다.

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