为二叉搜索树创建一个统一的搜索函数

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 而不是我分配给它的新节点？

这是 header 如果这可能有帮助

#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() 用于测试）至少对于导致 PO 出现问题的简单测试 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;
}

为二叉搜索树创建一个统一的搜索函数

Creating a unified search function for a binary search tree

c++

search

binary-tree

binary-search-tree