이진 검색 트리에 포함 된 함수

Question

이진 검색 트리에 "포함"함수를 쓰려고합니다. "처리되지 않은 예외를 BST.exe 0x77291CB3 (ntdll.dll)에서 컴파일 할 때 다음 오류가 나타납니다. 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'- 따라서, 나는 결과가 거짓으로 기대.

Answer 1

current은 함수의 로컬 변수입니다. 함수가 재귀 적으로 호출 될 때, 각각의 새로운 호출은 자신이 가지고있는 로컬 변수를 가지게 될 것이고 외부 호출이 외부 함수의 로컬 변수에 대해 무엇을했는지 알지 못할 것이다.

특히 재귀 호출 전에 함수는 current 노드를 다음에 검색해야 할 노드로 설정합니다. 그러나 호출 된 함수는 변수 current을 결코 보지 못하며 변수 current을 가져와 root으로 초기화하고 거기에서 검색을 시작합니다.

각 재귀 호출은 스택 메모리가 부족하여 스택 오버플로가 발생할 때까지 처음부터 검색을 시작한 다음 다시 호출합니다.

current 변수를 설정하는 대신 함수의 재귀 호출에 추가 매개 변수로 현재 노드를 전달해야합니다.

당신은 contains()의 매개 변수를 아마도 추가 매개 변수와 거래를한다 도우미 함수로 실제 작업을 이동하는 것이 문제를 해결할 수있는 좋은 방법 변경하지 않으려면 :

bool BST::contains(int value) { 
    return contains_rec(value, root); 
} 

bool BST::contains_rec(int value, Node *current) { 
    ... 
} 

하는 경우를 당신 도우미 기능을 만들 수 있습니다. private 당신은 또한 아무도 그것의 존재에 의해 혼란스러워하거나 실수로 그것을 호출하지 않도록 할 수 있습니다.

또 다른 가능성은 모두 재귀를 피하고 대신 루프를 사용하는 것입니다.