0

二分探索木の幅優先探索関数を作ろうとしているのですが、うまくいかないようです。どんなポインタでも大歓迎です！

template <class T>
bool BST<T>::displayBfs(T searchKey, BST<T> *node)
{
    BST<T> *tmp = node;
    queue <int> queue;
    queue.push(node->mData);

    if (node == NULL)
    {
        return false;    
    }

    while (!queue.empty())
    {
        queue.pop();
        if (tmp->mData == searchKey)
            return true;
        else
        {
            if(tmp->mLeft != NULL)
                queue.push(tmp->mLeft->mData);
            if(tmp->mRight != NULL)
                queue.push(tmp->mRight->mData);
        }
    }
    return false;
}
4

2 に答える 2

2

ノードには子に関する情報があるため、BST<T>現在行っている値ではなく、ノードをキューに入れる必要があります。もう1つのことは、要素をqueueポップする前に要素を取得していないことです。std::queue最後に、使用していると想定しているため、キューに別の名前を付ける必要があります。

BFS を次のように書き直してみてください。

template <class T>
bool BST<T>::displayBfs(T searchKey, BST<T> *node)
{
    if (node == NULL) return false;

    queue<BST<T>*> q;
    q.push(node);

    while (!q.empty())
    {
        BST<T>* tmp = q.front();
        q.pop();

        if (tmp->mData == searchKey)
            return true;
        else
        {
            if(tmp->mLeft != NULL)
                q.push(tmp->mLeft);
            if(tmp->mRight != NULL)
                q.push(tmp->mRight);
        }
    }
    return false;
}
于 2012-10-24T05:45:42.753 に答える
0

いくつかのこと:

ノードにアクセスする前に、次のテストがnode == NULL行​​われます。

if (node == NULL)
    return false;    
queue.push(node);

また、キューはノード タイプである必要があり、ノードをキューに挿入する必要があります。

キュー*>キュー;

最後に、dequed 要素にアクセスしていないため、frontpop を呼び出す前に queue クラスのメソッドを使用してフロント要素にアクセスする必要があります。

于 2012-10-24T05:48:47.490 に答える