C++バイナリ検索ツリーからノードを削除

Question

バイナリ検索ツリーを構築し、いくつかのランダム値ノードを挿入しました。私は、ノードを削除する関数を実装しようとしていますが、何らかの理由で動作しません。特定のノードを削除しようとすると、削除されたノードの親ノードと削除されたノードの子ノードは「接続」しないようです。

私は間違ったことを誰にでも見せてくれるでしょうか？私は間違いがどこにあるかを見るためにプログラムを何度もデバッグしようとしましたが、私は親と子をどのようにリンクさせることができないのか分かりません。ノードを削除すると、あなたはまた、親ノードに格納されるNULLポインタを設定する必要が

#include <iostream> 
using namespace std; 

struct Node 
{ 
    int data; 
    Node* left; 
    Node* right; 
}; 

Node* insertNode(Node* root, int n); 
Node* newNode(int d); 
Node* deleteNode(Node* root, int d); 
Node* findMin(Node* root); 

int main() 
{ 
    int num; 
    Node* rootPtr = NULL; 
    Node* min; 

    rootPtr = insertNode(rootPtr, 15); 
    rootPtr = insertNode(rootPtr, 10); 
    rootPtr = insertNode(rootPtr, 20); 
    rootPtr = insertNode(rootPtr, 24); 
    rootPtr = insertNode(rootPtr, 7); 
    rootPtr = insertNode(rootPtr, 25); 
    rootPtr = insertNode(rootPtr, 5); 

    rootPtr = deleteNode(rootPtr, 7); 

    cout << "\nEnter a number to search for: "; 
    cin >> num; 
    if(search(rootPtr, num)) 
     cout << "\nFound."; 
    else 
     cout << "\nNot found."; 

    cout << endl; 
    return 0; 
} 

Node* insertNode(Node* root, int n) 
{ 
    if(root == NULL)         
     root = newNode(n);       
    else if(n <= root->data)       
     root->left = insertNode(root->left, n);  
    else if(n > root->data)       
     root->right = insertNode(root->right, n); 
    return root;          
} 

Node* newNode(int d) 
{ 
    Node* newNode = new Node();    
    newNode->data = d;      
    newNode->left = newNode->right = NULL; 
    return newNode;       
} 

bool search(Node* root, int d) 
{ 
    if(root == NULL)      
     return false; 
    else if(root->data == d)    
     return true; 
    else if(d < root->data)    
     return search(root->left, d); 
    else if(d > root->data)    
     return search(root->right, d); 
} 

Node* deleteNode(Node* root, int d) 
{ 
    if(root == NULL) 
     return root; 
    else if(d < root->data) 
     deleteNode(root->left, d); 
    else if(d > root->data) 
     deleteNode(root->right, d); 
    else 
    { 
     if(root->left == NULL && root->right == NULL) 
     { 
      delete root; 
      root = NULL; 
     } 
     else if(root->left == NULL)  
     { 
      Node* temp = root;  
      root = root->right;   
      delete temp;     
     } 
     else if(root->right == NULL)  
     { 
      Node* temp = root;   
      root = root->left;   
      delete temp;     
     } 
     else 
     { 
      Node* temp = findMin(root->right); 
      root->data = temp->data;    
      root->right = deleteNode(root->right, temp->data); 
     } 
    } 
    return root; 
} 

Node* findMin(Node* root) 
{ 
    if(root == NULL) 
     cout << "\nThe tree is empty."; 
    else 
    { 
     Node* temp = root;   
     while(temp->left != NULL) 
      temp = temp->left;  
     return temp;     
    } 
} 

Answer 1

deleteNode()関数では、ノードは再帰の戻りパスで接続されません。 insertNode()の場合と同じように、関数の戻り値を使用する必要があるかもしれません。例えば、

else if(d < root->data) 
    deleteNode(root->left, d); 
else if(d > root->data) 
    deleteNode(root->right, d); 

は、（のようなもの）であるかもしれない

else if(d < root->data) 
    root->left = deleteNode(root->left, d); 
else if(d > root->data) 
    root->right = deleteNode(root->right, d); 

また、findMin()の呼び出し側は分ノードとその親の両方が必要になる場合があります。両方を返そう。 deleteNode()では、parentの子ポインタの1つをNULLに設定する必要があります。

Answer 2

：

は、ここに私のプログラムです。

ノードPとノードCがあり、Pleft = Cであり、Cがリーフノードであるとします。あなたのコードはCのメモリを解放し、一時変数（プログラムのrootと呼ばれる）をNULLに設定します。 （BTWはNULLの代わりにnullptrを使用します）。しかし、Pの内容を調べると、依然としてCの割り当て解除されたアドレスを参照します。