程序中堆栈溢出问题
因此，当我尝试运行这个程序时，我目前遇到了一个奇怪的堆栈溢出异常，该程序从数据/文本文件中的列表中读取数字并将其插入到二叉搜索树中。奇怪的是，当程序运行时，我有一个随机顺序的 4095 个数字列表。然而，当我有一个按升序排列的 4095 个数字的列表（因此它形成一个线性搜索树）时，它会抛出堆栈溢出消息。问题不在于静态计数变量，因为即使我删除它并放入 t=new BinaryNode(x,1) 它仍然给出堆栈溢出异常。我尝试调试它，它在 if (t == NULL){ t = new BinaryNode(x,count); 这是插入函数。
BinaryNode *BinarySearchTree::insert(int x, BinaryNode *t) {
static long count=0;
count++;
if (t == NULL){
t = new BinaryNode(x,count);
count=0;
}
else if (x < t->key){
t->left = insert(x, t->left);
}
else if (x > t->key){
t->right = insert(x, t->right);
}
else
throw DuplicateItem();
return t;
}
So I am currently getting a strange stack overflow exception when i try to run this program, which reads numbers from a list in a data/text file and inserts it into a binary search tree. The weird thing is that when the program works when I have a list of 4095 numbers in random order. However when i have a list of 4095 numbers in increasing order (so it makes a linear search tree), it throws a stack overflow message. The problem is not the static count variable because even when i removed it, and put t=new BinaryNode(x,1) it still gave a stack overflow exception. I tried debugging it, and it broke at if (t == NULL){ t = new BinaryNode(x,count); Here is the insert function.
BinaryNode *BinarySearchTree::insert(int x, BinaryNode *t) {
static long count=0;
count++;
if (t == NULL){
t = new BinaryNode(x,count);
count=0;
}
else if (x < t->key){
t->left = insert(x, t->left);
}
else if (x > t->key){
t->right = insert(x, t->right);
}
else
throw DuplicateItem();
return t;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在像 C++ 这样的语言中，您无法在高大的树上使用递归算法，因为每个函数调用都会在有限的堆栈上使用额外的空间。您必须更改算法（使用迭代而不是递归）或使用平衡二叉树结构。
如果您的输入有界（正如本例中所示），您可以通过增大堆栈（如 Andreas 建议的那样）或在堆栈上放置更少的数据来减轻堆栈压力。似乎
insert是BinarySearchTree类的成员函数，尽管它没有引用该类的任何其他成员。如果您将insert设为静态方法（或不在类中的常规函数），则不必为每个函数调用将this指针压入堆栈，并且您将能够在溢出之前获得更多迭代。In a language like C++, you cannot use recursive algorithms on tall trees because each function call uses additional space on a limited stack. You must either change your algorithm (use iteration rather than recursion) or use a balanced binary tree structure.
If you have a bounded input (as it appears you do in this case), you can relieve stack pressure by either making the stack bigger (as Andreas suggests) or put less data on the stack. It seems as though
insertis a member function of theBinarySearchTreeclass even though it doesn't reference any other members of the class. If you makeinserta static method (or a regular function not in a class), it won't have to push athispointer on the stack for every function call, and you will be able to get more iterations before overflowing.您可以增加堆栈的大小。根据您使用的编译器，这可以通过不同的方式完成。例如，在 Visual Studio 中，可以使用命令行选项设置堆栈大小：
You can increase the size of the stack. Depending on which compiler you're working with this is done in different ways. For instance in Visual Studio the stack size can be set with the command line option: