Указатель пользователя, который перезаписывается при возврате функции?

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

Я думаю, проблема заключается в том, что ваш метод insert возвращает значение BinarySearchTree по значению, но у вас нет определенного конструктора копий. В результате это делает мелкую копию BinarySearchTree, возвращает ее и вызывает уничтожение деструктора копии. Затем он удаляет BstNode, хранящийся в качестве корня, но поскольку скопированный BinarySearchTree разделяет BstNodes с исходным деревом, вы уничтожаете память в исходном дереве. Ошибка при получении доступа к освобожденной памяти при повторном доступе к узлу.

Чтобы исправить это, либо функция вставки возвращает ссылку на дерево (так что копия не создается), либо определить конструктор копирования или оператор присваивания. В идеале, сделайте обоим. :-)

Надеюсь, это поможет!