c++ - 二叉树BFS队列

我只是尝试一些代码，而不是经验丰富的编码器。我实现了（至少认为）级别顺序遍历，并且排序很容易完成。想知道它是否正确的方法。

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

}

最佳答案

这使用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);
}

只是一些注意事项：


不要在容器上使用size()来确定是否存在元素：例如遍历元素以对其进行计数（尽管没有标准容器可以计数），而empty()则说出您真正想知道的内容（尽管应该将其称为is_empty()）。
不要使用全局变量。
您的程序似乎泄漏了所有node对象。
您应该为您的node类提供一个构造函数，以初始化子级和info的指针。

关于c++ - 二叉树BFS队列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9849861/