我在用 C++ 实现 BST 时遇到问题。当我向 BST 插入大约 20,000 个数据的小数据时,它运行良好。如果我尝试插入大约 100,000 条的大量数据。 BST 出现运行时错误。你们能帮帮我吗?
这是我的实现。 二分查找.h
#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;
struct treeNode
{
long long data;
treeNode *left;
treeNode *right;
};
treeNode *insertNode(treeNode *node,long long data)
{
if(node==NULL)
{
treeNode *temp = new treeNode;
//temp = (treeNode *)malloc(sizeof(treeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = insertNode(node->right,data);
}
else if(data < (node->data))
{
node->left = insertNode(node->left,data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
}
treeNode * searchNode(treeNode *node, long long data)
{
if(node==NULL)
{
/* Element is not found */
return NULL;
}
if(data > node->data)
{
/* Search in the right sub tree. */
return searchNode(node->right,data);
}
else if(data < node->data)
{
/* Search in the left sub tree. */
return searchNode(node->left,data);
}
else
{
/* Element Found */
return node;
}
}
void displayInorder(treeNode *node)
{
if(node==NULL)
{
return;
}
displayInorder(node->left);
cout<<" " << node->data<<" ";
displayInorder(node->right);
}
void displayPreorder(treeNode *node)
{
if(node==NULL)
{
return;
}
cout<<" " <<node->data<<" ";
displayPreorder(node->left);
displayPreorder(node->right);
}
void displayPostorder(treeNode *node)
{
if(node==NULL)
{
return;
}
displayPostorder(node->left);
displayPostorder(node->right);
cout<<" " <<node->data<<" ";
}
我在 : 处收到运行时错误
node->right = insertNode(node->right,data);
请大家帮帮我。
提前致谢!
最佳答案
您可能会用完所有递归的堆栈,因此您可以增加堆栈,或者编写一些(或全部)函数以使用迭代而不是递归(尽管前序、后序、中序遍历很难正确地写成循环)。
这是Search
和Insert
方法的一个简单示例:
struct TreeNode
{
long long data = 0;
std::shared_ptr<TreeNode> left;
std::shared_ptr<TreeNode> right;
TreeNode(long long _data) : data(_data){}
};
class BST
{
public:
void Insert(std::shared_ptr<TreeNode> node)
{
if (!node)
throw std::runtime_error("Cannot insert null node");
if (!root)
{
root = node;
return;
}
std::shared_ptr<TreeNode>* next = &root;
while(*next)
{
if (node->data < (*next)->data)
next = &((*next)->left);
else
next = &((*next)->right);
}
*next = node;
}
std::pair<bool, std::shared_ptr<TreeNode>> Search(long long data)
{
if (!root)
return std::make_pair(false, nullptr); // searching empty tree
std::shared_ptr<TreeNode> next = root;
while(next)
{
if (data < next->data)
next = next->left;
else if (data > next->data)
next = next->right;
else
return std::make_pair(true, next); // match found
}
// no match found
return std::make_pair(false, nullptr);
}
private:
std::shared_ptr<TreeNode> root;
};
可以找到完整的工作演示 here
关于c++ - 二叉搜索树实现 C++ 运行时错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41957849/