二叉搜索树的删除方法删除所有节点而不是只删除选定的一个C++

Question

我在取消二叉搜索树中的节点时遇到问题。我实现的消除树节点的方法会消除所有节点，我不明白为什么。 这是 Node 类：

#include <iostream>

using namespace std;

template <class T>
class Nodo {
private:
    T val;
    Nodo<T> *sx;
    Nodo<T> *dx;
    Nodo<T> *padre;
public:
    explicit Nodo(T x) {
        this->val = x;
    }
    void setVal(T y) {
        this->val = y;
    }
    T getVal() {return this->val;}

    void setPadre(Nodo<T> *x) {
        this->padre = x;
    }

    Nodo<T> *getPadre() {
        return this->padre;
    }

    void setSx(Nodo<T> *n) {
        this->sx = n;
    }

    void setDx(Nodo<T> *n) {
        this->dx = n;
    }

    Nodo *getSx() {return this->sx;}
    Nodo *getDx() {return this->dx;}
};

有包含所有方法的 BST 类：

template <typename T>
class BinarySearchTree {
private:
    Nodo<T> *radice;
public:
    BinarySearchTree() {
        radice = nullptr;
    }
    void insert(T x) {
        Nodo<T>* tmp = new Nodo<T>(x);
        Nodo<T> *supp = nullptr;
        Nodo<T> *radix = radice;
        tmp->setSx(nullptr);
        tmp->setDx(nullptr);

        while (radix != nullptr) {
            supp = radix;
            if (x < radix->getVal()) {
                radix = radix->getSx();
            } else {
                radix = radix->getDx();
            }
        }
        tmp->setPadre(supp);
        if (supp == nullptr) {
            radice = tmp;
        } else if(x < supp->getVal()) {
            supp->setSx(tmp);
        } else {
            supp->setDx(tmp);
        }
    }

    void _inorder(Nodo<T> *prova) {
        if (prova != nullptr) {
            _inorder(prova->getSx());
            cout << prova->getVal() << " ";
            _inorder(prova->getDx());
        }
    }

    void inorder() {
        _inorder(radice);
        cout << "----" << endl;
    }

    Nodo<T> *minimum(Nodo<T>* x) {
        Nodo<T> *min = x;
        while (min->getSx() != nullptr)
            min = min->getSx();
        return min;
    }

    Nodo<T> *search(T x) {
        Nodo<T> *iter = radice;
        if (x < iter->getVal()) {
            while (iter->getVal() != x)
                iter = iter->getSx();
            return iter;
        } else {
            while (iter->getVal() != x)
                iter = iter->getDx();
            return iter;
        }
    }
    
    void transplant(Nodo<T> *u, Nodo<T> *v) {
        if (u->getPadre() == nullptr) {
            radice = v;
        } else if (u == u->getPadre()->getSx()) {
            u->getPadre()->setSx(v);
        } else {
            u->getPadre()->setDx(v);
        }
        if (v != nullptr)
            v->setPadre(u->getPadre());
    }


    void delTree(T x) {
        Nodo<T> *tmp = search(x);
        Nodo<T> *supp = nullptr;
        if (tmp->getSx() == nullptr)
            transplant(tmp, tmp->getDx());
        else if (tmp->getDx() == nullptr)
            transplant(tmp, tmp->getSx());
        else {
            supp = minimum(tmp->getDx());
            if (supp->getPadre() != tmp) {
                transplant(supp, supp->getDx());
                supp->setDx(tmp->getDx());
                supp->getDx()->setPadre(supp) ;
            }
            transplant(tmp, supp);
            supp->setSx(tmp->getSx());
            supp->getSx()->setPadre(supp);
        }
    }
};


int main() {
    BinarySearchTree<int> bst;
    bst.insert(30);
    bst.insert(10);
    bst.insert(50);
    bst.insert(2);
    bst.inorder();
    bst.delTree(2);
    bst.inorder();
}

现在，当我对任何节点调用 delTree 方法时，它会消除所有节点。谁能帮我理解代码中的错误在哪里？谢谢！

编辑：我在 BST 类中添加了

search()

方法，并修改了

delTree()

方法中的 tmp 分配，现在它工作正常！

Answer 1

经过您所做的编辑，您的函数

delTree

看起来不错。然而，当我运行以下示例时，函数

search

出现问题，导致它崩溃。

void example() {
    BinarySearchTree<int> bst;
    bst.insert(0);
    bst.insert(2);
    bst.insert(1);
    bst.insert(3);
    bst.inorder();
    bst.delTree(1);
    bst.inorder();
    bst.delTree(100);
    bst.inorder();
}

StackOverflow.exe 中的 0x00007FF733062C47 处抛出异常：0xC0000005：读取位置 0x0000000000000000 时发生访问冲突。

在搜索例程的第二个循环中执行时抛出异常。

Nodo<T>* search(T x) {
    Nodo<T>* iter = radice;
    if (x < iter->getVal()) {
        while (iter->getVal() != x)
            iter = iter->getSx();
        return iter;
    }
    else {
        while (iter->getVal() != x)
            iter = iter->getDx();  // <--------------- Access violation
        return iter;
    }
}

显然，变量

iter

的值为

nullptr

，然后被取消引用。

查看代码你就可以知道发生了什么。该循环沿着树的右侧向下延伸，寻找

x

，当找不到它时，

iter

得到

nullptr

。

这就是另一个问题。当

x

位于树的左半部分时，

search

仅检查每个节点的左子节点。同样，当

x

位于树的右半部分时，

search

只扫描右子节点。

您可以通过使用递归搜索来解决这两个问题。

Nodo<T>* search(T const x)
{
    // Search the tree for a node with the value `x`.
    // If found, return a pointer to the node.
    // If `x` is not in the tree, return `nullptr`.
    return search(x, radice);
}
Nodo<T>* search(T const x, Nodo<T>* const ptr)
{
    if (!ptr) return nullptr;
    if (x == ptr->getVal()) return ptr;
    if (x < ptr->getVal()) return search(x, ptr->getSx());
    return search(x, ptr->getDx());
}

当函数

search

失败时，因为

x

不在树中，所以它返回

nullptr

。您需要在函数顶部检查这一点

delTree

。

void delTree(T x) {
    Nodo<T>* tmp = search(x);
    if (tmp == nullptr) return;
    //...
}