lundi 4 septembre 2017

Difficulty inserting nodes to binary search tree using templates and template inheritance

I have spent 3 days trying to find a solution that actually works. What I am dealing with is I have created 3 template classes. I am trying to make a library for binary trees though I have limited knowledge of C++. I have implemented binary trees in C using structs but this time I wanted to take advantage of the object oriented programming C++ offers so I created classes for the node, the binary tree and the binary search tree. I am sorry that I had to post all the code but I feel more comfortable showing all the code in case there is something else wrong that I didn't notice. So here it is. (Note: C++11 in use)

node_class.h

template <typename key_type, typename value_type>
class node_class {
public:
    node_class(key_type key, value_type value) {
        SetKey(key);
        SetValue(value);
        SetLeft(nullptr);
        SetRight(nullptr);
    }
    void SetKey(key_type key) {
        this->key = key;
    }
    void SetValue(value_type value) {
        this->value = value;
    }
    void SetLeft(node_class <key_type, value_type> *left) {
        this->left = left;
    }
    void SetRight(node_class <key_type, value_type> *right) {
        this->right = right;
    }
    key_type GetKey() {
        return this->key;
    }
    value_type GetValue() {
        return this->value;
    }
    node_class <key_type, value_type> *GetLeft() {
        return this->left;
    }
    node_class <key_type, value_type> *GetRight() {
        return this->right;
    }
private:
    key_type key;
    value_type value;
    node_class <key_type, value_type> *left;
    node_class <key_type, value_type> *right;
};

binary_tree_class.h

template <typename key_type, typename value_type>
class binary_tree_class {
public:
    binary_tree_class() {
        SetRoot(nullptr);
    }
    // ...
protected:
    void SetRoot(node_class <key_type, value_type> *root) {
        this->root = root;
    }
    node_class <key_type, value_type> *GetRoot() {
        return this->root;
    }
private:
    node_class <key_type, value_type> *root;
    // ...
};

binary_search_tree_class.h

template <typename key_type, typename value_type>
class binary_search_tree_class : public binary_tree_class <key_type, value_type> {
public:
    binary_search_tree_class() {

    }
    void Insert(key_type key, value_type value) {
        Insert(key, value, this->GetRoot());
    }
    void Insert(key_type key, value_type value, node_class <key_type, value_type> *node) {
        if (node == nullptr) {
            node = new node_class <key_type, value_type> (key, value);
        }
        if (key > node->GetKey()) {
            Insert(key, value, node->GetRight());
        } else if (key < node->GetKey()) {
            Insert(key, value, node->GetLeft());
        }
    }
    // ...
};

As far as the Insert function is conserned, I read that I have to pass the node parameter by reference to pointer in order for the changes to the tree to take place (Correct me if I am wrong). That being said I have to change the function protorype from this

void Insert(key_type key, value_type value, node_class <key_type, value_type> *node)

into this

void Insert(key_type key, value_type value, node_class <key_type, value_type> *&node)

After i did that i was completely unable to figure out what is wrong so i am still stuck with the following error from g++

In file included from main.cpp:1:0:
binary_search_tree_class.h: In instantiation of ‘void binary_search_tree_class<key_type, value_type>::Insert(key_type, value_type) [with key_type = int; value_type = int]’:
main.cpp:5:31:   required from here
binary_search_tree_class.h:11:9: error: invalid initialization of non-const reference of type ‘node_class<int, int>*&’ from an rvalue of type ‘node_class<int, int>*’
   Insert(key, value, this->GetRoot());
         ^
binary_search_tree_class.h:13:7: note:   initializing argument 3 of ‘void binary_search_tree_class<key_type, value_type>::Insert(key_type, value_type, node_class<key_type, value_type>*&) [with key_type = int; value_type = int]’
  void Insert(key_type key, value_type value, node_class <key_type, value_type> *&node) {

In the files above i couldn't write the include directories because the # symbol was causing problems with the indentation but I think you get it.

Any help will be considerably usefull. Thanks for your time.

Aucun commentaire:

Enregistrer un commentaire