二叉树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类构造函数来初始化孩子的指针和info。

Answer 2

是的，你做得很好，但 要实现DFS algorithm.because “it goes deeper until it reaches to a leaf and then back tracks.”

，它是清洁改变为与while：

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

Answer 3

您正在填充队列，但是您并未在遍历树中使用它。您稍后使用它按您访问过的顺序打印节点，但此顺序是DFS而不是BFS。您也可以立即打印这个简单案例中的节点，目前不需要队列。

这里是在C实际工作DFS算法++像伪代码：

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

这是非常相似的，但它是通过使用堆栈改变顺序。