Wsrtjtyk

I'm trying to create a search function in a binary search tree that can be used by both the insert and search functions.

I tried passing my cursor as a reference

template<class key_type, class data_type>

bool binary_tree<key_type, data_type>::internal_search(node *& cursor, key_type query) {

    if (cursor == NULL) {

        return false;

    }else if (cursor->key == query) {

        return true;

    }

    if (cursor->key < query) {

        internal_search(cursor->left, query);

    }

    else {

        internal_search(cursor->right, query);

    }

}

Here is the insert function I'm trying to use it in

template<class key_type, class data_type>

void binary_tree<key_type, data_type>::insert(key_type key_in, data_type data_in) {

    node * local_cursor = start;

    if (!internal_search(local_cursor, key_in)) {

        local_cursor = new node;

        local_cursor->key = key_in;

        local_cursor->data = data_in;

        local_cursor->left = NULL;

        local_cursor->right = NULL;

        size++;

    }

    else {

        std::cout << "entry already present" << std::endl;

    }

}

Here is the search function I'm trying to use it in

template<class key_type, class data_type>

data_type binary_tree<key_type, data_type>::search(key_type query) {

    node * local_cursor = start;

    if (internal_search(local_cursor, query)) {

        return local_cursor->data;

    }

    std::cout << "search query not found" << std::endl;

}

Neither passing through as a reference or returning as a value have worked

I don't understand why when I run this code the start pointer is always NULL when inserting a new value into the binary search tree.

I also tried rewriting the code with the internal_search function returning a node pointer but that didn't work either.

Why does start point to NULL everytime instead of the new node I assigned it to?

here's the header if that might help

#pragma once



template <class key_type, class data_type>

class binary_tree

{

private:

    struct node {

        key_type key;

        data_type data;

        node * left;

        node * right;

    };

    node * start;

    int size;



    bool internal_search(node *, key_type);



    void print_preorder(node * cursor = start);

    void file_preorder( std::ofstream&, node *);



    void file_inorder(std::ofstream&, node *);

    void print_inorder_pri(node *);



    void print_postorder(node *);

    void file_postorder(std::ofstream&, node *);



public:

    binary_tree();

    void insert(key_type);

    void remove();

    bool is_empty();

    data_type search(key_type);

    void print_preorder();

    void file_preorder(std::ofstream&);

    void print_inorder();

    void file_inorder(std::ofstream&);

    void print_postorder();

    void file_postorder(std::ofstream&);

    void print_level();

    bool load_file(std::string);

    void save_file(std::string);

    ~binary_tree();

};

After some trivial modifications (including the one related to @Scheff's comment), I got it compiled.

However, start was effectively always equal to NULL.
I discovered that the problem was that ìnternal_search was always returning NULL, i.e.
the value of the node* before node creation and not the address of node* where to create the new node. Therefore, it was needed to replace (node* &) by (node** &).

Here is the code that seems to work, (with a main() for test) at least for the simple test searchthat was causing problem to the PO. Some work must be done to improve (e.g. a recursive insert) and complete the code (e.g. to delete the object binary_tree) but this is out of the scope of the question (fortunately!).

#include    <iostream>



template <class key_type, class data_type>

class binary_tree

{

private:

    struct node {

    key_type key;

    data_type data;

    node* left = NULL;

    node* right = NULL;

    };

    node* start = NULL;

    int size = 0;



    bool internal_search(node** &cursor, key_type);



    //void print_preorder(node * cursor = start);

    //void file_preorder( std::ofstream&, node *);



    void file_inorder(std::ofstream&, node *);

    void print_inorder_pri(node *);



    void print_postorder(node *);

    void file_postorder(std::ofstream&, node *);



public:

    binary_tree() {};

    void insert(key_type, data_type);

    void remove();

    bool is_empty();

    data_type search(key_type);

    //void print_preorder();

    void file_preorder(std::ofstream&);

    void print_inorder();

    void file_inorder(std::ofstream&);

    void print_postorder();

    void file_postorder(std::ofstream&);

    void print_level();

    bool load_file(std::string);

    void save_file(std::string);



    void print_start () {std::cout << start << "n";}   // Added



    //~binary_tree();

};



template<class key_type, class data_type>

bool binary_tree<key_type, data_type>::internal_search (node** &cursor, key_type query) {

    if (*cursor == NULL) {

        return false;

     } else if ((*cursor)->key == query) {

        return true;

    }

    if ((*cursor)->key < query) {

        cursor = &((*cursor)->left);

        return internal_search(cursor, query);

    } else {

        cursor = &((*cursor)->right);

        return internal_search(cursor, query);

    }

}



template<class key_type, class data_type>

void binary_tree<key_type, data_type>::insert(key_type key_in, data_type data_in) {

    node** local_cursor = &start;

    if (!internal_search(local_cursor, key_in)) {

        *local_cursor = new node;

        (*local_cursor)->key = key_in;

        (*local_cursor)->data = data_in;

        size++;

    }

    else {

        std::cout << "entry already present" << std::endl;

    }

}



template<class key_type, class data_type>

data_type binary_tree<key_type, data_type>::search(key_type query) {

    node** local_cursor = &start;

    if (internal_search(local_cursor, query)) {

        return (*local_cursor)->data;

    }

    std::cout << "search query not found" << std::endl;

    return 0;

}



int main() {

    binary_tree<int,int> tree;

    tree.insert (0,0);

    tree.insert (2,3);

    tree.insert (-2,3);

    tree.insert (-1,-1);

    std::cout << "start = ";

    tree.print_start();



    std::cout << tree.search(2) << "n";

    return 0;

}