c++ - 成员指针在函数返回时被覆盖？

Question

我一直在练习我的 C++，因为它从大学开始就有点生疏了，而且我遇到了一个奇怪的问题，我的函数一返回，成员值就被覆盖了。

template <class T>
class BstNode
{
    public:
        T value;
        BstNode<T>* left;
        BstNode<T>* right;
        BstNode<T>* parent;

        BstNode()
        { left = right = parent = NULL; }
        BstNode(T value)
        { this->value=value; left=right=parent=NULL;}
        BstNode(T value, BstNode<T>* parent)
        { this->value=value; this->parent=parent; left=right=NULL;}
};

template <class T>
class BinarySearchTree 
{
    protected:
        BstNode<T>* root;

        void removeNode(BstNode<T>* node);
        void addChild(T value, BstNode<T>* node);
        BstNode<T>* find(T value, BstNode<T>* node);
    public:
        BinarySearchTree()
        { root = NULL; }
        ~BinarySearchTree()
        { removeNode(root); }

        BinarySearchTree<T> insert(T value);
        bool contains(T value);
        BinarySearchTree<T> remove(T value);

        void print();

        BstNode<T>* getRoot() {return root;}

};

template <class T>
BinarySearchTree<T> BinarySearchTree<T>::insert(T value)
{
    if (root == NULL)
    {
        root = new BstNode<T>(value);       
    }
    else
    {
        addChild(value, root);
    }
    cout << "VAL: " << root->value << endl << "LEFT: " << root->left << endl << "RIGHT: "<< root->right << endl << "ADDR: " << root <<endl;
    return *this;
}
template <class T>
void BinarySearchTree<T>::addChild(T value, BstNode<T>* node)
{

    if (value > node->value)
    {
        cout <<"\tgt"<<endl;
        if (node->right == NULL)
        {
            node->right = new BstNode<T>(value, node);
        }
        else
        {
            addChild(value, node->right);
        }
    }
    else
    {
        cout<<"\tlte"<<endl;
        if (node->left == NULL)
        {
            node->left = new BstNode<T>(value, node);
        }
        else
        {
            addChild(value, node->left);
        }
    }
}

// [other member functions]


int main()
{
    BinarySearchTree<int> tree;
    BstNode<int> *n;
    n = tree.getRoot();
    cout << "ADDR: " << n <<endl<<endl;
    tree.insert(5);
    n = tree.getRoot();

    cout << "VAL: " << n->value << endl << "LEFT: " << n->left << endl << "RIGHT: "<< n->right << endl << "ADDR: " << n << endl;
    return 1;
}

我的函数的输出是:

$ ./bst
ADDR: 0

VAL: 5
LEFT: 0
RIGHT: 0
ADDR: 0xa917c8

VAL: 11085080
LEFT: 0xa917a8
RIGHT: 0
ADDR: 0xa917c8

我不明白为什么根节点中的值发生了变化，但指针仍指向同一位置。我唯一能想到的是，根节点是在堆栈上创建的，而不是在堆中分配的，但是 new 不能确保在 C++ 中正确分配内存吗？

Answer 1

我认为问题在于您的插入方法按值返回 BinarySearchTree，但您没有定义复制构造函数。结果，这生成了 BinarySearchTree 的浅表拷贝，返回它，并导致拷贝的析构函数被触发。然后，这将删除存储为根的 BstNode，但由于复制的 BinarySearchTree 与原始树共享 BstNode，因此您正在破坏原始树中的内存。您收到的错误是在您尝试再次访问该节点时访问已释放的内存。

要解决这个问题，要么让插入函数返回对树的引用(因此不进行复制)，要么定义复制构造函数或赋值运算符。理想情况下，两者都做。 :-)

希望这对您有所帮助!