二叉搜索樹包含函數

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，將其初始化爲root，然後從那裏開始搜索。

每次遞歸調用將從頭開始搜索，然後再次調用自身，直到用完堆棧內存並導致堆棧溢出。

而不是設置current變量，您應該將當前節點作爲附加參數傳遞給函數的遞歸調用。

如果你不想改變參數來處理這很可能是移動的實際工作提高到一個助手函數，它涉及的是附加參數的好方法：

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

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

如果你做助手功能private你也可以確保沒有人因爲它的存在而感到困惑，或者偶然地打電話給它。

另一種可能性是完全避免遞歸併使用循環代替。