通过类方法初始化后，指针类成员保持为NULL

Question

我试图实现二叉查找树数据结构。我遇到了使用二叉搜索树类的insert/insert_helper方法初始化我的树的问题。

使用GDB，我可以看到根数据成员在第一次调用insert方法时没有初始化。我无法弄清楚为什么，因为我期望，因为我通过指向insert_helper方法的指针，我应该能够在方法本身内初始化那个指针。实质上，为什么在第一次调用insert_helper时将root指针传递给root成员可以不正确地初始化类root成员？ C++有哪些规则不允许这样做？

任何帮助或建议将是有用的。以下是相关的代码片段。

#ifndef BST_H_ 
#define BST_H_ 

#include <vector> 
#include <iostream> 
#include <exception> 

template <typename T> 
class Bin_Search_Tree { 
private: 
    typedef T value_type; 
    typedef T& reference; 
    typedef const T& const_reference; 
    typedef std::size_t size_type; 
    struct Node { 
    value_type data; 
    Node* left; 
    Node* right; 
    Node* parent; 
    }; 
    Node* root; 

    void free_tree(Node* rnode); 
    size_type size_helper(const Node* rnode) const; 
    Node* find_helper(const Node* rnode, const value_type& val) const; 
    void print_tree_helper(const Node* rnode) const; 
    bool insert_helper(Node* parent, Node* rnode, const value_type& val); 
    bool remove_helper(Node* rnode, const value_type& val); 
    Node* create_node(Node* parent, const value_type& val) const; 
    Node* get_min(const Node* rnode) const; 

public: 
    Bin_Search_Tree() : root(nullptr) { } 
    Bin_Search_Tree(const std::vector<value_type>& vals); 
    ~Bin_Search_Tree() { free_tree(root); } 

    bool empty() const { return (nullptr == root); } 
    size_type size() const { return size_helper(root); } 
    Node* find(const value_type& val) { return find_helper(root, val); } 
    bool insert(const value_type& val) { insert_helper(nullptr, root, val); } 
    bool remove(const value_type& val); 
    void print_tree() const { print_tree_helper(root); } 
}; 

template <typename T> 
bool Bin_Search_Tree<T>::insert_helper(Node* parent, Node* rnode, const value_type& val) { 
    if (nullptr == rnode) { 
    rnode = create_node(parent, val); 
    return true; 
    } else if (val == rnode->data) { 
    return false; 
    } else if (rnode->data < val) { 
    return insert_helper(rnode, rnode->right, val); 
    } else { 
    return insert_helper(rnode, rnode->left, val); 
    } 
} 

template <typename T> 
typename Bin_Search_Tree<T>::Node* Bin_Search_Tree<T>::create_node(Node* parent, const value_type& val) const { 
    Node* inode = new Node; 

    if (nullptr == inode) { 
    throw std::bad_alloc(); 
    } 
    inode->data = val; 
    inode->left = nullptr; 
    inode->right = nullptr; 
    inode->parent = parent; 
    return inode; 
} 

Answer 1

在功能

template <typename T> 
bool Bin_Search_Tree<T>::insert_helper(Node* parent, Node* rnode, const value_type& val) { 
    if (nullptr == rnode) { 
    rnode = create_node(parent, val); 
    return true; 
    } else if (val == rnode->data) { 
    return false; 
    } else if (rnode->data < val) { 
    return insert_helper(rnode, rnode->right, val); 
    } else { 
    return insert_helper(rnode, rnode->left, val); 
    } 
} 

最初，root=nullptr，所以第一个if条件得到满足。然后，使用

rnode = create_node(parent, val); 

创建一个新节点并返回。但是，rnode对于按值传递根的函数来说是本地的。当你返回时，指针被销毁，你不能再访问你分配的内存。此外，你从来没有做任何改变，因为它指向root，所以它仍然是nullptr。

通过使用这是类的成员函数这一事实，您可以简单地做到这一点 - root成员对函数可见。所以，你不需要把它作为一个参数来传递。它可以直接在函数内部使用，这应该可以解决问题。