-1

二分探索木の「含む」関数を作成しようとしています。コンパイル時に次のエラーが表示されます。以下は私のコードです。

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' を持つノードのバイナリ検索ツリーを検索します。したがって、結果は false になると予想されます。

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を作成すると、その存在に混乱したり、誤って呼び出したりしないようにすることもできます。

もう 1 つの可能性は、再帰を完全に回避し、代わりにループを使用することです。

于 2013-10-24T21:40:00.370 に答える