проблема переполнения стека в программе

Question

Так что в настоящее время я получаю странное исключение переполнения стека при попытке запустить эту программу, которая считывает числа из списка в файле данных/текста и вставляет его в двоичное дерево поиска. Странно то, что когда программа работает, когда у меня есть список из 4095 номеров в случайном порядке. Однако, когда у меня есть список из 4095 номеров в порядке возрастания (поэтому он создает линейное дерево поиска), он выдает сообщение о переполнении стека. Проблема не в переменной статического счетчика, потому что даже когда я ее удалил, и положил t = новый 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; 
} 

Answer 1

В языке, как C++, вы не можете использовать рекурсивные алгоритмы на высоких деревьев, потому что каждый вызов функции использует дополнительное пространство на ограниченном стеке. Вы должны либо изменить свой алгоритм (использовать итерацию, а не рекурсию) или использовать сбалансированную двоичную древовидную структуру.

Если у вас ограниченный вход (как вы видите, в этом случае), вы можете сбросить давление в стеке, сделав стек больше (как предполагает Андреас) или поместите меньше данных в стек. Кажется, что insert является функцией-членом класса BinarySearchTree, хотя он не ссылается ни на какие другие члены класса. Если вы сделаете insert статическим методом (или обычной функцией, не входящей в класс), ему не нужно будет нажимать указатель this на стек для каждого вызова функции, и вы сможете получить больше итераций до переполнения.

Answer 2

Вы можете увеличить размер стека. В зависимости от того, какой компилятор вы работаете с этим, выполняется по-разному. Например, в Visual Studio размер стека может быть установлен с помощью опции командной строки:

/F stacksize