CODEWITHSUNDEEP
c++pointers
Hana
Hana

Reputation: 39

pointer data member not initialized

I am trying to implement a binary search tree class. This is the code (header):

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

So basically my class holds Node* which initialized to null in the constructors and each time I insert an element, a new node is allocated. But it seems like I am doing something wrong. This is my test:

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

I get a segmentation fault (see comment in the code for location). While debugging I see that each time I call the insert function the m_root data member is NULL, although after the the first insert it is not supposed to be null. so something in my insert is not correct.

Thanks

Upvotes: 1

Views: 53

Answers (1)

R Sahu
R Sahu

Reputation: 206577

While debugging I see that each time I call the insert function the m_root data member is NULL, although after the the first insert it is not supposed to be null. so something in my insert is not correct.

The first argument of RecInsert needs to be a reference to a Node*. Otherwise, any changes to _root in the function is only a local change.

Declaration

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

Definition

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

Upvotes: 5

Related Questions