Очередь для двоичного дерева BFS

Question

Я просто пробовал какой-то код, а не опытный кодер. Я реализовал (по крайней мере, думаю) обход уровня порядка, и это довольно легко сделать. Хотите знать, если это правильный подход.

#include<iostream>
#include<queue>
using namespace std;

class node {
public :
  node *right;
  node *left;
  int info;
}*root;

queue<int> inf;

void bfs(node *t)
{
if(t!=NULL)
{
    if(t->right!=NULL)
        inf.push(t->right->info);

    if(t->left!=NULL)
        inf.push(t->left->info);

    bfs(t->right);
    bfs(t->left);
}
}

int main()
{
node *temp = new node();
temp->info = 1;

root = temp;

root->right = new node();
root->right->info = 2;
root->right->right = root->right->left = NULL;

root->left = new node();
root->left->info = 3;
root->left->right = root->left->left = NULL;

node *tmp = root;
root=root->right;

root->right = new node();
root->right->info = 4;
root->right->right = root->right->left = NULL;

root->left = new node();
root->left->info = 5;
root->left->right = root->left->left = NULL;

root = tmp;
root = root->left;

root->right = new node();
root->right->info = 6;
root->right->right = root->right->left = NULL;

root->left = new node();
root->left->info = 7;
root->left->right = root->left->left = NULL;

root = temp;


node *it;
it = root;

inf.push(root->info);


bfs(root);
for(;inf.size()!=0;)
{
    cout<<inf.front()<<" : ";
    inf.pop();
}

return 0;

}

Answer 1

Это использует std::queue<int> печатать узлы в порядке DFS! Простое использование очереди где-то не делает порядок обхода BFS. То, что вы хотите, это std:: queue<node*> где вы положили корневой узел. Затем вы выполняете итерацию, пока очередь не пуста, и на каждой итерации вы берете следующий узел из очереди и помещаете его дочерние элементы в очередь:

for (std::queue<node*> inf(1, root); !inf.empty(); inf.pop()) {
    n = inf.front();
    process(n->info);
    if (n->left) inf.push(n->left);
    if (n->right) inf.push(n->right);
}

Всего несколько заметок:

1. Не использовать size() на контейнере, чтобы определить, есть ли элементы: он может, например, пройти через элементы для их подсчета (хотя ни один из стандартных контейнеров не делает) и empty() говорит то, что вы действительно хотите знать (хотя это должно было называться is_empty()).
2. Не используйте глобальные переменные.
3. Кажется, ваша программа пропускает все node объекты.
4. Вы должны дать свой node класс конструктор для инициализации указателей для детей и info,

Answer 2

Вы заполняете очередь, но не используете ее при обходе дерева. Позже вы будете использовать его для печати узлов в том порядке, в котором вы их посетили, но этот порядок - DFS, а не BFS. Также вы можете сразу же распечатать узлы в этом простом случае, в настоящее время нет необходимости в очереди.

Вот действующий алгоритм DFS в C++, подобный псевдокоду:

queue q;
q.push_back( tree.root() );

while( !q.empty() ) {
  node n = q.pop_front();
  // Visit n here (i.e. print it in your case)
  for all( c in n.children() ) {
    q.push_back( c );
  }
}

Как видите, с BFS нет рекурсивного вызова вообще.

Если вы используете рекурсию, это обычно означает использование простой доступной структуры данных стека. Однако для BFS вы хотите использовать реальную очередь. Ваша реализация примерно эквивалентна следующему алгоритму (я только заменил рекурсию на фактически полный стек):

stack s;
s.push( tree.root() );

while( !s.empty() ) {
   node n = s.pop();
  // Visit n here (i.e. print it in your case)
  for all( c in n.children() ) {
    s.push( c );
  }
}

Это очень похоже, однако это меняет порядок с помощью стека.

Answer 3

Да, у вас все хорошо, но вы реализуете алгоритм DFS. Потому что " он идет глубже, пока не достигнет листа, а затем проследит назад".

и чище поменять на некоторое время:

while(inf.size())
{
    cout<<inf.front()<<" : ";
    inf.pop();
}