程序没有显示在二进制搜索树中插入的值

Question

我曾尝试编写一段代码来实现二进制搜索树，但当我运行代码时，什么都不输出，并关闭了一个程序。我认为我的插入函数是正确的，因为我写了cout<lt"是"；在插入函数的多个位置，并显示我在顺序遍历中使用的二进制搜索树的所有节点，顺序遍历是在一个简单函数内递归完成的。这是我的代码：

#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *right;
Node *left;
};
void insert(Node **root_ref, int value)
{
Node *temp = new Node();
temp->data = value;
temp->right = NULL;
temp->left = NULL;
Node *current = *root_ref;
if (*root_ref == NULL)
{
*root_ref = temp;
return;
}
while (current != NULL)
{
if ((temp->data < current->data) && (current->left == NULL))
{
current->left = temp;
return;
}
else if ((temp->data > current->data) && (current->right == NULL))
{
current->right = temp;
return;
}
else if ((temp->data > current->data))
{
current = current->right;
}
else
{
current = current->left;
}
}
}
void printinorder(Node *root1)
{
printinorder(root1->left);
cout << " " << root1->data << " ";
printinorder(root1->right);
}
int main()
{
Node *root = NULL;
insert(&root, 60);
insert(&root, 50);
insert(&root, 70);
insert(&root, 30);
insert(&root, 53);
insert(&root, 80);
insert(&root, 65);
printinorder(root);
}

Answer 1

对于初学者来说，当一个值被添加到树中时，当已经有一个节点具有相同的值时，函数insert可能会产生内存泄漏，因为在这种情况下，只有这个else语句才能被评估

while (current != NULL)
{
//...
else
{
current = current->left;
}
}

因此，循环将结束迭代，尽管已经分配了节点，但不会向树中添加任何内容。

例如，可以用以下方式编写函数

void insert( Node **root_ref, int value )
{
Node *temp = new Node { value, nullptr, nullptr };
while ( *root_ref != nullptr )
{
if ( ( *root_ref )->data < value )
{
root_ref = &( *root_ref )->right;
}
else
{
root_ref = &( *root_ref )->left;
}
}
*root_ref = temp;
}

在递归函数printinorder中

void printinorder(Node *root1)
{
printinorder(root1->left);
cout << " " << root1->data << " ";
printinorder(root1->right);
}

您不是在检查传递的参数是否等于nullptr。因此，该函数调用未定义的行为。

该功能可以通过以下方式编写

std::ostream & printinorder( const Node *root, std::ostream &os = std::cout )
{
if ( root != nullptr )
{
printinorder( root->left, os );
os << " " << root->data << " ";
printinorder( root->right, os );
}
return os;
}