-1

我正在尝试为二叉搜索树编写一个“包含”函数。我在编译“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”的节点——因此，我希望结果为假。

4

1 回答 1

3

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，您还可以确保没有人会因为它的存在而感到困惑或意外调用它。

另一种可能性是完全避免递归并使用循环。

于 2013-10-24T21:40:00.370 回答