Dobry wieczór. Napisałem implementację wskaźnikową drzewa BST. Teraz staram się na jej podstawie stworzyć klasę szablonową, by drzewo mogło przechowywać różne typy danych. Problem w tym, że próba kompilacji kończy się zwróceniem tytułowego błędu. Zaobserwowałem, że kompilator zawsze wskazuje na te same linie, nawet gdy gdzieś wcześniej w kodzie wstawię kilka pustych. Proszę o pomoc w znalezieniu przyczyny błędu.
Kompilator zwraca dokładnie to:
bst.hpp: In instantiation of ‘node<E>* BST<E>::insert(element<E>) [with E = int; BSTNode<E> = node<int>*; element<E> = int]’:
test2.cpp18: required from here
bst.hpp25: error: ‘struct node<int>’ has no member named ‘value’^
bst.hpp10: error: ‘struct node<int>’ has no member named ‘value’
}
~ ^
bst.hpp26: error: ‘struct node<int>’ has no member named ‘value’
}
^
bst.hpp: In instantiation of ‘bool BST<E>::remove(element<E>) [with E = int; element<E> = int]’:
test2.cpp18: required from here
bst.hpp34: error: ‘struct node<int>’ has no member named ‘value’
nEl->key=x;
^
bst.hpp22: error: ‘struct node<int>’ has no member named ‘value’
if(x < previous->key) {
~~~~~~^~~~~
bst.hpp19: error: ‘struct node<int>’ has no member named ‘value’
}
~ ^
bst.hpp28: error: ‘struct node<int>’ has no member named ‘value’
}
^
bst.hpp19: error: ‘struct node<int>’ has no member named ‘value’
parent->left=temp->right;
~~^~~~~
bst.hpp28: error: ‘struct node<int>’ has no member named ‘value’
parent->left=temp->right;
~~~^~~~~
Kod programu:
bst.hpp:
#ifndef BST_HPP
#define BST_HPP
#include <iostream>
#include <cstddef>
template <typename E>
class BST {
struct node
{
E key; //klucz
node* right; //prawe dziecko
node* left; //lewe dziecko
};
node* root; //korzeń
size_t numberOfNodes; //liczba elementów drzewa
void copyTree(node* copyTo, node* copyFrom);
public:
BST();
BST(const BST<E>& source);
node* getMin() const;
node* getMax() const;
node* insert(E x);
//E remove(E x);
bool remove(E x);
//const node* find(E x) const;
node* find(E x) const;
size_t size() const;
void inOrder(node* e) const;
void preOrder(node* e) const;
void postOrder(node* e) const;
const node* getTreeRoot() const;
//void copyTree(node* copyTo, node* copyFrom);
};
/*----------------------------------------------------------------------------------*/
template <typename E>
BST<E>::BST() {
root=nullptr;
numberOfNodes=0;
}
template <typename E>
BST<E>::BST(const BST<E>& source) {
copyTree(root, source.root);
}
template <typename E>
void BST<E>::copyTree(node* copyTo, node* copyFrom) {
if(copyFrom==nullptr) {
copyTo=nullptr;
return;
}
copyTo=new node;
copyTo->key=copyFrom->key;
copyTree(copyTo->right, copyFrom->right);
copyTree(copyTo->left, copyTo->left);
}
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>
const node* BST<E>::find(E x) const {
auto temp=find(x);
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>
const typename BST<E>::node* BST<E>::getTreeRoot() const {
return root;
}
#endif //BST_HPP
test.cpp:
#include "bst.hpp"
int main() {
//BST<int> bst1;
//tu część testowa, ale była godzina 2;22, więc mi się nie chciało...
BST<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);
auto tree2=tree;
/*tree.inOrder(tree.getTreeRoot());
std::cout<<std::endl;*/
tree.remove(2);
tree.remove(2);
tree.remove(11);
//BST<int> tree3;
//tree3=tree;
/*tree.inOrder(tree.getTreeRoot());
std::cout<<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;
return 0;
}