Dzień dobry. Na podstawie drzewa BST postanowiłem stworzyć implementację zbioru. Problem polega na tym, że metoda pomocnicza (copyTree()
) operatora kopiującego powoduje naruszenie ochrony pamięci. Szukałem przyczyny i dotarłem do tego, że pomimo prawidłowego zakończenia metody dla liści, wykonywany jest w pewnym momencie krok dalej. Co ciekawe, ta sama metoda wywołana dla drzewa (zarówno w konstruktorze, jak i w operatorze) działa prawidłowo. Mógłby mi ktoś pomóc, wyjaśnić w czym może tkwić problem?
gdb zwraca coś takiego:
7
kolejny krok: 0x55555556ae70
kolejny krok: 0x55555556aef0
kolejny krok: 0x55555556af30
kolejny krok: 0 nullptr
kolejny krok: 0 nullptr
kolejny krok: 0x55555556af10
kolejny krok: 0 nullptr
kolejny krok: 0 nullptr
kolejny krok: 0x55555556ae90
kolejny krok: 0x55555556aed0
kolejny krok: 0 nullptr
kolejny krok: 0 nullptr
kolejny krok: 0x55555556aeb0
kolejny krok: 0 nullptr
kolejny krok: 0 nullptr
kolejny krok: 0xffffffffffffff90Program received signal SIGSEGV, Segmentation fault.
0x00005555555559fe in BST<int>::copyTree (this=0x7fffffffdda0, copyTo=@0x7fffffffddb0: 0x55555556af30, copyFrom=0xffffffffffffff90) at bst.hpp:71
71 copyTo->key=copyFrom->key;
Kod mojego programu wygląda następująco:
bst.hpp
#ifndef BST_HPP
#define BST_HPP
#include <iostream>
#include <cstddef>
template <typename E>
class BST {
protected:
struct node
{
E key; //klucz
node* right; //prawe dziecko
node* left; //lewe dziecko
};
protected:
node* root; //korzeń
size_t numberOfNodes; //liczba elementów drzewa
void copyTree(node*& copyTo, const node* copyFrom);
public:
BST(); //konstruktor
BST(const BST<E>& source); //konstruktor (nie)kopiujący
node* getMin() const;
node* getMax() const;
node* insert(E x);
bool remove(E x);
node* find(E x) const;
size_t size() const;
void inOrder(node* e) const;
void preOrder(node* e) const;
void postOrder(node* e) const;
node* getTreeRoot() const;
BST<E>& operator=(const BST<E>& source);
};
/*----------------------------------------------------------------------------------*/
template <typename E>
BST<E>::BST() : root(nullptr), numberOfNodes(0) {
}
template <typename E>
BST<E>::BST(const BST<E>& source) : root(nullptr), numberOfNodes(source.numberOfNodes) {
copyTree(root, source.root);
}
template <typename E>
void BST<E>::copyTree(node*& copyTo, const node* copyFrom) {
std::cout<<"kolejny krok: ";
std::cout<<copyFrom<<" ";
if(copyFrom==nullptr) {
std::cout<<"nullptr"<<std::endl;
copyTo=nullptr;
return;
}
//std::cout<<copyFrom->key<<" "<<copyFrom->left<<" "<<copyFrom->right<<std::endl;
copyTo=new node;
/*std::cout<<"value: "<<std::endl;
std::cout<<copyFrom->key<<" "<<copyFrom<<" "<<copyFrom->left<<" "<<copyFrom->right;*/
std::cout<<std::endl;
copyTo->key=copyFrom->key;
copyTree(copyTo->right, copyFrom->right);
copyTree(copyTo->left, copyFrom->left);
}
template <typename E>
BST<E>& BST<E>::operator=(const BST<E>& source) {
if(&source==this) {
return *this;
}
this->numberOfNodes=source.numberOfNodes;
std::cout<<"tree c-op="<<std::endl;
copyTree(root, source.root);
return *this;
}
template<typename E>
typename BST<E>::node* BST<E>::getMax() const {
node* temp=root;
if(temp==nullptr) {
return nullptr;
}
while(temp->right!=nullptr) {
temp=temp->right;
}
return temp;
}
template <typename E>
typename BST<E>::node* BST<E>::getMin() const {
node* temp=root;
if(temp==nullptr) {
return nullptr;
}
while(temp->left!=nullptr) {
temp=temp->left;
}
return temp;
}
template <typename E>
typename BST<E>::node* BST<E>::insert(E x) {
node* current=root;
node* previous=nullptr;
while(current!=nullptr) {
previous=current;
if(x < current->key) {
current=current->left;
}
else {
current=current->right;
}
}
node* nEl=new node;
nEl->right=nullptr;
nEl->left=nullptr;
nEl->key=x;
if(previous!=nullptr) {
if(x < previous->key) {
previous->left=nEl;
}
else {
previous->right=nEl;
}
}
else {
root=nEl;
}
++numberOfNodes;
return nEl;
}
template <typename E>
bool BST<E>::remove(E x) {
auto temp=root;
node* parent=nullptr;
while(temp!=nullptr && temp->key!=x) {
parent=temp;
if(x < temp->key) {
temp=temp->left;
}
else {
temp=temp->right;
}
}
if(temp==nullptr) {
return false;
}
auto toRemove=temp;
if(temp->right==nullptr) {
if(parent!=nullptr) {
if(parent->left==temp) {
parent->left=temp->left;
}
else {
parent->right=temp->left;
}
}
else {
root=temp->left;
}
}
else if(temp->left==nullptr) {
if(parent!=nullptr) {
if(parent->left==temp) {
parent->left=temp->right;
}
else {
parent->right=temp->right;
}
}
else {
root=temp->right;
}
}
else {
auto e=temp->left;
parent=temp;
if(e->right==nullptr) {
temp->key=e->key;
parent->left=e->left;
}
else {
while(e->right!=nullptr) {
parent=e;
e=e->right;
}
temp->key=e->key;
parent->right=e->left;
}
toRemove=e;
}
delete toRemove;
--numberOfNodes;
return true;
}
template <typename E>
typename BST<E>::node* BST<E>::find(E x) const {
auto temp=root;
while(temp!=nullptr && temp->key!=x) {
if(x < temp->key) {
temp=temp->left;
}
else {
temp=temp->right;
}
}
return temp;
}
template <typename E>
size_t BST<E>::size() const {
return numberOfNodes;
}
template <typename E>
void BST<E>::inOrder(node* e) const {
if(e==nullptr) {
return;
}
inOrder(e->left);
std::cout<<e->key<<" ";
inOrder(e->right);
}
template <typename E>
void BST<E>::postOrder(node* e) const {
if(e==nullptr) {
return;
}
postOrder(e->left);
postOrder(e->right);
std::cout<<e->key<<" ";
}
template <typename E>
void BST<E>::preOrder(node* e) const {
if(e==nullptr) {
return;
}
std::cout<<e->key<<" ";
preOrder(e->left);
preOrder(e->right);
}
template <typename E>
typename BST<E>::node* BST<E>::getTreeRoot() const {
return root;
}
#endif //BST_HPP
set.hpp:
#ifndef SET_HPP
#define SET_HPP
#include "bst.hpp"
//#include <stack>
template <typename E>
class Set : public BST<E> {
typename BST<E>::node* root;
size_t numberOfNodes;
public:
Set();
Set(const Set<E>& source);
typename BST<E>::node* find(E x) const;
typename BST<E>::node* insert(E x);
void inOrder(typename BST<E>::node* e) const;
bool remove(E x);
typename BST<E>::node* getTreeRoot() const;
Set<E>& operator=(const Set<E>& source);
};
template <typename E>
Set<E>::Set() : BST<E>() {
}
template <typename E>
Set<E>::Set(const Set<E>& source) : BST<E>(source) {
}
template <typename E>
typename BST<E>::node* Set<E>::insert(E x) {
if(find(x)!=nullptr) { //znaleziono taki element
return nullptr;
}
return BST<E>::insert(x);
}
template <typename E>
typename BST<E>::node* Set<E>::find(E x) const {
return BST<E>::find(x);
}
template <typename E>
void Set<E>::inOrder(typename BST<E>::node* e) const {
return BST<E>::inOrder(e);
}
template <typename E>
typename BST<E>::node* Set<E>::getTreeRoot() const {
return BST<E>::getTreeRoot();
}
template <typename E>
bool Set<E>::remove(E x) {
return BST<E>::remove(x);
}
template <typename E>
Set<E>& Set<E>::operator=(const Set<E>& source) {
if(&source==this) {
return *this;
}
this->numberOfNodes=source.numberOfNodes;
BST<E>::copyTree(root, source.root);
std::cout<<"skopiowane"<<std::endl;
return *this;
}
#endif //SET_HPP
test4.cpp:
#include "set.hpp"
int main() {
Set<int> tree;
tree.insert(8);
tree.insert(2);
tree.insert(1);
tree.insert(3);
tree.insert(10);
tree.insert(9);
tree.insert(11);
tree.insert(11);
std::cout<<tree.size()<<std::endl;
/*tree.inOrder(tree.getTreeRoot());
std::cout<<std::endl;*/
auto tree2=tree;
/*tree.inOrder(tree.getTreeRoot());
std::cout<<std::endl;*/
tree.remove(2);
tree.remove(2);
tree.remove(11);
Set<int> tree3;
tree3=tree;
tree.inOrder(tree.getTreeRoot());
std::cout<<std::endl;
tree2.inOrder(tree2.getTreeRoot());
std::cout<<std::endl;
//std::cout<<tree2.getTreeRoot()->key<<std::endl;
//std::cout<<tree.size()<<std::endl;
std::cout<<tree.size()<<std::endl;
std::cout<<tree2.size()<<std::endl;
std::cout<<tree3.size()<<std::endl;
}