C bST删除节点会破坏排序算法

Question

我正在尝试为二进制搜索树实现递归删除算法，并成功地做到了这一点，但它破坏了排序算法(Inorder，inorder，predorder和postorder(。这是我的删除功能的代码

void remove_rec(string word, Node* ptr) {
        if (word < ptr->data && ptr->left != nullptr) {
            remove_rec(word, ptr->left);
        }
        else if (word > ptr->data && ptr->right != nullptr) {
            remove_rec(word, ptr->right);
        }
        else {
            //if the node has no children
            if (ptr->left == nullptr && ptr->right == nullptr) {
                delete(ptr);
                ptr = nullptr;
            }
            //if there is a right child
            else if (ptr->left == nullptr && ptr->right != nullptr) {
                Node* temp = ptr;
                ptr = ptr->right;
                delete temp;
            }
            //if there is a left child
            else if (ptr->left != nullptr && ptr->right == nullptr) {
                Node* temp = ptr;
                ptr = ptr->left;
                delete temp;
            }
        }
    }

当inorder(或任何其他排序方法(递归调用并且左或右节点为空时，该程序似乎会崩溃。该程序并没有跳过该语句，而是一直试图访问左节点，直到它以"读取访问违规"的错误崩溃为止。如果我不调用remove_rec函数，则排序函数按预期工作。对我来说，似乎我在删除节点后没有正确建造树。任何帮助深表感谢！我只包括我认为该函数未调用的代码会导致问题，一切都按预期工作。

Answer 1

您没有修改自己认为自己的指针。线

ptr = nullptr;
ptr = ptr->right;
ptr = ptr->left;

修改本地参数ptr，这是您Node的一个孩子之一的独特 copy 。您需要通过引用通过ptr进行修改以具有任何效果。

您获得"读取访问违规"的原因是由于节点中的指针的 value 仍然与您删除之前的 value 相同，但现在无效，因为您delete D对象。

您还在复制要搜索的数据，这相当低效率。

void remove_rec(const std::string & word, Node *& ptr) {
    if (word < ptr->data && ptr->left != nullptr) {
        remove_rec(word, ptr->left);
    }
    else if (word > ptr->data && ptr->right != nullptr) {
        remove_rec(word, ptr->right);
    }
    else {
        //if the node has no children
        if (ptr->left == nullptr && ptr->right == nullptr) {
            delete(ptr);
            ptr = nullptr;
        }
        //if there is a right child
        else if (ptr->left == nullptr && ptr->right != nullptr) {
            Node* temp = ptr;
            ptr = ptr->right;
            delete temp;
        }
        //if there is a left child
        else if (ptr->left != nullptr && ptr->right == nullptr) {
            Node* temp = ptr;
            ptr = ptr->left;
            delete temp;
        }
        // TODO: handle case when node has both left and right child
    }
}

另外，我将更改Node以使用std::unique_ptr<Node>的left和right。然后，如果您将来犯了类似的错误，就会出现编译时间错误。