为什么我不能 return 指向我的 BST 树结构的节点的指针？ C++

Question

我正在编写一个 BST 树，首先我用整数键创建它，一切正常。然后我复制了我的代码并做了一些更改，我将整数键切换为字符串键并添加了一个新指针（因为我的目标是创建两棵树，一棵有英文单词，一棵有他们的波兰语翻译）所以我测试了它首先使用字符串键和插入函数的单树像在整数树中一样工作正常，但搜索函数返回一些 NULL 的垃圾或指向节点的指针。我真的不知道这里有什么问题。

我把整数树的代码放在下面：

#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

我还把我的树的字符串键版本的代码放在下面：

#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 =

然后程序崩溃了，不管我是否想搜索已经存在或不存在的字符串，总是相同的结果，可能它返回一些垃圾而不是节点或 NULL 但我真的不知道为什么在整数树上工作，但在字符串树上没有。它还会生成 3 个警告：

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).

还有调试时的异常：

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

提前感谢您的帮助。

Answer 1

递归函数bstSearch不正确，因为它return每个执行路径中没有一个节点

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

最后一个 if else 语句应该是这样的

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

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

此外，对于为字符串设计的函数，无需使用 C 函数 strcmp。该函数可以按以下方式定义

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

注意while循环的条件

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

不正确。 eof状态可以出现在这条语句之后

    in1 >> suppVar;

你应该这样写

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

Answer 2

请注意，编译时，编译器应打印如下警告：

warning: control may reach end of non-void function

参照bstStrInsert。实际上，查看函数定义，两个递归分支没有 return 值。

为了防止警告（以及一般的此类错误），您可以使用局部变量来保存结果，并且有一个 return.

此外，函数应该重写为BST节点的成员函数class。您还可以使用模板（和模板特化），而不是为每个密钥类型创建单独的、不相关的 BST classes。使用 scohe001 的提示，模板函数将与实现标准比较运算符的任何键类型一起使用（因此您不必为 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;
}

由于最后一个分支涵盖了所有剩余的情况，因此 if (node->key > data) 测试是不必要的。

上面的 BST_Node<K>::search 有一个额外的 BST_Node<K>* 参数，这并不是绝对必要的。另一种方法是在每个节点上调用 search，这意味着将指针测试移动到紧接在每个递归调用之前（并在 this 上运行，而不是额外的 node 参数）。

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

一般来说，交互式调试器是解决崩溃和意外行为的最强大工具。查找并学习使用您的开发套件提供的任何调试器。

额外

如 C++ 参考文献中所述，传递 string::data to C string functions can result in undefined behavior, as it's not guaranteed to be null terminated. string::c_str 应该用于此目的，但（通常）C 字符串函数应该只在与 C 代码（例如库）交互时使用。

打印消息时，请务必包含换行符。这可以通过字符串中的换行符来完成，但更好的是输出 std::endl，这也会刷新输出缓冲区（如果输出被缓冲，可能是这样）。

将所有 std 导入当前命名空间对于一次性、示例和练习代码来说是好的，但不应该在生产中完成。导入特定符号（例如 std::cin、std::cout 和 std::endl）是可以的，不太可能导致冲突。

为什么我不能 return 指向我的 BST 树结构的节点的指针？ C++

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

c++

tree

pointers

binary-search-tree

额外