c++ - 为二叉搜索树创建统一搜索函数

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

如果这可能有帮助，这是标题

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

标签： c++searchbinary-treebinary-search-tree

Answer 1

经过一些微不足道的修改（包括与@Scheff 的评论相关的修改），我编译了它。

但是，start实际上总是等于 NULL。我发现问题在于它ìnternal_search总是返回 NULL，即在创建节点之前 node* 的值，而不是 node* 在哪里创建新节点的地址。因此，需要将其替换(node* &)为(node** &)。

这是似乎有效的代码（带有main()测试），至少对于search导致 PO 出现问题的简单测试。必须做一些工作来改进（例如递归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;
}