# BFS中的二进制树[英] BFS in binary tree

### 问题描述

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

## 推荐答案

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

## 其他推荐答案

```void bfs_bintree (btree_t *head)
{
queue_t *q;
btree_t *temp;

q = queue_allocate ();

while (!queue_is_empty (q))
{
temp = queue_remove (q);

if (temp->left)
queue_insert (temp->left);

if (temp->right)
queue_insert (temp->right);
}
queue_free (q);
return;
}
```

```                                A
/ \
/   \
B     C
/ \     \
/   \     \
D     E     F
/ \         / \
/   \       /   \
G     H     I     J

iteration  Vertex Selection Discovery Queue State
initial                    :  A
1            A          :  B C     {A is removed and its children inserted}
2            B          :  C D E   {B is removed and its only child inserted}
3            C          :  D E F   {C is removed and its children inserted}
4            D          :  E F G H {D is removed and its children inserted}
5            E          :  F G H   {E is removed and has not children}
6            F          :  G H I J {F is removed and its children inserted}
7            G          :  H I J   {G is removed has no children}
8            H          :  I J     {H is removed has no children}
9            I          :  J       {I is removed has no children}
10           J          :  (empty) {J is removed has no children}
```

i您的代码首先您通过队列中的节点加入，然后再次递归地穿越这些孩子，从而创建DFS模式.如果您必须进行递归，则需要检查队列是否为基本条件为空.还要检查您如何通过队列，我认为这可能是不正确的.我建议迭代解决方案.

## 其他推荐答案

```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()
{