Поиск в ширину по дереву двоичного поиска

Я пытаюсь создать вначале широкую функцию поиска для двоичного дерева поиска, но, похоже, я не могу заставить его работать. Любые указатели будут с благодарностью!

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;
}

0

Решение

Так как 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;
}
2

Другие решения

Несколько вещей:

Тест для node == NULL должен прийти до доступа к узлу:

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

Также ваша очередь должна быть типа узла, и вы должны вставлять узлы в очередь:

очередь *> очередь;

И, наконец, у вас нет доступа к элементу dequed, вам нужно использовать front метод класса очереди для доступа к переднему элементу перед вызовом pop.

0

По вопросам рекламы [email protected]