Why can't I return pointer to a node of my BST tree structure? C++

user_17750604 0
Viewed 97

I was coding a BST Tree, and first i made it with integer key, everything worked fine. Then i copied my code and made some changes, i switched integer key to string key and also added one new pointer (because my goal is to create two trees, one with English words and one with their Polish translation) so i tested it just on single tree with string key first and insert function works fine like in the interger tree, but search function is returning some garbage insted of NULL or pointer to node. I dont really know what is a problem here.

I put the code of Integer tree below:

#include <iostream>
#include <fstream>
#include <string.h>
#include <string>
using namespace std;

        typedef struct BST
    {
        int key;
        BST* right;
        BST* left;
    }BST_node;
    
    BST_node* CreateNewNode(int data)  // function that returns new node of my tree
    {
        BST_node* NewNode = new BST_node;
        NewNode->key = data;
        NewNode->right = NULL;
        NewNode->left = NULL;
        return NewNode;
    }
    
    BST_node* bstSearch(BST_node* root, int data) // search function
    {
        if (root == NULL)
            return NULL;
    
        else if (root->key == data)
            return root;
    
        else if (root->key < data)
            bstSearch(root->right, data);
    
        else
            bstSearch(root->left, data);
    }
    
    void bstInsert(BST_node*& root, int data) // insert function
    {
        if (root == NULL)
            root = CreateNewNode(data);
        
        if (data < root->key) 
            bstInsert(root->left, data); 
    
        else if (data > root->key) 
            bstInsert(root->right, data); 
    }
            
    int main()
    {
        ifstream in1("InTest1.txt"); // InTest1.txt:1 2 4 3 5 52 2 4
        BST_node* root = NULL;
        int suppVar;
        while (!in1.eof())
        {
            in1 >> suppVar;
            bstInsert(rootEng, suppVar);
        }
        BST_node* tmp = bstSearch(rootEng, 2);
        if (tmp == NULL)
            cout << "There is no element with given key";
        else
            cout << "key = " << tmp->key;
        
    }

OUT: key = 2

And also i put the code of string key version of my tree below:

#include <iostream>
#include <fstream>
#include <string.h>
#include <string>
using namespace std;

typedef struct BST_str
{
    string key;
    BST_str* right;
    BST_str* left;
    BST_str* engWordPtr; // pointer to node in translation tree (not used yet)
}BST_strNode;

BST_strNode* CreateNewStrNode(string data) // function that returns new node of my tree
{
    BST_strNode* NewNode = new BST_strNode;
    NewNode->key = data;
    NewNode->right = NULL;
    NewNode->left = NULL;
    NewNode->engWordPtr = NULL;
    return NewNode;
}

BST_strNode* bstStrSearch(BST_strNode* root, string data) // search function
{
    if (root == NULL)
        return NULL;

    else if (strcmp(root->key.data(), data.data()) == 0)
        return root;

    else if (strcmp(root->key.data(), data.data()) < 0)
        bstStrSearch(root->right, data);

    else if (strcmp(root->key.data(), data.data()) > 0)
        bstStrSearch(root->left, data);
}

void bstStrInsert(BST_strNode*& root, string data) // insert function
{
    if (root == NULL)
        root = CreateNewStrNode(data);

    else if (strcmp(root->key.data(), data.data()) > 0) 
        bstStrInsert(root->left, data);

    else if (strcmp(root->key.data(), data.data()) < 0)
        bstStrInsert(root->right, data);
}

int main()
{
    ifstream in1("InTest2.txt"); // InTest2.txt:O G X E OH D F I OA H OB OX
    BST_strNode* rootEng = NULL;
    string suppVar;
    while (!in1.eof())
    {
        in1 >> suppVar;
        bstStrInsert(rootEng, suppVar);
    }
    BST_strNode* tmp = bstStrSearch(rootEng, "OXcasdf");
    if (tmp == NULL)
        cout << "There is no element with given key";
    else
        cout << "key = " << tmp->key;
}

OUT: key =

And program crashes, it doesnt matter if i want to search for string that is already there or not, always the same result, probably its returning some garbage instead of node or NULL but i don't really know why it's working on integer tree, but on string tree doesn't. It also generates 3 warnings:

Warning C26495 Variable 'BST_str::engWordPtr' is uninitialized. Always initialize a member variable (type.6).

Warning C26495 Variable 'BST_str::left' is uninitialized. Always initialize a member variable (type.6).

Warning C26495 Variable 'BST_str::right' is uninitialized. Always initialize a member variable (type.6).

And also an exception while debugging:

Exception thrown: read access violation. this was 0x45.

Thanks for the help in advance.

binary-search-tree tree pointers c++
2 Answers

The recursive function bstSearch is incorrect because it does not return a node in each its path of execution

BST_node* bstSearch(BST_node* root, int data) // search function
{
    if (root == NULL)
        return NULL;

    else if (root->key == data)
        return root;

    else if (root->key < data)
        bstSearch(root->right, data);

    else
        bstSearch(root->left, data);
}

The last if else statements should look like

    else if (root->key < data)
        return bstSearch(root->right, data);

    else
        return bstSearch(root->left, data);

Also for the function designed for strings there is no need to use the C function strcmp. The function could be defined the following way

BST_strNode* bstStrSearch( BST_strNode* root, const string &data) // search function
{
    if (root == NULL)
        return NULL;

    else if ( root->key == data )
        return root;

    else if ( root->key < data )
        return bstStrSearch(root->right, data);

    else 
        return bstStrSearch(root->left, data);
}

Pay attention to that the condition of the while loop

while (!in1.eof())
{
    in1 >> suppVar;
    bstStrInsert(rootEng, suppVar);
}

is incorrect. The eof state can occur after this statement

    in1 >> suppVar;

Instead you should write

while ( in1 >> suppVar)
{
    bstStrInsert(rootEng, suppVar);
}
user_28772410

Note when compiled, the compiler should print a warning along the lines of:

warning: control may reach end of non-void function

in reference to bstStrInsert. Indeed, looking at the function definition, the two recursive branches don't return a value.

To prevent the warning (and this sort of error in general), you can use a local variable to hold the result, and have a single return.

Additionally, the functions should be rewritten as member function of the BST node class. You can also use templates (and template specializations) rather than creating separate, unrelated BST classes for each key type. With scohe001's protip, the template functions will work with any key type that implements standard comparison operators (so you don't have to write a specialization for std::string).

template<typename K> BST_Node<K>* BST_Node<K>::search(BST_Node<K>* node, const K& data) {
    BST_Node<K>* result = NULL;

    if (node) {
        if (node->key == data)
            result = node;
        else if (node->key < data)
            result = search(node->right, data);
        else // if (node->key > data)
            result = search(node->left, data);
    }

    return result;
}

Since the last branch covers all remaining cases, the if (node->key > data) test is unnecessary.

The above BST_Node<K>::search has an extra BST_Node<K>* argument that isn't strictly necessary. An alternative is to call search on each node, which means moving the pointer test to immediately before each recursive call (and operating on this, rather than the extra node argument).

template<typename K> BST_Node<K>* BST_Node<K>::search(const K& data) {
    BST_Node<K>* result = NULL;

    if (key == data)
        result = this;
    else if (key < data) {
        if (right) {
            result = right->search(data);
        }
    } else if (left) // (key > data)
        result = left->search(data);

    return result;
}

In general, an interactive debugger is your most powerful tool for troubleshooting crashes and unexpected behavior. Find and learn to use whatever debugger your development suite provides.

Additional

As noted in C++ references, passing string::data to C string functions can result in undefined behavior, as it's not guaranteed to be null terminated. string::c_str should be used for that purpose, but (in general) C string functions should only be used when interacting with C code (such as libraries).

When printing a message, be sure to include a newline. This can be done with a newline in the string, but better is to output std::endl, which will also flush the output buffer (if output is buffered, which it probably is).

Importing all of std into the current namespace is fine for one-offs, sample and practice code, but shouldn't be done in production. Importing specific symbols (such as std::cin, std::cout and std::endl) is fine and unlikely to cause collisions.

user_905270
Related