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>节点具有有关其子节点的信息，因此您必须将它们放在队列中，而不是您正在做的值。另一件事是你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 元素，你需要front在调用 pop 之前使用 queue 类的方法访问前面的元素。

于 2012-10-24T05:48:47.490 回答