Поиск в ширину по дереву двоичного поиска
Я пытаюсь создать вначале широкую функцию поиска для двоичного дерева поиска, но, похоже, я не могу заставить его работать. Любые указатели будут с благодарностью!
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;
}
Решение
Так как 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;
}
Другие решения
Несколько вещей:
Тест для node == NULL должен прийти до доступа к узлу:
if (node == NULL)
return false;
queue.push(node);
Также ваша очередь должна быть типа узла, и вы должны вставлять узлы в очередь:
очередь *> очередь;
И, наконец, у вас нет доступа к элементу dequed, вам нужно использовать front метод класса очереди для доступа к переднему элементу перед вызовом pop.