I'm trying to implement binary search tree in c++. Problem is that I get an error, when I try to implement functions so it can work for structs and ints
This is the haeder file for binary search tree template bst.h
// Forward declaration of Node template
template <typename T>
struct Node;
template <>
struct Node<Car> {
using NodePtr = std::shared_ptr<Node<Car>>; ///< Pointer to a tree node.
Car value;
NodePtr left;
NodePtr right;
Node(const Car& val) : value(val), left(nullptr), right(nullptr) {}
};
template <typename T>
struct Node {
using NodePtr = std::shared_ptr<Node<T>>; ///< Pointer to a tree node.
T value;
NodePtr left;
NodePtr right;
Node(const T& val) : value(val), left(nullptr), right(nullptr) {}
};
/**
* @brief Template class for a binary search tree.
*
* @param T The type of elements stored in the tree.
*/
template <typename T>
class BST {
public:
using ValueType = T; ///< The type of elements stored in the tree.
struct Node;
using NodePtr = std::shared_ptr<Node>; ///< Pointer to a tree node.
/**
* @brief Pointer to the root node of the BST.
*/
NodePtr root;
/**
* @brief Default constructor.
*/
BST() noexcept = default; ///< Default constructor.
/**
* @brief Copy constructor.
*
* @param other The BST to copy.
*/
BST(const BST& other) = delete; ///< Copy constructor.
/**
* @brief Move constructor.
*
* @param other The BST to move.
*/
BST(BST&& other) noexcept = default; ///< Move constructor.
/**
* @brief Destructor.
*/
~BST() = default; ///< Destructor.
template <typename U>
void inorderTraversal(const std::shared_ptr<Node<U>>& node, std::ostream& output) const {
if (node) {
inorderTraversal(node->left, output);
output << node->value.make << " " << node->value.model << " " << node->value.year << " ";
inorderTraversal(node->right, output);
}
}
};
// Explicit instantiation for Car type
template class BST<Car>;
// Explicit instantiation for int type
template class BST<int>;
This is a file with functions defined in header file: bst.cpp
template <typename U>
void BST<U>::inorderTraversal(const std::shared_ptr<Node<U>>& node, std::ostream& output) const {
if (node) {
inorderTraversal(node->left, output);
output << node->value.make << " " << node->value.model << " " << node->value.year << " ";
inorderTraversal(node->right, output);
}
}
template <>
void BST<int>::inorderTraversal(const std::shared_ptr<Node<int>>& node, std::ostream& output) const {
if (node) {
inorderTraversal(node->left, output);
output << node->value << " ";
inorderTraversal(node->right, output);
}
}
template class BST<Car>; // Explicit instantiation for Car type
template class BST<int>; // Explicit instantiation for int type
A file that contains declaration of a struct that I want to implement: struct.cpp
struct Car {
std::string make;
std::string model;
int year;
Car(const std::string& make, const std::string& model, int year) : make(make), model(model), year(year) {}
};
I've tried taking it out of a class, making private, but nothing worked.