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

Question

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

我把Integer树的代码放在下面：

#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不正确，因为它没有在其执行的每个路径中返回一个节点

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 loop 的情况

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

不正确。eof状态可以发生在该语句之后

in1 >> suppVar;

相反，你应该写

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

Answer 2

注意，编译时，编译器应该按照以下行打印警告：

警告：控制可能到达非无效功能的末尾

参考bstStrInsert。事实上，从函数定义来看，这两个递归分支不会返回值。

为了防止出现警告(以及通常的此类错误(，可以使用局部变量来保存结果，并返回一个值。

此外，函数应该重写为BST节点类的成员函数。您也可以使用模板(和模板专业化(，而不是为每个键类型创建单独的、不相关的BST类。使用scohe001的protip，模板函数将与任何实现标准比较运算符的键类型一起工作(因此您不必为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传递给C字符串函数可能会导致未定义的行为，因为它不能保证以null结尾。string::c_str应该用于此目的，但(通常(C字符串函数只能在与C代码(如库(交互时使用。

打印邮件时，请确保包含换行符。这可以通过字符串中的换行来完成，但最好是输出std::endl，它也会刷新输出缓冲区(如果输出是缓冲的，它可能是缓冲的(。

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