5

二分木で幅優先探索のコードを書こうとしています。すべてのデータをキューに保存しましたが、すべてのノードに移動してすべての子を消費する方法がわかりません。

Cでの私のコードは次のとおりです。

void breadthFirstSearch (btree *bt, queue **q) {
   if (bt != NULL) {

      //store the data to queue if there is

      if (bt->left != NULL) enqueue (q, bt->left->data);
      if (bt->right != NULL) enqueue (q, bt->right->data);

      //recursive

      if (bt->left != NULL) breadthFirstSearch (bt->left, q);
      if (bt->right != NULL) breadthFirstSearch (bt->right, q);
   }
}

すでにルート データをエンキューしましたが、まだ機能していません。誰かが私の間違いを指摘できますか?

4

3 に答える 3

13

BFS は、再帰なしで簡単に作成できます。キューを使用して拡張を注文するだけです。

void BFS(btree *start)
{
    std::deque<btree *> q;
    q.push_back(start);
    while (q.size() != 0)
    {
        btree *next = q.front();
        // you may want to print the current node here or do other processing
        q.pop_front();
        if (next->left)
            q.push_back(next->left);
        if (next->right)
            q.push_back(next->right);
    }
}

重要なのは、ツリーを再帰的にトラバースする必要がないことです。ノードにアクセスする順序をデータ構造に処理させるだけです。

ここでは C++ 両端キューを使用していますが、項目を背面に配置して前面から取得できるものはすべて正常に機能します。

于 2011-05-17T03:12:04.627 に答える
5

ここでは、幅優先のトラバーサルを行っていません。代わりに、左右の要素をキュー内にエンキューし、左側のサブツリーに移動します。最初に左のサブツリーを使い果たし、次に右のサブツリーに移動します。

代わりにノードをエンキューする手順を記述してください。

void breadthFirstSearch (btree *bt, queue **q) {
 btree *tmpNode;
 enqueue(q,bt); //Assuming your root node has data

 while (!isempty(q)) //Assume isempty returns false when queue is not empty
 {
  tmpNode = dequeue(q);
  //Do whatever you want to do with tmpNode->data
  enqueue(tmpNode->left);
  enqueue(tmpNode->right);
  /* If this is a acyclic graph(tree) then this procedure should do, else you have to mark the nodes you have visited in-order not to end in a cycle */
 }

}

int main()
{
breadthFirstSearch(bt,q)
return 0
}
于 2011-05-17T03:02:58.870 に答える