1

Я занимаюсь своим 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++?

+0

Можете ли вы опубликовать код fore 'addChild'? Проблема, кажется, там – JaredPar

+0

В вашем примере код выводит только VAL. Откуда вы получаете второй выход VAL? – HighCommander4

+0

Один приходит из основного, а один из вставки – Kristofer

ответ

3

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

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

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

+0

Ничего себе, не видел этого, но да, добавив, что «мертвый Jim' cout для деструктора показывает, что он запущен, мы не получаем ошибку, потому что нам не хватает реализации' removeNode' и, следовательно, освободить любую память. –

+0

Так оно и было, спасибо! Я возвращал '* this', поэтому я мог объединить вставки вставки - tree.insert (5) .insert (10) .insert (-3) и т. Д. - как я был обучен делать на Java и C#. Я думаю, в C++ я должен использовать разыменование '->' вместо точки, чтобы выполнить одно и то же? –

+1

@ AndrewRueckert- В C++ вы должны вернуть функцию BinarySearchTree & (ссылку на объект) вместо BinarySearchTree (копия объекта). Трюк Java и C# все еще работает здесь, но вам нужно явно указать, что вы вернете ссылку. В Java и C# все объекты передаются по ссылке, но в C++ значение pass-by-value является значением по умолчанию. – templatetypedef