Is there a way to assign a templated type to a defined class structure?-CodePudding

I am trying to create a simple binary tree capable of holding data of multiple types. The binary tree will be hard coded with data (compile time could work for this). Here is my code:

class BTree {
  template <typename T>
  struct Node {
    Node* left_ = nullptr;
    Node* right_ = nullptr;

    T data_;

    explicit Node(T value) : data_(value) {}
  };

  Node<int>* root_ = nullptr;

public:
  BTree() {
    root_ = new Node<int>(2);

    auto ptr = root_;
    ptr->left_ = new Node<const char*>("SomeString");
  }
};

I get the error message "Cannot assign to type Node<int>* from Node<const char*>*".

Now, I fully understand what the error message is saying and I know there is no way to convert a char* into an int, but is there a way to have my left_ and right_ pointer members to point at a templated type?

For this project, I cannot include any third-party libraries.

I tried changing them to Node<T>* but it still doesn't work because when the initial root_ node is created, it is created with an int type. I also tried making a custom = operator:

Node<T>& operator=(const Node<const char*>* ptr) {
  left_ = nullptr;
  right_ = nullptr;

  data_ = *ptr->data_;

  return this;
}

This also does not work and at this point I'm a little bit out of my scope.

CodePudding user response：

You can solve the immediate problem of being able to build the tree of pointers by using inheritance.

struct NodeBase
{
    NodeBase* left = nullptr;
    NodeBase* right = nullptr;
};

template <typename T>
struct Node : NodeBase
{
    T data;
    explicit Node(T value) : data(value) {}
};

NodeBase* root = nullptr;

Now you can build the tree and walk through it. But you can't do anything with the values in each node unless you have external knowledge of the type of each one.

CodePudding user response：

I am trying to create a simple binary tree capable of holding data of multiple types.

A single binary search tree normally holds data of one single type. Different unrelated trees may hold data of different types, but each tree should hold one and only one type.

In C this is normally achieved by templatizing the type of the tree (as opposed to just the type of the node).

template <typename T>
class BinarySearchTree {
   struct Node {            // not a template on its own
      T data;
      Node* left;
      Node* right;
   };
   Node* root;
   // the rest of the tree class
};

You should take into account that BinarySearchTree<const char*> won't do what you want. Use BinarySearchTree<std::string> or roll your own simplified string class.

At a later stage you may also want to parameterise the tree with additional template parameters, such as the comparator and the allocator.