c++ - 二叉树 BFS 的队列

Question

我只是在尝试一些代码，而不是一个有经验的编码员。我实现了(至少认为)Level Order 遍历并且它很容易完成。想知道这种方法是否正确。

#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构造一个构造函数来初始化 child 的指针和info .