バイナリ検索ツリーからすべてのリーフノードを削除する機能

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;は完全に役に立たない。

もう1つの問題は、両方の子へのポインターを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 
}