Двоичное дерево поиска содержит функцию
Я пытаюсь написать «содержит» функцию для двоичного дерева поиска. При компиляции я получаю следующую ошибку: «Необработанное исключение в 0x77291CB3 (ntdll.dll) в BST.exe: 0xC00000FD: переполнение стека (параметры: 0x00000001, 0x001E2FFC).» Ниже мой код.
struct Node {
int data;
Node* leftChild;
Node* rightChild;
Node() : leftChild(NULL), rightChild(NULL) {}
};
struct BST {
Node* root;
BST() : root(NULL) {}
void insert(int value);
bool contains(int value);
};
void BST::insert(int value) {
Node* temp = new Node();
temp->data = value;
if(root == NULL) {
root = temp;
return;
}
Node* current;
current = root;
Node* parent;
parent = root;
current = (temp->data < current->data ? (current->leftChild) : (current->rightChild)
while(current != NULL) {
parent = current;
current = (temp->data < current->data) ? (current->leftChild) : (current->rightChild)
}
if(temp->data < parent->data) {
parent->leftChild = temp;
}
if(temp->data > parent->data) {
parent->rightChild = temp;
}
}
bool BST::contains(int value) {
Node* temp = new Node();
temp->data = value;
Node* current;
current = root;
if(temp->data == current->data) { // base case for when node with value is found
std::cout << "true" << std::endl;
return true;
}
if(current == NULL) { // base case if BST is empty or if a leaf is reached before value is found
std::cout << "false" << std::endl;
return false;
}
else { // recursive step
current = (temp->data < current->data) ? (current->leftChild) : (current->rightChild);
return contains(temp->data);
}
}
int main() {
BST bst;
bst.insert(5);
bst.contains(4);
system("pause");
}
В его нынешнем виде я бы вставил один узел со значением «5», и я бы искал в двоичном дереве поиска узел со значением «4» — таким образом, я ожидал бы, что результат будет ложным.
Решение
current является локальной переменной в contains() функция. Когда функция вызывается рекурсивно, каждый новый вызов получит свой собственный набор локальных переменных и не увидит, что внешний вызов сделал с локальными переменными во внешней функции.
Особенно перед рекурсивным вызовом функция устанавливает current узел к узлу, который должен быть найден следующим. Но вызываемая функция никогда не увидит, что current переменная, она получит свою собственную current переменная, инициализировать его rootи начать поиск оттуда.
Каждый рекурсивный вызов начинает поиск с самого начала, а затем снова вызывает сам себя, пока вы не исчерпаете память стека и не получите переполнение стека.
Вместо установки current переменная, вы должны передать текущий узел в качестве дополнительного параметра для рекурсивного вызова contains() функция.
Если вы не хотите изменять параметры contains() Хороший способ справиться с этим, вероятно, состоит в том, чтобы переместить реальную работу в вспомогательную функцию, которая обрабатывает дополнительный параметр:
bool BST::contains(int value) {
return contains_rec(value, root);
}
bool BST::contains_rec(int value, Node *current) {
...
}
Если вы делаете вспомогательную функцию private Вы также можете убедиться, что никто не смущен его присутствием или случайно позвонил.
Другой возможностью было бы вообще избежать рекурсии и использовать цикл.
Другие решения
Других решений пока нет …