在二叉树中的BFS

Question

我在编写二叉树中的广度优先搜索代码。我已将所有数据存储在队列中，但我无法弄清楚如何前往所有节点并使用其所有子节点。

这里是我的代码在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); 
    } 
} 

我已经排队根数据，但它仍然没有工作。 任何人都可以指出我的错误吗？

Answer 1

你不在这里做广度优先遍历。相反，您将队列中的左侧和右侧元素排入队列并移至左侧子树。您正在耗尽左侧子树，然后移动到右侧子树。

写入一个过程来排队节点。

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 
} 

Answer 2

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++ deque，但任何可让您将项目放在后面并从前面获取它们的东西都可以正常工作。

Answer 3

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

    q = queue_allocate(); 
    queue_insert (q, head); 

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

首先将head节点插入到队列中。循环将在队列不空时进行迭代。从头节点开始，在每次迭代中删除一个节点，并将非空的子节点插入到队列中。在每次迭代中，一个节点出去并且它的非空子节点被推送。在下一次迭代中，下一个最早发现的顶点（现在位于队列的前面）被取出（按照它们被发现的顺序），然​​后处理它们以检查它们的孩子。

       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} 

以上迭代停止时，我们得到的是没有更多的它正在等待被选择，在队列中发现的顶点，所以所有这些都在二叉树（图连接组件）发现的顶点选择。

我的代码首先通过队列中的节点，然后递归遍历这些子节点，这会创建一个DFS模式。如果您必须进行递归，则需要检查队列是否为空作为基础条件。还有一个检查你是如何通过队列，我认为这可能是不正确的。我会建议一个迭代解决方案。