Создание единой функции поиска для бинарного дерева поиска

Question

Я пытаюсь создать функцию поиска в бинарном дереве поиска, которая может использоваться как функциями вставки, так и функциями поиска.

Я попытался передать курсор в качестве ссылки

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);
    }
}

Вот функция вставки, которую я пытаюсь использовать в

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;
    }
}

Вот функция поиска, которую я пытаюсь использовать в

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;
}

.ссылка или возврат в качестве значения сработали

Я не понимаю, почему при запуске этого кода указатель start всегда равен NULL при вставке нового значения в двоичное дерево поиска.

Я также попытался переписать код с помощью функции internal_search, возвращающей указатель узла, но это тоже не сработало.

Почему start указывает на NULL каждый раз вместо нового узла Iприсвоить его?

вот заголовок, если это может помочь

#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();
};

Answer 1

После некоторых тривиальных изменений (в том числе связанных с комментарием @ Scheff) я скомпилировал его.

Однако, start фактически всегда был равен NULL. Я обнаружил, что проблема была в том, что ìnternal_search всегда возвращал NULL, т.е. значение узла * перед созданием узла, а не адрес узла *, где следует создать новый узел. Поэтому необходимо было заменить (node* &) на (node** &).

Вот код, который, кажется, работает (с main() для теста) по крайней мере для простого теста search, который вызывал проблемы с ПО. Некоторая работа должна быть сделана, чтобы улучшить (например, рекурсивный insert) и завершить код (например, чтобы удалить объект binary_tree), но это выходит за рамки вопроса (к счастью!).

#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;
}