이진 검색 트리에서 모든 리프 노드를 삭제하는 기능

Question

해당 기능에 대한 수정을 요청하고 싶습니다. 문제는 나뭇잎보다 많은 노드를 삭제한다는 것입니다. 먼저 모든 나뭇잎을 삭제하고 방금 만든 나뭇잎을 삭제한다는 의미입니다. 수정 방법을 알려주십시오. 리프 = 자식 노드가없는 노드.

typedef struct node { 
    int key; 
    node* left; 
    node* right; 
}node; 

void BST::DeleteLeafs() 
{ 
    if (root == nullptr) 
     throw InvalidOperationException(); 
    else 
     deleteLeavesHelper(nullptr, root); 
} 

void BST::deleteLeavesHelper(node* parent, node* n) 
{ 
    if (n == nullptr) 
     return; 
    else 
    { 
     if (n->left == nullptr && n->right == nullptr) 
     { 
      n = nullptr; 
      if (parent != nullptr) 
      { 
       parent->left = nullptr; 
       parent->right = nullptr; 
      } 
     } 
     else 
     { 
      deleteLeavesHelper(n, n->left); 
      deleteLeavesHelper(n, n->right); 
     } 
    } 
} 

Answer 1

당신은 쓰기 :

if (n->left == nullptr && n->right == nullptr) 
    { 
     n = nullptr; 
     if (parent != nullptr) 
     { 
      parent->left = nullptr; 
      parent->right = nullptr; 
     } 
    } 

하나의 문제는, 당신이 n에 대한 메모리 할당을 해제해야한다, 그렇지 않으면 당신은 메모리 누수가. n=nullptr;은 완전히 쓸모가 없습니다.

또 다른 문제는 parent의 두 자식에 대한 포인터를 무효화하는 것입니다. 대신 올바른 아동을 가리키는 포인터 만 무효화해야합니다.

if (n->left == nullptr && n->right == nullptr) { 
    if (parent != nullptr) { 
     if (parent->left == n) 
      parent->left = nullptr; 
     else if (parent->right == n) 
      arent->right = nullptr; 
     else 
      // raise some exception 
    } 
    // deallocate n 
}