指针数据成员未初始化

Question

我正在尝试实现二叉搜索树类.这是代码(标题):

template <typename Data>
class BST
{
public:
    BST();
    void Insert(Data _item);
    //~BST(); TODO

    struct Node
    {
        Node()
        {m_left = m_right = 0;}

        Data m_data;
        Node* m_left;
        Node* m_right;
    };

    Node* m_root;

private:
    void RecInsert(Node* _root, Data _item);
    Node* CreateNode(Data _item);
};


template <typename Data>
BST<Data>::BST()
: m_root(0)
{
}


template <typename Data>
void BST<Data>::Insert(Data _item)
{
    RecInsert(m_root, _item);
}

template <typename Data>
void BST<Data>::RecInsert(Node* _root, Data _item)
{
    if (NULL == _root)
    {
        _root = CreateNode(_item);
        return;
    }
    if(_item < _root->m_data)
    {
        RecInsert(_root->m_left, _item);
    }
    else
    {
        RecInsert(_root->m_right, _item);
    }
}

template <typename Data>
typename BST<Data>::Node* BST<Data>::CreateNode(Data _item)
{
    Node* newNode = new Node();
    newNode->m_data = _item;
    newNode->m_left = newNode->m_right = 0;
    return newNode;
}

所以基本上我的类保存Node*,它在构造函数中初始化为null,每次插入一个元素时,都会分配一个新节点.但似乎我做错了什么.这是我的测试:

#include <iostream>
#include "bst.h"

using namespace std;
int main()
{
    BST<int> tree;
    tree.Insert(4);
    tree.Insert(11);
    tree.Insert(1);

    cout << tree.m_root->m_data << "\t"; //segmentation fault!!
    cout << tree.m_root->m_left->m_data << "\t";
    cout << tree.m_root->m_right->m_data << "\t";
}

我遇到了分段错误(请参阅代码中的注释以获取位置).在调试时我看到每次调用insert函数时m_root数据成员都是NULL,尽管在第一次插入之后它不应该为null.所以插入内容不正确.

谢谢

Answer 1

在调试时我看到每次调用insert函数时m_root数据成员都是NULL,尽管在第一次插入之后它不应该为null.所以插入内容不正确.

第一个参数RecInsert需要是对a的引用Node*.否则,_root函数中的任何更改都只是本地更改.

宣言

void RecInsert(Node*& _root, Data _item);
               //  ^^^

定义

template <typename Data>
void BST<Data>::RecInsert(Node*& _root, Data _item)
                          //  ^^^
{
   ...
}