Удалить метод узла, фактически не удаляющий узел в бинарном дереве поиска. C ++ - PullRequest
Новая
       27

Удалить метод узла, фактически не удаляющий узел в бинарном дереве поиска. C ++

0 голосов
/ 09 июля 2019

Когда я вызываю мой метод removeNode, он показывает, что локально удаляет узел и устанавливает его в null в отладчике, но когда я смотрю на дерево в отладчике, узел, который должен был быть удален, все еще там.Когда я печатаю дерево, печатается узел, который должен был быть удален, но int и строка, присвоенные структуре, указывают вместо этого на распечатку.

Я пытался использовать free () и удалить, но ни один из них не удалил. 

bool BinTree::addNode(int id, string info, DataNode *add_node) {
    auto *temp_node = new DataNode;
    temp_node->data.id = id;
    temp_node->data.information = info;
    temp_node->left = temp_node->right = nullptr;

    if(id < add_node->data.id){
        if(!add_node->left){
            add_node->left = new DataNode;
            add_node->left = temp_node;
            count++;
        }else{
            addNode(id, info, add_node->left);
        }
    }else{
        if(!add_node->right){
            add_node->right = new DataNode;
            add_node->right = temp_node;
            count++;
        }else{
            addNode(id, info, add_node->right);
        }
    }
}

bool BinTree::removeNode(int id, DataNode *temp_root) {
    cout << "Searching to remove: " << id << endl;
    if(temp_root == nullptr){
        return false;
    }
    else if(id < temp_root->data.id) {
        removeNode(id, (temp_root->left);
    }
    else if(id > temp_root->data.id){
        removeNode(id, temp_root->right);
    }
    else{
        //no child
        if(temp_root->left == nullptr && temp_root->right == nullptr){
            cout << "Deleting no children node" << endl;            //DEBUG ONLY
            cout << "Temp root address:" << temp_root << endl;      //DEBUG ONLY
            delete temp_root;
            temp_root->data.id = 123456;                            //DEBUG ONLY
            cout << "no child deleted" << endl;                     //DEBUG ONLY
            count--;
        }
        //one child
        else if(temp_root->left == nullptr){
            cout << "Deleting 1 child node" << endl;
            DataNode *temp_node = temp_root;
            temp_root = temp_root->right;
            delete temp_node;
            temp_node = nullptr;
            count--;
        }
        else if(temp_root->right == nullptr){
            cout << "Deleting 1 child node" << endl;
            DataNode *temp_node = temp_root;
            temp_root = temp_root->left;
            free(temp_node);
            temp_node = nullptr;
            count--;
        }
        //two children
        else if(temp_root->left && temp_root->right){
            cout << "Deleting 2 child node" << endl;
            DataNode temp_node = minValueNode(temp_root->right);
            temp_root->data = temp_node.data;
            removeNode(temp_node.data.id, temp_root->right);
        }
        return true;
    }
}

DataNode BinTree::minValueNode(DataNode *temp_node) {
    while(temp_node->left){
        temp_node = temp_node->left;
    }
    return *temp_node;
}

У меня есть некоторые отладочные выходные данные в методе, чтобы проверить, что адрес temp_root, который он удаляетэто тот же адрес, который дерево имеет для данного узла, и это правильно.Он просто не удаляется из реального дерева.

1 Ответ

2 голосов
/ 10 июля 2019

Лично я бы написал удалить, чтобы вернуть новое значение ссылки. 

void removeNode(int id) {
    root = removeNode(id, root);
}
Node* removeNode(int id, Node* n) {
    if (n == nullptr) {
        return nullptr;
    }

    if (id < n->id) {
        n->left = removeNode(id, n->left);
        return n;
    }
    else if (n->id < id) {
        n->right = removeNode(id, n->right);
        return n;
    }
    else if (n->left == null) {
         Node* result = n->right;
         delete n;
         return result;
    }
    else if (n->right == null) {
         Node* result = n->left;
         delete n;
         return result;
    }
    else {
         int v = findSmallestValue(n->right);
         n->right = removeNode(v, n->right);
         n->id = v;
         return n;
    }
}
...