c++ - 如何在 C++ 中删除 BST？

Question

有人可以帮我弄清楚如何正确删除我的 bst 实现吗？我知道这是一个简单的问题，但我尝试了一切。我想避免声明一个动态数组，如果可能的话，让代码保持这个指针结构(没有双关语意)。问题出在析构函数部分。谢谢!

    #include<iostream>
    using namespace std;
    struct Tree{
        struct Tree* left;
        struct Tree* right;
        int val;
        Tree(int);
        ~Tree();
        void Print();
    };
    Tree::Tree(int val){
        this->val = val;
        cout<<"insert l/r for node: "<<this->val<<" , type 0 0 - exit"      <<endl;
int l,r;
cin>>l>>r;
if(l and r){
this->left = new Tree(l);
this->right = new Tree(r);
}else if(l==0 and r==0){
    this->left = NULL;
    this->right = NULL;
    return;
}
    }
    Tree::~Tree(){
        if(this->left == NULL and this->right == NULL){
            delete this;
            return;
        }else{
            this->left->~Tree();
            this->right->~Tree();
        }
    }
    void Tree::Print(){
        if(this == NULL) return;
        cout<<this->val<<endl;
        this->left->Print();
        this->right->Print();
    }
    int main(){
        int n;
        cin>>n;
        Tree* newT = new Tree(n);
        newT->Print();
        newT->~Tree();
        //cout<<newT->val<<endl;
        //newT->Print();


    return 0;
    }

Answer 1

很少需要delete this，在析构函数中它实际上是致命的。调用析构函数是因为有人正在对该对象执行delete。通过在析构函数中执行 delete this，您将获得无限递归。

此外，不要调用 left 和 right 析构函数，而是 delete 它们。 而且当然在main 函数中你也不应该调用析构函数，而应该使用delete。您唯一应该显式调用析构函数的时间是在使用了 placement new 时，您还没有这样做。

还有一些其他缺陷，比如您从不检查 left 或 right 指针是否为 Print 函数中的空指针。

最后，如果 this 是一个空指针，那么你在其他地方有一些严重的问题，所以永远不需要检查它。

---

析构函数应该只是

~Tree()
{
    delete left;
    delete right;
}

如果您随后在 main 函数中执行 delete newT，整个子树将被自动删除。