二叉樹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); 
    } 
} 

這是非常相似的，但它是通過使用堆棧改變順序。