二叉树中的广度优先搜索

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

我已经将根数据加入了队列，但仍然不起作用。有人能指出我的错误吗？

- jason

Answer 1

可以轻松地编写一个不使用递归的 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，但任何允许您将项放在后面并从前面获取它们的内容都可以正常工作。

- Nathan S.

Answer 2

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}

在迭代过程中，当我们发现队列中没有等待选择的已发现顶点时，迭代停止，因此选择了在二叉树（图连接组件）中被发现的所有顶点。

在你的代码中，首先将节点排入队列，然后再递归遍历这些子节点，从而创建了一种深度优先搜索模式。如果必须使用递归，需要检查队列是否为空作为基本条件。同时要检查如何传递队列，我认为可能是不正确的。我建议使用迭代解决方案。

- phoxis

Answer 3

你这里不是在进行广度优先遍历，而是在队列中加入左右元素并移动到左子树。你首先耗尽了左子树，然后才移动到右子树。

编写一个将节点加入队列的过程。

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
}

- Julius Canute

---

我还是不理解。如果您只是将左右节点加入队列，那么队列中只有3个节点（根、根的左侧和根的右侧）。其余的节点将不会被插入到队列中... - jason

我在代码片段中犯了一个错误。我必须检查tempNode->left和tempNode->right是否为null。 - Julius Canute

这是它的工作原理：假设您有一棵完整的二叉树，具有从左到右编号为1到7的7个节点（即根节点为1，最后一个叶节点在右下角为7）。您首先将根节点（编号为1）推入队列中，然后出队并处理该元素，将左侧（编号为2）和右侧（编号为3）节点推入队列中。在下一次迭代中，您出队队列中的第一个元素（编号为2），并将其左侧和右侧元素（即节点编号为4和5）入队。在下一次迭代中，您出队节点编号为3的节点并处理数据元素，并将节点编号为6和7的节点推入队列。 - Julius Canute

这个过程会持续到队列清空。 - Julius Canute

Answer 4

这是一个用于清晰BFS概念的静态代码。在此代码中，我使用了两个数组，一个是节点数组，另一个是边缘数组。通过递归，我打印出了有向图中每个节点的所有邻居。

 Graph is:  A-->D-->E
            |\  |   | 
            v \ v   v     
            B-->C <-|
           
 There is a Edge from A to C    

这是代码：

这是代码：

enter code here
 #include<stdio.h>
 int NodeArr[5][3]={{'A',1,0},
               {'B',2,3},
               {'C',3,-1},
               {'D',4,4},
               {'E',-1,6}};

  int edgeArr[7][2]={
                 //For A Node
                {'B',1},
                {'C',2},
                {'D',-1},
                 //For B Node
                {'C',-1},
                  //As C Node has no directed neighbour 
                 //For D Node
                {'C',5},
                {'E',-1},
                 //For E Node
                {'C',-1},};

  void printcharacter(int edge_index){
    printf("%c ",edgeArr[edge_index][0]);
     if(edgeArr[edge_index][1]==-1)
        return;

    printcharacter(edgeArr[edge_index][1]);

  }

int main(){

 printf("Neighbour of All Nodes for Directed Graph");
for(int i=0;i<5;i++){
   if(NodeArr[i][2]!=-1){
    int edge_index=NodeArr[i][2];
    printf("Neighbour of %c are ",NodeArr[i][0]);
    printcharacter(edge_index);
    printf("\n");
       }
 
     }
 }

- Ritanath Malakar