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()에서 부모의 자식 포인터 중 하나를 NULL로 설정해야 할 수도 있습니다.

Answer 2

:

여기 내 프로그램입니다.

노드 P와 C가 있다고 가정 해보십시오. 여기서는 P.left = C이고 C는 잎 노드입니다. 코드는 C에 대한 메모리 할당을 해제하고 임시 변수 (프로그램의 루트라고 함)를 NULL로 설정합니다. (BTW는 NULL 대신 nullptr을 사용합니다.)하지만 P의 내용을 검사하면 여전히 C의 할당 해제 된 주소를 참조합니다.