试图删除二叉树C++

Question

我试图在C++中删除二叉树,但我遇到的问题是树的大小似乎没有改变.这是我正在使用的尺寸函数:

int BST::size(Node *& cur_root)
{
    if (cur_root == NULL) {
        return 0;
    } else { 
        return(size(cur_root->m_left) + 1 + size(cur_root->m_right));
    }
}

这是我正在尝试使用它的功能:

void BST::deletetree(Node *& cur_root)
{
    cout << "tree size: " << size() << endl;
    if (cur_root!=NULL)
    {
        deletetree(cur_root->m_left);
        deletetree(cur_root->m_right);
        delete cur_root;
        if(cur_root->m_left != NULL) {
            cur_root->m_left = NULL;
        }
        if(cur_root->m_right != NULL) {
            cur_root->m_right = NULL;
        }
        cur_root=NULL;
    }
}

对于三个(1,2,3)的树大小,我的输出是:

tree size: 3
tree size: 3
tree size: 3
tree size: 3
tree size: 3
tree size: 3
tree size: 3

有谁知道为什么我的尺寸不会随着每个删除的节点而下降？

编辑:我删除了if语句,但问题仍然存在

void BST::deletetree(Node *& cur_root)
{
    cout << "tree size: " << size() << endl;
    if (cur_root!=NULL)
    {
        deletetree(cur_root->m_left);
        deletetree(cur_root->m_right);
        delete cur_root;
        cur_root=NULL;
    }
}

编辑2:这是我的完整代码.BST.h:

#ifndef BST_H
#define BST_H

#include <iostream>
using namespace std;

class BST
{
    public:
        BST();
        bool insert(string str) {return insert(str, m_root);}
        int size() {return size(m_root);}
        void deletetree() {return deletetree(m_root);}
    private:
        class Node
        {
            public:
                Node(string value, Node *left = NULL, Node *right = NULL)
                {m_value = value; m_left = left; m_right = right;}
                string m_value;
                Node *m_left;
                Node *m_right;
        };
        Node *m_root;
        bool insert(string str, Node *& cur_root);
        int size(Node *& cur_root);
        void deletetree(Node *& cur_root);
};

#endif

BST.cpp:

#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include <queue> 
#include <math.h> 
#include "bst.h"

BST::BST()
{
    m_root = NULL;
}

bool BST::insert(string str, Node *& cur_root)
{
    /*if (find(str) == true) {
        return false;
    }*/
    if (cur_root == NULL) {
        cur_root = new Node(str);
        return true;
    } else {
        if (cur_root->m_value < str) {
            return insert(str, cur_root->m_right);
        } else {
            return insert(str, cur_root->m_left);
        }
    }
}

int BST::size(Node *& cur_root)
{
    if (cur_root == NULL) {
        return 0;
    } else { 
        return(size(cur_root->m_left) + 1 + size(cur_root->m_right)); 
    }
}

void BST::deletetree(Node *& cur_root)
{
    cout << "tree size: " << size() << endl;
    if (cur_root!=NULL)
    {
        deletetree(cur_root->m_left);
        deletetree(cur_root->m_right);
        delete cur_root;
        cur_root=NULL;
    }
}

main.cpp中:

#include <iostream>
using namespace std;
#include "bst.h"

int main()
{
    BST tree;
    tree.insert("1");
    tree.insert("2");
    tree.insert("3");
    tree.deletetree();
}

忽略插入时的注释部分.当我有一个find函数时,我将在稍后实现这一点.

Answer 1

让我们看看你的deletetree函数中的这些行:

delete cur_root;
if(cur_root->m_left != NULL) {
    cur_root->m_left = NULL;
}
if(cur_root->m_right != NULL) {
    cur_root->m_right = NULL;
}

第一行破坏指向的对象cur_root,其余行取消引用指针以访问现在被破坏的对象.

取消引用指向被破坏对象的指针会导致未定义的行为,这使得所有关于行为的猜测都无用.

对此的简单解决方案是不进行if检查,因为根本不需要它们.你所需要的就是delete cur_root随后的cur_root = nullptr.

现在,当我们看到您的完整代码时,我们可以看到您的插入函数不会创建树.它会创建一个列表(按照您显示的顺序插入数据).

插入时,"1"它将成为树的根.然后,当你插入"2"它成为m_root->m_right.然后,当你插入"3"它成为m_root->m_right->m_right.我没有经历过你的代码走到知道它是否会引起size的deletetree的行为不对,但其中一人做.您应该使用调试器找出哪个函数会导致您的明显问题.

然后,您应该考虑将节点插入树中的顺序.或者,如果您的树应该自我平衡并在插入时重新排序节点.