2016-10-26 7 views
0

Я построил двоичное дерево поиска и вставил некоторые узлы случайных значений. Я пытаюсь реализовать функцию для удаления узлов, но по какой-то причине она не работает. При попытке удалить данный узел кажется, что родительский узел удаленного узла и дочерний узел удаленного узла не будут «подключаться».C++ Удалить узел из двоичного дерева поиска

Может ли кто-нибудь увидеть, что я сделал неправильно? Я пытался несколько раз отлаживать программу, чтобы увидеть, где моя ошибка, но я не понимаю, как я могу связать родителя и ребенка вместе.

Вот моя программа:

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

ответ

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.

0

При удалении узла, необходимо также установить NULL указатель, сохраненный в родительском узле.

Скажем, у вас есть узел P и C, где P.left = C, а C - листовой узел. Ваш код освободит память для C и задает временную переменную (называемую root в вашей программе) значением NULL. (BTW использует nullptr вместо NULL.) Но если вы изучите содержимое P, оно все равно относится к удаленному адресу C.

+0

Какая часть родителя и когда я устанавливаю его в NULL (или nullptr)? После удаления моей временной переменной? –

+0

В моем примере вам нужно изменить поле «left» родительского узла. Ваш алгоритм deleteNode() должен отслеживать родителя, используя отдельную временную переменную. И он должен знать, является ли удаляемый узел левым дочерним элементом или правым дочерним элементом родительского узла. –

Смежные вопросы