バイナリツリーのキュー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

うんあなたはよくやっているが、 あなたは "it goes deeper until it reaches to a leaf and then back tracks."

algorithm.because DFSを実装していると、しばらくのために変更するクリーナーです：

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

Answer 3

キューを満たしていますが、ツリーを横断する際にキューを使用していません。後で訪問した順序でノードを印刷するためにこのノードを使用しますが、この順序はBFSではなくDFSです。また、この単純なケースですぐにノードを印刷することもできます。現在、キューは必要ありません。ここで

は、擬似コードのようなC++でactuall 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の場合は、実際のキューを使用します。あなたの実装は次のアルゴリズム（私はちょうどactuall明示的なスタックによって再帰を置き換え）とほぼ同等です：

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

しかし、それはスタックを使用して順序を変更している、非常によく似ています。